Informace o publikaci

Visibly Pushdown Automata: From Language Equivalence to Simulation and Bisimulation

Logo poskytovatele
Název česky Viditelne Zasobnikove Automaty: Od Jazykove Ekvivalence k Simulaci a Bisimulaci
Autoři

SRBA Jiří

Rok publikování 2006
Druh Článek v odborném periodiku
Časopis / Zdroj LNCS, Annual Conference on Computer Science Logic (CSL'06)
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
Obor Informatika
Klíčová slova visibly pushdown automata; bisimilarity; decidability
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info