Detail publikace

Internally Expandable Pushdown Automata and Their Computational Completeness

CHARVÁT, L.; MEDUNA, A. Internally Expandable Pushdown Automata and Their Computational Completeness. Romanian Journal of Information Science and Technology (ROMJIST), 2018, vol. 21, no. 3, p. 232-237. ISSN: 1453-8245.
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
anglicky
Autoři
Charvát Lucie, Ing.
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
URL
Klíčová slova

pushdown automata, Turing power, state grammars, descriptional complexity

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
UT WoS
000455900300004
EID Scopus
2-s2.0-85056635452
BibTeX 
@article{BUT154998,
  author="Lucie {Charvát} and Alexandr {Meduna}",
  title="Internally Expandable Pushdown Automata and Their Computational Completeness",
  journal="Romanian Journal of Information Science and Technology (ROMJIST)",
  year="2018",
  volume="21",
  number="3",
  pages="232--237",
  issn="1453-8245",
  url="http://www.romjist.ro/full-texts/paper595.pdf"
}
Nahoru