Conference paper

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). Telč, 2017, pp. 1-1.
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:1-1
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, Non-Input Pushdown Symbols
Annotation
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.
BibTeX:
@INPROCEEDINGS{
   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 = {http://www.fit.vutbr.cz/research/view_pub.php?id=11521}
}

Your IPv4 address: 54.225.59.14
Switch to IPv6 connection

DNSSEC [dnssec]