Publication Details

Absolutely Unlimited Deep Pushdown Automata

KUČERA Jiří, MEDUNA Alexander and SOUKUP Ondřej. Absolutely Unlimited Deep Pushdown Automata. In: Proceedings of the 10th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2015). Telč: Ing. Vladislav Pokorný - Litera, 2015, pp. 36-44. ISBN 978-80-214-5254-1.
Czech title
Absolutně neomezené hluboké zásobníkové automaty
Type
conference paper
Language
english
Authors
Kučera Jiří, Ing., Ph.D. (DIFS FIT BUT)
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Soukup Ondřej, Ing. (DIFS FIT BUT)
Keywords
deep pushdown automata, unlimited deep pushdown automata, computational power, absolutely unlimited deep expansions
Abstract

This paper introduces an absolutely unlimited deep pushdown
automata and studies their computational power. These automata are generalized versions of recently introduced deep pushdown automata in the terms of the depth of expansions. They can
expand nonterminal pushdown symbol despite its depth. It is
shown that propagating and erasing versions of absolutely unlimited deep pushdown automata characterize type 1 and type 0 languages, respectively.

Published
2015
Pages
36-44
Proceedings
Proceedings of the 10th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2015)
Conference
MEMICS'15 - 10th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, Telč, CZ
ISBN
978-80-214-5254-1
Publisher
Ing. Vladislav Pokorný - Litera
Place
Telč, CZ
BibTeX 
@INPROCEEDINGS{FITPUB10978,
   author = "Ji\v{r}\'{i} Ku\v{c}era and Alexander Meduna and Ond\v{r}ej Soukup",
   title = "Absolutely Unlimited Deep Pushdown Automata",
   pages = "36--44",
   booktitle = "Proceedings of the 10th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2015)",
   year = 2015,
   location = "Tel\v{c}, CZ",
   publisher = "Ing. Vladislav Pokorn\'{y} - Litera",
   ISBN = "978-80-214-5254-1",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/10978"
}
Back to top