Publication Details
Internally Expandable Pushdown Automata and Their Computational Completeness
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
pushdown automata, Turing power, state grammars, descriptional complexity
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
@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"
}