Department of Information Systems
Conference paperCHARVÁT Lucie and MEDUNA Alexander. A Reduction of Finitely Expandable Deep Pushdown Automata. In: Proceedings 12th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2017). Telč, 2017, pp. 11.  Publication language:  english 

Original title:  A Reduction of Finitely Expandable Deep Pushdown Automata 

Title (cs):  Redukce konečně expandovatelných hlubokých zásobníkových automatů 

Pages:  11 

Proceedings:  Proceedings 12th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2017) 

Conference:  MEMICS'17  12th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science 

Series:  Electronic Proceedings in Theoretical Computer Science 

Place:  Telč, CZ 

Year:  2017 

Keywords 

Deep Pushdown Automata, Finite Expandability, Reduction, NonInput Pushdown Symbols 
Annotation 

For a positive integer n, nexpandable deep pushdown automata always contain no more than n occurrences of noninput 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 noninput 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 noninput symbol in these automata, then they characterize the family of regular languages. 
BibTeX: 

@INPROCEEDINGS{
author = {Lucie Charv{\'{a}}t and Alexander Meduna},
title = {A Reduction of Finitely Expandable Deep Pushdown
Automata},
pages = {11},
booktitle = {Proceedings 12th Doctoral Workshop on Mathematical and
Engineering Methods in Computer Science (MEMICS 2017)},
series = {Electronic Proceedings in Theoretical Computer Science},
year = 2017,
location = {Tel{\v{c}}, CZ},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php.en?id=11521}
} 
