Detail publikace

Controlled Finite Automata

MEDUNA Alexander a ZEMEK Petr. Controlled Finite Automata. Acta Informatica, roč. 51, č. 5, 2014, s. 327-337. ISSN 0001-5903. Dostupné z: http://link.springer.com/article/10.1007/s00236-014-0199-5
Název česky
Řízené konečné automaty
Typ
článek v časopise
Jazyk
angličtina
Autoři
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
Zemek Petr, Ing. (UIFS FIT VUT)
URL
Klíčová slova

konečné automaty, řízené přijímání, řídící jazyky, přijímací síla, výpočetní úplnost, redukce

Abstrakt

Článek diskutuje konečné automaty regulované řídícími jazyky definovanými nad stavy a přechodovými pravidly. Dokazuje, že s oběma typy řízení konečné automaty řízené regulárními a bezkontextovými jazyky definují třídu regulárních respektive bezkontextových jazyků. Taktéž ustanovuje podmínky, za kterých je možné konečné automaty řízené stavy transformovat na ekvivalentní konečné automaty řízené přechodovými pravidly a naopak. Článek dále demonstruje blízký vztah mezi těmito automaty a programovanými gramatikami. Dokazuje, že konečné automaty řízené jazyky generovanými programovanými gramatiky s kontrolou na výskyt bez vymazávacích pravidel jsou výpočetně úplně. Ve skutečnosti je ukázáno, že jejich výpočetní úplnost platí i v případě, kdy mají tyto automaty omezený počet stavů.

Rok
2014
Strany
327-337
Časopis
Acta Informatica, roč. 51, č. 5, ISSN 0001-5903
Vydavatel
Springer Verlag
DOI
10.1007/s00236-014-0199-5
UT WoS
000339103700003
EID Scopus
2-s2.0-84903900178
BibTeX 
@ARTICLE{FITPUB9893,
   author = "Alexander Meduna and Petr Zemek",
   title = "Controlled Finite Automata",
   pages = "327--337",
   journal = "Acta Informatica",
   volume = 51,
   number = 5,
   year = 2014,
   ISSN = "0001-5903",
   doi = "10.1007/s00236-014-0199-5",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9893"
}
Nahoru