Publication Details

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.
Czech title
Zásobníkové automaty s vnitřním přepisem a jejich výpočetní úplnost
Type
journal article
Language
English
Authors
Charvát Lucie, Ing.
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
URL
Keywords

pushdown automata, Turing power, state grammars, descriptional complexity

Abstract

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

Published
2018
Pages
232–237
Journal
Romanian Journal of Information Science and Technology (ROMJIST), vol. 21, no. 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"
}
Back to top