Journal article

CHARVÁT Lucie and MEDUNA Alexander. A Reduction of Finitely Expandable Deep Pushdown Automata. Schedae Informaticae. Krakov: 2018, vol. 2017, no. 26, pp. 61-68. ISSN 0860-0295.
Publication language:english
Original title:A Reduction of Finitely Expandable Deep Pushdown Automata
Title (cs):Redukce konečně expandovatelných hlubokých zásobníkových automatů
Pages:61-68
Place:PL
Year:2018
Journal:Schedae Informaticae, Vol. 2017, No. 26, Krakov, PL
ISSN:0860-0295
DOI:10.4467/20838476SI.17.005.8151
URL:http://www.ejournals.eu/Schedae-Informaticae/2017/Volume-26/art/10836/ [HTML]
Keywords
Deep Pushdown Automata, Finite Expandability, Reduction, Non-Input Pushdown Symbols
Annotation
For a positive integer n, n-expandable deep pushdown automata always contain no more than n occurrences of non-input symbols in their pushdowns during any computation. As its main result, the paper demonstrates that these automata are as powerful as the same automata with only two non-input pushdown symbols---$ and #, where # always appears solely as the pushdown bottom. Moreover, the paper demonstrates an infinite hierarchy of language families that follows from this main result. The paper also points out that if # is the only non-input symbol in these automata, then they characterize the family of regular languages.
BibTeX:
@ARTICLE{
   author = {Lucie Charv{\'{a}}t and Alexander Meduna},
   title = {A Reduction of Finitely Expandable Deep Pushdown
	Automata},
   pages = {61--68},
   journal = {Schedae Informaticae},
   volume = {2017},
   number = {26},
   year = {2018},
   ISSN = {0860-0295},
   doi = {10.4467/20838476SI.17.005.8151},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php.en.iso-8859-2?id=11519}
}

Your IPv4 address: 54.166.133.84
Switch to https

DNSSEC [dnssec]