Článek v časopise

MEDUNA Alexander a ZEMEK Petr. Controlled Finite Automata. Acta Informatica. 2014, roč. 51, č. 5, s. 327-337. ISSN 0001-5903. Dostupné z: http://link.springer.com/article/10.1007/s00236-014-0199-5
Jazyk publikace:angličtina
Název publikace:Controlled Finite Automata
Název (cs):Řízené konečné automaty
Strany:327-337
Místo vydání:DE
Rok:2014
URL:http://link.springer.com/article/10.1007/s00236-014-0199-5
Časopis:Acta Informatica, roč. 51, č. 5, DE
ISSN:0001-5903
DOI:10.1007/s00236-014-0199-5
Klíčová slova
konečné automaty, řízené přijímání, řídící jazyky, přijímací síla, výpočetní úplnost, redukce
Anotace
Č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ů.
BibTeX:
@ARTICLE{
   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 = {http://www.fit.vutbr.cz/research/view_pub.php.cs.iso-8859-2?id=9893}
}

Vaše IPv4 adresa: 3.83.192.109
Přepnout na https