Deciding emptiness of min-automata

Speaker(s)

Szymon Toruńczyk

Affiliation

Uniwersytet Warszawski

Date

May 13, 2009, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---