Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Marek Kosta:

TR11-034 | 20th January 2011
Pavol Duris, Marek Kosta

Flip-Pushdown Automata with k Pushdown Reversals and E0L Systems are Incomparable

We prove that any propagating E0L system cannot generate the language containing all words of the form w#w. This result, together with some known ones, enable us to conclude that the flip-pushdown automata with k pushdown reversals (i.e. the pushdown automata with the ability to flip its pushdown) and E0L ... more >>>

ISSN 1433-8092 | Imprint