| 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, vol. 2006, No 4207, p. 89-103. |
Other formats:
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, vol.~2006, No~4207, p.~89-103.
|
