Faculty of Information Technology, BUT

Publication Details

A Reduction of Finitely Expandable Deep Pushdown Automata

CHARVÁT Lucie and MEDUNA Alexander. A Reduction of Finitely Expandable Deep Pushdown Automata. Schedae Informaticae, vol. 2017, no. 26, pp. 61-68. ISSN 0860-0295.
Czech title
Redukce konečně expandovatelných hlubokých zásobníkových automatů
Type
journal article
Language
english
Authors
URL
Keywords
Deep Pushdown Automata, Finite Expandability, Reduction, Non-Input Pushdown Symbols
Abstract
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.
Published
2018
Pages
61-68
Journal
Schedae Informaticae, vol. 2017, no. 26, ISSN 0860-0295
DOI
BibTeX
@ARTICLE{FITPUB11519,
   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 = "https://www.fit.vut.cz/research/publication/11519"
}
Back to top