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.
Originalsprog | Engelsk |
---|---|
Titel | Computer Science Logic : Proceedings of 20th International Workshop, CSL 2006, 15th Annual Conference of the EACSL, Szeged, Hungary, September 25-29, 2006 |
Antal sider | 15 |
Forlag | IEEE Computer Society Press |
Publikationsdato | 2006 |
Sider | 89-103 |
ISBN (Trykt) | 9783540454588 |
DOI | |
Status | Udgivet - 2006 |
Begivenhed | Annual Conference on Computer Science Logic (CSL'06) - Szeged, Ungarn Varighed: 25 sep. 2006 → 29 sep. 2006 Konferencens nummer: 15 |
Konference
Konference | Annual Conference on Computer Science Logic (CSL'06) |
---|---|
Nummer | 15 |
Land/Område | Ungarn |
By | Szeged |
Periode | 25/09/2006 → 29/09/2006 |
Navn | Lecture Notes in Computer Science |
---|---|
Nummer | 4207 |
ISSN | 0302-9743 |