Internally Expandable Pushdown Automata and Their Computational Completeness
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F18%3APU130690" target="_blank" >RIV/00216305:26230/18:PU130690 - isvavai.cz</a>
Result on the web
<a href="http://www.romjist.ro/full-texts/paper595.pdf" target="_blank" >http://www.romjist.ro/full-texts/paper595.pdf</a>
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Internally Expandable Pushdown Automata and Their Computational Completeness
Original language description
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
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Romanian Journal of Information Science and Technology (ROMJIST)
ISSN
1453-8245
e-ISSN
—
Volume of the periodical
21
Issue of the periodical within the volume
3
Country of publishing house
RO - ROMANIA
Number of pages
6
Pages from-to
232-237
UT code for WoS article
000455900300004
EID of the result in the Scopus database
2-s2.0-85056635452