Přístupnostní navigace
E-application
Search Search Close
Publication detail
CHARVÁT, L. MEDUNA, A.
Original Title
A Reduction of Finitely Expandable Deep Pushdown Automata
Type
article in a collection out of WoS and Scopus
Language
English
Original 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.
Keywords
Deep Pushdown Automata, Finite Expandability, Reduction, Non-Input Pushdown Symbols
Authors
CHARVÁT, L.; MEDUNA, A.
Released
31. 12. 2017
Location
Telč
Pages from
1
Pages to
Pages count
URL
https://www.fit.vut.cz/research/publication/11521/
BibTex
@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/" }