part 1/ A Tight Lower Bound for Determinization of Transition Labeled Buchi Automata

Prelegent(ci)

Konrad Zdanowski

Afiliacja

Uniwersytet Warszawski

Termin

2 grudnia 2009 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Thomas Colcombet

Seminarium

Seminarium „Teoria automatów”

---

We present a lower bound for the problem of translating a Buchi word automaton into a deterministic Rabin word automaton when both the Buchi and the Rabin conditions label transitions rather than states. This lower bound exactly matches the known upper bound to this problem.

---