Visibly Pushdown Automata: From Language Equivalence to Simulation and Bisimulation

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

SRBA Jiří

Year of publication 2006
Type Article in Periodical
Magazine / Source LNCS, Annual Conference on Computer Science Logic (CSL'06)
MU Faculty or unit

Faculty of Informatics

Citation
Field Informatics
Keywords visibly pushdown automata; bisimilarity; decidability
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.