Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
427449 | Information Processing Letters | 2014 | 4 Pages |
Abstract
We prove that any propagating E0L system cannot generate the language {w#w|w∈{0,1}⁎}{w#w|w∈{0,1}⁎}. This result, together with some known ones, enables us to conclude that the flip-pushdown automata with k pushdown reversals, i.e., the pushdown automata with the ability to flip the pushdown, and E0L systems are incomparable. This result solves an open problem stated by Holzer and Kutrib in 2003.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Pavol Ďuriš, Marek Košta,