Publication Details

A Reduction of Finitely Expandable Deep Pushdown Automata

CHARVÁT, L.; MEDUNA, A. A Reduction of Finitely Expandable Deep Pushdown Automata. Proceedings 12th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2017). Electronic Proceedings in Theoretical Computer Science. Telč: 2017. p. 1 (1 s.).
Czech title
Redukce konečně expandovatelných hlubokých zásobníkových automatů
Type
conference paper
Language
English
Authors
Charvát Lucie, Ing.
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
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
Place
Telč
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/"
}
Back to top