Detail publikace

Absolutely Unlimited Deep Pushdown Automata

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

Originální název

Absolutely Unlimited Deep Pushdown Automata

Anglický název

Absolutely Unlimited Deep Pushdown Automata

Jazyk

en

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.

Anglický 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.

Dokumenty

BibTex 


@inproceedings{BUT119911,
  author="Alexandr {Meduna} and Jiří {Kučera} and Ondřej {Soukup}",
  title="Absolutely Unlimited Deep Pushdown Automata",
  annote="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.",
  address="Ing. Vladislav Pokorný - Litera",
  booktitle="Proceedings of the 10th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2015)",
  chapter="119911",
  edition="NEUVEDEN",
  howpublished="print",
  institution="Ing. Vladislav Pokorný - Litera",
  year="2015",
  month="october",
  pages="36--44",
  publisher="Ing. Vladislav Pokorný - Litera",
  type="conference paper"
}