Publication Details
A Reduction of Finitely Expandable Deep Pushdown Automata
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Deep Pushdown Automata, Finite Expandability, Reduction, Non-Input Pushdown
Symbols
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 presentation 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 presentation demonstrates an infinite hierarchy of language
families that follows from this main result. The presentation also points out
that if # is the only non-input symbol in these automata, then they characterize
the family of regular languages.
@inproceedings{BUT170110,
author="Lucie {Charvát} and Alexandr {Meduna}",
title="A Reduction of Finitely Expandable Deep Pushdown Automata",
booktitle="Proceedings 12th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2017)",
year="2017",
series="Electronic Proceedings in Theoretical Computer Science",
pages="1--1",
address="Telč",
url="https://www.fit.vut.cz/research/publication/11521/"
}