Complementation and Determinization of Büchi Automata

Thomas Wilke
Christian-Albrechts-Universität zu Kiel.
Friday, 3 April, 2009 (All day)

Ever since Büchi automata were introduced about 50 years ago, attention has been paid to their complementation and determinization, the interest being twofold: First, complementation and determinization are standard problems in automata theory anyhow. Second, respective constructions are useful in concrete settings, for instance, when it comes to proving the decidability of the monadic theory of the natural numbers with successor and of the monadic theory of the infinite binary tree or when it comes to solving Church's problem. In the talk, I will review the development over the last five decades and point out recent results.