Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > FORMAL LANGUAGES, E0L SYSTEMS, PUSHDOWN AUTOMATA:
Reports tagged with Formal languages, E0L systems, pushdown automata:
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