Vous êtes ici: UNIL > HEC Inst. > HEC App. > LOGIQUE > recent_news > SSLPS Annual Meeting March 31 and April 1, 2011 - Lausanne
Français | English

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

Sponsored by   and 

On the Posterity of Büchi

(Logic and Automata)



Mikolaj Bojanczyk     (University of Warsaw, Poland)

Thomas Colcombet  (Université Paris VII, France)

Christof Löding          (RWTH Aachen, Germany)

Wolfgang Thomas     (RWTH Aachen, Germany)

Igor Walukiewicz       (Université Bordeaux I, France)



Thursday, March 31

13:15 -->14:45  (Wolfgang Thomas)

     On the Impact and Perspectives of Büchi's Work - Some Personal Impressions
15:00 -->16:30  (Christof Löding)

     Strategy Synthesis for Infinite Games
Slides: here
17:00 -->18:30 (Mikolaj Bojanczyk)

     Extensions of Omega-Regular Languages
Slides : here

Friday, April 1

10:00 -->11:30 ( Igor Walukiewicz)

     MSOL-transfer theorems

11:45 -->13:15 (Thomas Colcombet)

     The Monadic Theory of Order


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.


The aim of this workshop is to bring together some among the best specialists from this new trend of automata theory and discuss the existing results and the ones to come.    Emphasis will be put on the various game-theoretical and new mathematical methods that underlie these new streams of research, as well as on the foreseen applications.



Internef - CH-1015 Lausanne - Suisse - Tél. +41 21 692 33 00 - Fax +41 21 692 33 05