Publication Details

A Reduction of Finitely Expandable Deep Pushdown Automata

CHARVÁ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). Electronic Proceedings in Theoretical Computer Science. Telč, 2017, pp. 1-1.
Czech title
Redukce konečně expandovatelných hlubokých zásobníkových automatů
Type
conference paper
Language
english
Authors
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 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.

Published
2017
Pages
1-1
Proceedings
Proceedings 12th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2017)
Series
Electronic Proceedings in Theoretical Computer Science
Conference
MEMICS'17 - 12th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, Telč, CZ
Place
Telč, CZ
BibTeX
@INPROCEEDINGS{FITPUB11521,
   author = "Lucie Charv\'{a}t and Alexander Meduna",
   title = "A Reduction of Finitely Expandable Deep Pushdown Automata",
   pages = "1--1",
   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 = "https://www.fit.vut.cz/research/publication/11521"
}
Back to top