Name
Abstract | ||
|---|---|---|
A one-counter automaton is a pushdown automaton over a singleton stack alphabet. We prove that the bisimilarity of processes generated by nondeterministic one-counter automata (with no ε-steps) is in PSPACE. This improves the previously known decidability result (Jančar 2000), and matches the known PSPACE lower bound (Srba 2009). We add the PTIME-completeness result for deciding regularity (i.e. finiteness up to bisimilarity) of one-counter processes. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-15375-4_13 | CONCUR |
Keywords | Field | DocType |
pushdown automaton,known pspace,one-counter automaton,ptime-completeness result,one-counter process,decidability result,nondeterministic one-counter automaton,lower bound | Transition system,Discrete mathematics,Combinatorics,Nondeterministic algorithm,Upper and lower bounds,PSPACE-complete,Automaton,Decidability,PSPACE,Pushdown automaton,Mathematics | Conference |
Volume | ISSN | ISBN |
6269 | 0302-9743 | 3-642-15374-7 |
Citations | PageRank | References |
10 | 0.62 | 27 |
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 |