TY - JOUR
TI - A Reduction of Finitely Expandable Deep Pushdown Automata
AU - Dvořáková, Lucie
AU - Meduna, Alexander
TI - A Reduction of Finitely Expandable Deep Pushdown Automata
AB - 
	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 present 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. 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. In its conclusion, the paper suggests open problems and topics for the future investigation.
VL - 2017
IS - Volume 26
PY - 2018
SN - 1732-3916
C1 - 2083-8476
SP - 61
EP - 68
DO - 10.4467/20838476SI.17.005.8151
UR - https://ejournals.eu/en/journal/schedae-informaticae/article/a-reduction-of-finitely-expandable-deep-pushdown-automata
KW - Finite Expandability
KW - Reduction
KW - Non- Input Pushdown Symbols
KW - Deep Pushown Automata