Srba, Jiří - Beyond Language Equivalence on Visibly Pushdown Automata

lmcs:756 - Logical Methods in Computer Science, January 26, 2009, Volume 5, Issue 1
Beyond Language Equivalence on Visibly Pushdown Automata

Authors: Srba, Jiří

We study (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.


Source : oai:arXiv.org:0901.2068
DOI : 10.2168/LMCS-5(1:2)2009
Volume: Volume 5, Issue 1
Published on: January 26, 2009
Submitted on: April 17, 2008
Keywords: Computer Science - Computational Complexity,Computer Science - Logic in Computer Science,F.4.3


Share

Consultation statistics

This page has been seen 51 times.
This article's PDF has been downloaded 35 times.