Abstract
We investigate the possibility of (bi)simulation-like preorder/equivalence checking on the class of visibly pushdown automata and its natural subclasses visibly BPA (Basic Process Algebra) and visibly one-counter automata. We describe generic methods for proving complexity upper and lower bounds for a number of studied preorders and equivalences like simulation, completed simulation, ready simulation, 2-nested simulation preorders/equivalences and bisimulation equivalence. Our main results are that all the mentioned equivalences and preorders are EXPTIME-complete on visibly pushdown automata, PSPACE-complete on visibly one-counter automata and P-complete on visibly BPA. Our PSPACE lower bound for visibly one-counter automata improves also the previously known DP-hardness results for ordinary one-counter automata and one-counter nets. Finally, we study regularity checking problems for visibly pushdown automata and show that they can be decided in polynomial time.
| Original language | English |
|---|---|
| Title of host publication | Computer Science Logic : Proceedings of 20th International Workshop, CSL 2006, 15th Annual Conference of the EACSL, Szeged, Hungary, September 25-29, 2006 |
| Number of pages | 15 |
| Publisher | IEEE Computer Society Press |
| Publication date | 2006 |
| Pages | 89-103 |
| ISBN (Print) | 9783540454588 |
| DOIs | |
| Publication status | Published - 2006 |
| Event | Annual Conference on Computer Science Logic (CSL'06) - Szeged, Hungary Duration: 25 Sept 2006 → 29 Sept 2006 Conference number: 15 |
Conference
| Conference | Annual Conference on Computer Science Logic (CSL'06) |
|---|---|
| Number | 15 |
| Country/Territory | Hungary |
| City | Szeged |
| Period | 25/09/2006 → 29/09/2006 |
| Series | Lecture Notes in Computer Science |
|---|---|
| Number | 4207 |
| ISSN | 0302-9743 |