On the Complexity of Bisimulation Equivalence for Pushdown Automata
University Freiburg, Germany
We give an overview over several recent results about the complexity
of checking weak and strong bisimulation equivalence on pushdown
automata (PDA) and their subclass BPA. The focus of the talk will be on the
general proof techniques used to achieve these results.
In particular we'll discuss the following results:
1. The undecidability of weak bisimilarity for PDA.
(Shown by Srba in CONCUR 2002).
2. The EXPTIME lower bound for strong bisimilarity on PDA.
(Shown by Kucera and Mayr in MFCS 2002).
3. The complexity of comparing PDA to finite-state systems
(PSPACE-complete for PDA; polynomial for BPA). (Kucera, Mayr)
Place: Information technology, Uppsala University
Time: 15.15-16.00 (+ discussions)
Room 1145 is in building 1, floor 1, room 13
(in the northern part of the building).
Help on how to find ASTEC Seminars.
There will be an extended period for discussions after the seminar.
Speakers are encouraged to give an short (5 min) introduction to the subject at the begining of the talk.
Listeners are excused if they have to leave after 16.00.
Everyone is welcome !
Updated 13-Sep-2002 16:36 by Roland Grönroos
e-mail: info -at- astec.uu.se