# 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.