SRBA, Jiří. Visibly Pushdown Automata: From Language Equivalence to Simulation and Bisimulation. LNCS, Annual Conference on Computer Science Logic (CSL'06). Netherlands: Springer-Verlag, 2006, roč. 2006, č. 4207, s. 89-103. |
Další formáty:
BibTeX
LaTeX
RIS
@article{702214, author = {Srba, Jiří}, article_location = {Netherlands}, article_number = {4207}, keywords = {visibly pushdown automata; bisimilarity; decidability}, language = {eng}, journal = {LNCS, Annual Conference on Computer Science Logic (CSL'06)}, title = {Visibly Pushdown Automata: From Language Equivalence to Simulation and Bisimulation}, volume = {2006}, year = {2006} }
TY - JOUR ID - 702214 AU - Srba, Jiří PY - 2006 TI - Visibly Pushdown Automata: From Language Equivalence to Simulation and Bisimulation JF - LNCS, Annual Conference on Computer Science Logic (CSL'06) VL - 2006 IS - 4207 SP - 89-103 EP - 89-103 PB - Springer-Verlag KW - visibly pushdown automata KW - bisimilarity KW - decidability N2 - 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. ER -
SRBA, Jiří. Visibly Pushdown Automata: From Language Equivalence to Simulation and Bisimulation. \textit{LNCS, Annual Conference on Computer Science Logic (CSL'06)}. Netherlands: Springer-Verlag, 2006, roč.~2006, č.~4207, s.~89-103.
|