Name
Abstract | ||
|---|---|---|
Flip-pushdown automata are pushdown automata with the additional power to flip or reverse its pushdown, and were recently
introduced by Sarkar [13]. We solve most of Sarkar’s open problems. In particular, we show that k+1 pushdown reversals are better than k for both deterministic and nondeterministic flip-pushdown automata, i.e., there are languages which can be recognized by
a deterministic flip-pushdown automaton with k+1 pushdown reversals but which cannot be recognized by a k-flip-pushdown (deterministic or nondeterministic). Furthermore, we investigate closure and non-closure properties as well
as computational complexity problems such as fixed and general membership.
|
Year | DOI | Venue |
|---|---|---|
2003 | 10.1007/3-540-45061-0_40 | ICALP'03 Proceedings of the 30th international conference on Automata, languages and programming |
Keywords | Field | DocType |
deterministic flip-pushdown automaton,pushdown automaton,open problem,general membership,pushdown reversal,non-closure property,computational complexity problem,nondeterministic flip-pushdown automaton,additional power,flip-pushdown automaton,pushdown automata | Deterministic context-free grammar,Embedded pushdown automaton,Discrete mathematics,Combinatorics,Two-way deterministic finite automaton,Context-free language,Nested word,Computer science,Deterministic pushdown automaton,Deterministic context-free language,Pushdown automaton | Conference |
Volume | ISSN | ISBN |
2719 | 0302-9743 | 3-540-40493-7 |
Citations | PageRank | References |
20 | 1.28 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Markus Holzer | 1 | 138 | 12.30 |
| Martin Kutrib | 2 | 778 | 89.77 |