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
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
UT WoS
000339103700003
EID Scopus
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