LSV Seminar
The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.
The seminar is open to public and does not require any form of registration.
Past Seminars
Equivalence checking of stack-based infinite-state systems
- Date
- Tuesday, March 11 2014 at 11:00AM
- Place
- Salle de Conférence (Pavillon des Jardins)
- Speaker
- Stefan Göller (University of Bremen)
I will give a survey of some results concerning the computational complexity of language equivalence and bisimulation equivalence of stack-based infinite-state systems like higher-order pushdown automata, pushdown automata and deterministic one-counter automata.
In particular I will try to convey the proof ideas to the following results: (i) bisimilarity of order-two pushdown automata is undecidable, (ii) bisimilarity of pushdown automata is non-elementary and (iii) equivalence of deterministic one-counter automata is NL-complete.
If there is sufficient time left I will mention some concrete problems that I think are worth investigating for possibly obtaining a better understanding of equivalence checking of stack-based infinite-state systems.