Detail publikace

Reducing Deep Pushdown Automata and Infinite Hierarchy

SCHÖNECKER, R. KŘIVKA, Z. MEDUNA, A.

Originální název

Reducing Deep Pushdown Automata and Infinite Hierarchy

Typ

článek ve sborníku ve WoS nebo Scopus

Jazyk

angličtina

Originální abstrakt

This contribution presents reducing variant of the deep pushdown automata. Deep pushdown automata is a new generalization of the classical pushdown automata. The basic idea of the modification consists of allowing these automata to access more deeper parts of pushdown and reducing strings to non-input symbols in the pushdown. It works similarly to bottom-up analysis simulation of context-free grammars in the classical pushdown automata except it reads the input from the right to the left. Further, this paper presents results concerning the equivalence of reducing deep pushdown automata with n-limited state grammars and infinite hierarchy of language families based on that and one open problem.

Klíčová slova

Automata Theory, Top-Down Parser, Bottom-Up Parser, Deep Pushdown Automata, Infinite hierarchy, Reduction Operation, Shift Operation

Autoři

SCHÖNECKER, R.; KŘIVKA, Z.; MEDUNA, A.

Rok RIV

2006

Vydáno

27. 10. 2006

Nakladatel

Faculty of Information Technology BUT

Místo

Mikulov

ISBN

80-214-3287-X

Kniha

MEMICS 2006 Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science

Strany od

214

Strany do

221

Strany počet

8

BibTex

@inproceedings{BUT22277,
  author="Rudolf {Schönecker} and Zbyněk {Křivka} and Alexandr {Meduna}",
  title="Reducing Deep Pushdown Automata and Infinite Hierarchy",
  booktitle="MEMICS 2006 Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science",
  year="2006",
  pages="214--221",
  publisher="Faculty of Information Technology BUT",
  address="Mikulov",
  isbn="80-214-3287-X"
}