Publication Details

Absolutely Unlimited Deep Pushdown Automata

MEDUNA, A.; KUČERA, J.; SOUKUP, O. Absolutely Unlimited Deep Pushdown Automata. Proceedings of the 10th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2015). Telč: Ing. Vladislav Pokorný - Litera, 2015. p. 36-44. ISBN: 978-80-214-5254-1.

Czech title

Absolutně neomezené hluboké zásobníkové automaty

Type

conference paper

Language

English

Authors

Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Kučera Jiří, Ing., Ph.D.
Soukup Ondřej, Ing., Ph.D.

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)

ISBN

978-80-214-5254-1

Publisher

Ing. Vladislav Pokorný - Litera

Place

Telč

BibTeX

@inproceedings{BUT119911,
  author="Alexandr {Meduna} and Jiří {Kučera} and Ondřej {Soukup}",
  title="Absolutely Unlimited Deep Pushdown Automata",
  booktitle="Proceedings of the 10th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2015)",
  year="2015",
  pages="36--44",
  publisher="Ing. Vladislav Pokorný - Litera",
  address="Telč",
  isbn="978-80-214-5254-1",
  url="https://www.fit.vut.cz/research/publication/10978/"
}