Detail publikačního výsledku

Internally Expandable Pushdown Automata and Their Computational Completeness

CHARVÁT, L.; MEDUNA, A.

Originální název

Internally Expandable Pushdown Automata and Their Computational Completeness

Anglický název

Internally Expandable Pushdown Automata and Their Computational Completeness

Druh

Článek WoS

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

Anglický 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

Klíčová slova v angličtině

pushdown automata, Turing power, state grammars, descriptional complexity

Autoři

CHARVÁT, L.; MEDUNA, A.

Rok RIV

2019

Vydáno

25.10.2018

ISSN

1453-8245

Periodikum

Romanian Journal of Information Science and Technology

Svazek

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",
  year="2018",
  volume="21",
  number="3",
  pages="232--237",
  issn="1453-8245",
  url="http://www.romjist.ro/full-texts/paper595.pdf"
}

Dokumenty

UDPDA_ROMJIST-2