Deciding emptiness of min-automata

Prelegent(ci)

Szymon Toruńczyk

Afiliacja

Uniwersytet Warszawski

Termin

13 maja 2009 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

I will present an algorithm which verifies emptiness of min-automata. This problem is equivalent to the problem of limitedness of Distance Automata and the finite section problem for the semiring of matrices over the (+,min) semiring, both of which were considered by Hashiguchi, Leung and Simon. I will present a proof of correctness based on a proof by Kirsten (which, in turn, originates from Leung). I will also show that the problem is PSpace-complete.

---