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, 2018, 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
Charvát Lucie, Ing. (DIFS FIT BUT)
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
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
10.4467/20838476SI.17.005.8151
EID Scopus
2-s2.0-85057858123
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