Publication detail

Absolutely Unlimited Deep Pushdown Automata

MEDUNA, A. KUČERA, J. SOUKUP, O.

Original Title

Absolutely Unlimited Deep Pushdown Automata

Type

article in a collection out of WoS and Scopus

Language

English

Original 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.

Keywords

deep pushdown automata, unlimited deep pushdown automata, computational power, absolutely unlimited deep expansions

Authors

MEDUNA, A.; KUČERA, J.; SOUKUP, O.

RIV year

2015

Released

23. 10. 2015

Publisher

Ing. Vladislav Pokorný - Litera

Location

Telč

ISBN

978-80-214-5254-1

Book

Proceedings of the 10th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2015)

Pages from

36

Pages to

44

Pages count

9

URL

https://www.fit.vut.cz/research/publication/10978/

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/"
}

Documents

paper2.pdf
paper2-src.zip