Name
Abstract | ||
|---|---|---|
The deterministic shrinking two-pushdown automata characterize the deterministic growing context-sensitive languages, known to be the Church-Rosser languages. Here, we initiate the investigation of reversible two-pushdown automata, RTPDAs, in particular the shrinking variant. We show that as with the deterministic version, shrinking and length-reducing RTPDAs are equivalent. We then give a separation of the deterministic and reversible shrinking two-pushdown automata, and prove that these are incomparable with the (deterministic) context-free languages. We further show that the properties of emptiness, (in) finiteness, universality, inclusion, equivalence, regularity, and context-freeness are not even semi-decidable for shrinking RTPDAs. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-319-30000-9_44 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
Unconventional models of computation,Reversible computing,Shrinking two-pushdown automata,Church-Rosser languages | Discrete mathematics,Computer science,Automaton,Reversible computing,Equivalence (measure theory),Pushdown automaton,Universality (philosophy) | Conference |
Volume | ISSN | Citations |
9618 | 0302-9743 | 1 |
PageRank | References | Authors |
0.35 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Holger Bock Axelsen | 1 | 243 | 20.18 |
| Markus Holzer | 2 | 138 | 12.30 |
| Martin Kutrib | 3 | 778 | 89.77 |
| Andreas Malcher | 4 | 204 | 39.40 |