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