Computer Science – Computational Complexity
Scientific paper
2009-01-14
LMCS 5 (1:2) 2009
Computer Science
Computational Complexity
Final version of paper, accepted by LMCS
Scientific paper
10.2168/LMCS-5(1:2)2009
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.
No associations
LandOfFree
Beyond Language Equivalence on Visibly Pushdown Automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Beyond Language Equivalence on Visibly Pushdown Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Beyond Language Equivalence on Visibly Pushdown Automata will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-376033