Detail publikace

Internally Expandable Pushdown Automata and Their Computational Completeness

CHARVÁT Lucie a MEDUNA Alexander. Internally Expandable Pushdown Automata and Their Computational Completeness. Romanian Journal of Information Science and Technology (ROMJIST), roč. 21, č. 3, 2018, s. 232-237. ISSN 1453-8245. Dostupné z: http://www.romjist.ro/full-texts/paper595.pdf
Název česky
Zásobníkové automaty s vnitřním přepisem a jejich výpočetní úplnost
Typ
článek v časopise
Jazyk
angličtina
Autoři
Charvát Lucie, Ing. (UIFS FIT VUT)
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
URL
Abstrakt

Č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.

Rok
2018
Strany
232-237
Časopis
Romanian Journal of Information Science and Technology (ROMJIST), roč. 21, č. 3, ISSN 1453-8245
Vydavatel
Romanian Academy, Publishing House of the Romanian Academy
UT WoS
000455900300004
EID Scopus
2-s2.0-85056635452
BibTeX 
@ARTICLE{FITPUB11554,
   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 = "https://www.fit.vut.cz/research/publication/11554"
}
Nahoru