Visibly Pushdown Automata: From Language Equivalence to Simulation and Bisimulation

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

14 Citationer (Scopus)

Abstract

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.
OriginalsprogEngelsk
TitelComputer Science Logic : Proceedings of 20th International Workshop, CSL 2006, 15th Annual Conference of the EACSL, Szeged, Hungary, September 25-29, 2006
Antal sider15
ForlagIEEE Computer Society Press
Publikationsdato2006
Sider89-103
ISBN (Trykt)9783540454588
DOI
StatusUdgivet - 2006
BegivenhedAnnual Conference on Computer Science Logic (CSL'06) - Szeged, Ungarn
Varighed: 25 sep. 200629 sep. 2006
Konferencens nummer: 15

Konference

KonferenceAnnual Conference on Computer Science Logic (CSL'06)
Nummer15
Land/OmrådeUngarn
BySzeged
Periode25/09/200629/09/2006
NavnLecture Notes in Computer Science
Nummer4207
ISSN0302-9743

Fingeraftryk

Dyk ned i forskningsemnerne om 'Visibly Pushdown Automata: From Language Equivalence to Simulation and Bisimulation'. Sammen danner de et unikt fingeraftryk.

Citationsformater