Simulation of one-counter automata
- Prelegent(ci)
- Piotr Hofman
- Afiliacja
- Uniwersytet Warszawski
- Termin
- 29 maja 2013 14:15
- Pokój
- p. 5870
- Seminarium
- Seminarium „Teoria automatów”
The talk will be devoted to the following decision problem: for two
given one-counter automata, find the winner of Simulation Game between
these automata. We will discuss variants of the problems, influencing
its decidability and complexity status. As a technical core a new proof
method will be sketched, that allows us to prove PSPACE-completeness of
the problem.