Beyond Language Equivalence on Visibly Pushdown Automata

Research output: Contribution to journalJournal articleResearchpeer-review

14 Citations (Scopus)

Abstract

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.
Original languageEnglish
JournalLogical Methods in Computer Science
Volume5
Issue number1:2
Pages (from-to)1-22
Number of pages22
ISSN1860-5974
DOIs
Publication statusPublished - 26 Jan 2009

Keywords

  • visibly pushdown automata
  • equivalence checking
  • complexity

Fingerprint

Dive into the research topics of 'Beyond Language Equivalence on Visibly Pushdown Automata'. Together they form a unique fingerprint.

Cite this