joint work with Thomas Colcombet

Speaker(s)

Konrad Zdanowski

Affiliation

Uniwersytet Warszawski

Date

Dec. 2, 2009, 2:15 p.m.

Room

room 5870

Title in Polish

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

Seminar

Seminar Automata Theory

---

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.

---