Publication result detail

Reducing Deep Pushdown Automata

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

Original Title

Reducing Deep Pushdown Automata

English Title

Reducing Deep Pushdown Automata

Type

Paper in proceedings outside WoS and Scopus

Original Abstract

This contribution presents reducing variant of the deep pushdown automata.
Deep pushdown automata is a new generalization of the classical pushdown automata.
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.
Further, this paper presents results of equivalence of reducing deep pushdown automata with n-limited state grammars
and infinite hierarchy of language families based on that.

English abstract

This contribution presents reducing variant of the deep pushdown automata.
Deep pushdown automata is a new generalization of the classical pushdown automata.
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.
Further, this paper presents results of equivalence of reducing deep pushdown automata with n-limited state grammars
and infinite hierarchy of language families based on that.

Keywords

Deep Pushdown Automata, State Grammars, Infinite hierarchy, Deep Bottom-Up Parser

Key words in English

Deep Pushdown Automata, State Grammars, Infinite hierarchy, Deep Bottom-Up Parser

Authors

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

Released

27.04.2006

Publisher

Faculty of Information Technology BUT

Location

Brno

ISBN

80-214-3163-6

Book

Proceedings of the 12th Conference and Competition STUDENT EEICT 2006 Volume 4

Pages from

365

Pages to

369

Pages count

5

URL

http://www.feec.vutbr.cz/EEICT/2006/sbornik/03-Doktorske_projekty/07-Informacni_systemy/04-krivka.pdf

BibTex

@inproceedings{BUT192592,
  author="Zbyněk {Křivka} and Rudolf {Schönecker}",
  title="Reducing Deep Pushdown Automata",
  booktitle="Proceedings of the 12th Conference and Competition STUDENT EEICT 2006 Volume 4",
  year="2006",
  pages="365--369",
  publisher="Faculty of Information Technology BUT",
  address="Brno",
  isbn="80-214-3163-6",
  url="http://www.feec.vutbr.cz/EEICT/2006/sbornik/03-Doktorske_projekty/07-Informacni_systemy/04-krivka.pdf"
}