Journal article

CHARVÁT Lucie and MEDUNA Alexander. Internally Expandable Pushdown Automata and Their Computational Completeness. Romanian Journal of Information Science and Technology (ROMJIST). Bukurest: Romanian Academy, Publishing House of the Romanian Academy, 2018, vol. 21, no. 3, pp. 232-237. ISSN 1453-8245. Available from: http://www.romjist.ro/full-texts/paper595.pdf
Publication language:english
Original title:Internally Expandable Pushdown Automata and Their Computational Completeness
Title (cs):Zásobníkové automaty s vnitřním přepisem a jejich výpočetní úplnost
Pages:232-237
Place:RO
Year:2018
URL:http://www.romjist.ro/full-texts/paper595.pdf
Journal:Romanian Journal of Information Science and Technology (ROMJIST), Vol. 21, No. 3, Bukurest, RO
ISSN:1453-8245
Keywords
pushdown automata, Turing power, state grammars, descriptional complexity
Annotation
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
BibTeX:
@ARTICLE{
   author = {Lucie Charv{\'{a}}t and Alexander Meduna},
   title = {Internally Expandable Pushdown Automata and Their
	Computational Completeness},
   pages = {232--237},
   journal = {Romanian Journal of Information Science and Technology
	(ROMJIST)},
   volume = {21},
   number = {3},
   year = {2018},
   ISSN = {1453-8245},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=11554}
}

Your IPv4 address: 18.234.51.17
Switch to https