Simulation of one-counter automata

Prelegent(ci)

Piotr Hofman

Afiliacja

Uniwersytet Warszawski

Termin

29 maja 2013 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Sławek Lasota, Patrick Toetzke and Richard Mayr

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.

---