Publication result detail

Absolutely Unlimited Deep Pushdown Automata

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

Original Title

Absolutely Unlimited Deep Pushdown Automata

English Title

Absolutely Unlimited Deep Pushdown Automata

Type

Paper in proceedings outside WoS and Scopus

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.

English 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

Key words in English

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

Authors

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

RIV year

2016

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
paper2-src