Přístupnostní navigace
E-application
Search Search Close
Publication detail
CHARVÁT, L. MEDUNA, A.
Original Title
A Reduction of Finitely Expandable Deep Pushdown Automata
Type
journal article in Scopus
Language
English
Original 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.
Keywords
Deep Pushdown Automata, Finite Expandability, Reduction, Non-Input Pushdown Symbols
Authors
CHARVÁT, L.; MEDUNA, A.
Released
16. 2. 2018
ISBN
0860-0295
Periodical
Schedae Informaticae
Year of study
2017
Number
26
State
Republic of Poland
Pages from
61
Pages to
68
Pages count
8
URL
http://www.ejournals.eu/Schedae-Informaticae/2017/Volume-26/art/10836/
BibTex
@article{BUT157232, author="Lucie {Charvát} and Alexandr {Meduna}", title="A Reduction of Finitely Expandable Deep Pushdown Automata", journal="Schedae Informaticae", year="2018", volume="2017", number="26", pages="61--68", doi="10.4467/20838476SI.17.005.8151", issn="0860-0295", url="http://www.ejournals.eu/Schedae-Informaticae/2017/Volume-26/art/10836/" }