Přístupnostní navigace
E-přihláška
Vyhledávání Vyhledat Zavřít
Detail publikace
CHARVÁT, L. MEDUNA, A.
Originální název
Internally Expandable Pushdown Automata and Their Computational Completeness
Typ
článek v časopise ve Web of Science, Jimp
Jazyk
angličtina
Originální abstrakt
The present paper defines the notion of an internally expandable pushdown automaton (IEPDA). In essence, this automaton expands the topmost expandable non-input symbol in its pushdown list. This expanded symbol, however, may not occur on the very top of the pushdown; instead, it may appear deeper in the pushdown. The paper demonstrates that this notion represents an automaton-based counter part to the notion of a state grammar. Indeed, both are equally powerful. Therefore, internally expandable pushdown automata are computationally complete--that is, they are as powerful as Turing machines. In fact there are computationally complete IEPDAs with no more than four states
Klíčová slova
pushdown automata, Turing power, state grammars, descriptional complexity
Autoři
CHARVÁT, L.; MEDUNA, A.
Vydáno
25. 10. 2018
ISSN
1453-8245
Periodikum
Romanian Journal of Information Science and Technology (ROMJIST)
Ročník
21
Číslo
3
Stát
Rumunsko
Strany od
232
Strany do
237
Strany počet
6
URL
http://www.romjist.ro/full-texts/paper595.pdf
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" }