Publication Details

Reducing Deep Pushdown Automata

KŘIVKA Zbyněk and SCHÖNECKER Rudolf. Reducing Deep Pushdown Automata. In: Proceedings of the 12th Conference and Competition STUDENT EEICT 2006 Volume 4. Brno: Faculty of Information Technology BUT, 2006, pp. 365-369. ISBN 80-214-3163-6.
Czech title
Redukující hluboký zásobníkový automat
Type
conference paper
Language
english
Authors
Křivka Zbyněk, Ing., Ph.D. (DIFS FIT BUT)
Schönecker Rudolf, Ing. (DIFS FIT BUT)
URL
Keywords
Deep Pushdown Automata, State Grammars, Infinite hierarchy, Deep Bottom-Up Parser
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.

Published
2006
Pages
365-369
Proceedings
Proceedings of the 12th Conference and Competition STUDENT EEICT 2006 Volume 4
Conference
Student EEICT 2006, Brno, CZ
ISBN
80-214-3163-6
Publisher
Faculty of Information Technology BUT
Place
Brno, CZ
BibTeX 
@INPROCEEDINGS{FITPUB8046,
   author = "Zbyn\v{e}k K\v{r}ivka and Rudolf Sch{\"{o}}necker",
   title = "Reducing Deep Pushdown Automata",
   pages = "365--369",
   booktitle = "Proceedings of the 12th Conference and Competition STUDENT EEICT 2006 Volume 4",
   year = 2006,
   location = "Brno, CZ",
   publisher = "Faculty of Information Technology BUT",
   ISBN = "80-214-3163-6",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8046"
}
Back to top