isAnon => cache

SSLPS Annual Meeting March 31 and April 1, 2011 - Lausanne

Sponsored by   and 

On the Posterity of Büchi

(Logic and Automata)

Speakers:

Mikolaj Bojanczyk     (University of Warsaw, Poland)

Thomas Colcombet  (Université Paris VII, France)

Christof Löding          (RWTH Aachen, Germany)

Wolfgang Thomas     (RWTH Aachen, Germany)

Program

Friday, April 1

Location

Julius-Richard Büchi (1924–1984) was a Swiss logician and a mathematician who received his Dr. sc. nat. in 1950 at the ETH Zürich under the supervision of Paul Bernays.

Almost half a century ago, in 1962, he invented what is now called the Büchi automaton: an extension of a finite state automaton for It accepts an infinite input sequence if and only if there exists a run of the automaton that visits one of the final states infinitely often.

These automata on infinite words are useful for specifying behaviors of non-terminating  systems such as operating systems. In fact their underlying logic is a class of monadic second order logic with a high expressive power, which Büchi proved to be decidable: one of his most remarkable results that paved the way to model-checking techniques.

 Later Rabin extended this result considering tree-automata instead of word-automata. Then gradually game theory came in the way providing new methods of analysis.

In the recent years there has been tremendous efforts devoted to extending Büchi’s results. It culminated with the brilliant works of Mikolaj Bojanczyk  and Thomas Colcombet.