Detail publikace

Absolutely Unlimited Deep Pushdown Automata

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

Originální název

Absolutely Unlimited Deep Pushdown Automata

Typ

článek ve sborníku mimo WoS a Scopus

Jazyk

angličtina

Originální abstrakt

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.

Klíčová slova

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

Autoři

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

Rok RIV

2015

Vydáno

23. 10. 2015

Nakladatel

Ing. Vladislav Pokorný - Litera

Místo

Telč

ISBN

978-80-214-5254-1

Kniha

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

Strany od

36

Strany do

44

Strany počet

9

URL

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