Článek v časopise

CHARVÁT Lucie a MEDUNA Alexander. Internally Expandable Pushdown Automata and Their Computational Completeness. Romanian Journal of Information Science and Technology (ROMJIST). Bukurest: Romanian Academy, Publishing House of the Romanian Academy, 2018, roč. 21, č. 3, s. 232-237. ISSN 1453-8245. Dostupné z: http://www.romjist.ro/full-texts/paper595.pdf
Jazyk publikace:angličtina
Název publikace:Internally Expandable Pushdown Automata and Their Computational Completeness
Název (cs):Zásobníkové automaty s vnitřním přepisem a jejich výpočetní úplnost
Strany:232-237
Místo vydání:RO
Rok:2018
URL:http://www.romjist.ro/full-texts/paper595.pdf
Časopis:Romanian Journal of Information Science and Technology (ROMJIST), roč. 21, č. 3, Bukurest, RO
ISSN:1453-8245
Klíčová slova
pushdown automata, Turing power, state grammars, descriptional complexity
Anotace
Článek definuje nový pojem zásobníkového automatu s vnitřním přepisem (IEPDA). V podstatě tento automat přepisuje nejvrchnější nevstupní symbol ve své zásobníkové paměti. Tento přepis tedy nemusí proběhnout na samém vrcholu zásobníku, ale může se odehrát hlouběji v zásobníku. Článek demonstruje, že tento model reprezentuje automatový ekvivalent pro stavové gramatiky, takže mají oba modely stejnou výpočetní sílu. Tedy jsou výpočetně úplné neboli mají sílu Turingových strojů. Ve skutečnosti pro tento výsledek vždy postačí IEPDA s maximálně čtyřmi stavy.
BibTeX:
@ARTICLE{
   author = {Lucie Charv{\'{a}}t and Alexander Meduna},
   title = {Internally Expandable Pushdown Automata and Their
	Computational Completeness},
   pages = {232--237},
   journal = {Romanian Journal of Information Science and Technology
	(ROMJIST)},
   volume = {21},
   number = {3},
   year = {2018},
   ISSN = {1453-8245},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php.cs?id=11554}
}

Vaše IPv4 adresa: 107.23.129.77