Name
Abstract | ||
|---|---|---|
Equivalence of deterministic pushdown automata is a famous problem in theoretical computer science whose decidability has been shown by Senizergues. Our first result shows that decidability no longer holds when moving from finite words to infinite words. This solves an open problem that has recently been raised by Lading. In fact, we show that already the equivalence problem for deterministic Buchi one-counter automata is undecidable. Hence, the decidability border is rather tight when taking into account a recent result by Loding and Repke that equivalence of deterministic weak parity pushdown automata (a subclass of deterministic Biichi pushdown automata) is decidable. Another known result on finite words is that the universality problem for vector addition systems is decidable. We show undecidability when moving to infinite words. In fact, we prove that already the universality problem for nondeterministic Buchi one-counter nets (or equivalently vector addition systems with one unbounded dimension) is undecidable. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.4230/LIPIcs.STACS-2017.14 | Leibniz International Proceedings in Informatics |
Keywords | Field | DocType |
infinite words,deterministic pushdown automata | Deterministic context-free grammar,Discrete mathematics,Combinatorics,Open problem,Nondeterministic algorithm,Nested word,Deterministic pushdown automaton,Decidability,Pushdown automaton,Mathematics,Undecidable problem | Conference |
Volume | ISSN | Citations |
66 | 1868-8969 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stanislav Böhm | 1 | 50 | 8.69 |
| Stefan Göller | 2 | 148 | 15.10 |
| Simon Halfon | 3 | 0 | 0.34 |
| Piotr Hofman | 4 | 61 | 11.43 |