Name
Abstract | ||
|---|---|---|
We prove that language equivalence of deterministic one-counter automata is NL-complete. This improves the superpolynomial time complexity upper bound shown by Valiant and Paterson in 1975. Our main contribution is to prove that two deterministic one-counter automata are inequivalent if and only if they can be distinguished by a word of length polynomial in the size of the two input automata. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2488608.2488626 | symposium on the theory of computing |
Keywords | DocType | Volume |
superpolynomial time complexity,main contribution,language equivalence,deterministic one-counter automaton,length polynomial,input automaton,computational complexity | Conference | abs/1301.2181 |
Citations | PageRank | References |
12 | 0.54 | 21 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stanislav Böhm | 1 | 50 | 8.69 |
| Stefan Göller | 2 | 148 | 15.10 |
| Petr Jančar | 3 | 315 | 20.84 |