Conference paper

KŘIVKA Zbyněk, MEDUNA Alexander and SCHÖNECKER Rudolf. Reducing Deep Pushdown Automata and Infinite Hierarchy. In: MEMICS 2006 Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Mikulov: Faculty of Information Technology BUT, 2006, pp. 214-221. ISBN 80-214-3287-X.
Publication language:english
Original title:Reducing Deep Pushdown Automata and Infinite Hierarchy
Title (cs):Redukující hluboké zásobníkové automaty a nekonečná hierarchie
Pages:214-221
Proceedings:MEMICS 2006 Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
Conference:2nd Doctoral Workshop on Mathematical and Engineering Methods in Computer Science -- MEMICS'06
Place:Mikulov, CZ
Year:2006
ISBN:80-214-3287-X
Publisher:Faculty of Information Technology BUT
Keywords
Automata Theory, Top-Down Parser, Bottom-Up Parser, Deep Pushdown Automata, Infinite hierarchy, Reduction Operation, Shift Operation
Annotation
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.
BibTeX:
@INPROCEEDINGS{
   author = {Zbyn{\v{e}}k K{\v{r}}ivka and Alexander Meduna and Rudolf
	Sch{\"{o}}necker},
   title = {Reducing Deep Pushdown Automata and Infinite Hierarchy},
   pages = {214--221},
   booktitle = {MEMICS 2006 Second Doctoral Workshop on Mathematical and
	Engineering Methods in Computer Science},
   year = {2006},
   location = {Mikulov, CZ},
   publisher = {Faculty of Information Technology BUT},
   ISBN = {80-214-3287-X},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=8193}
}

Your IPv4 address: 54.166.228.35
Switch to IPv6 connection

DNSSEC [dnssec]