Church's Problem on the Synthesis of Nonterminating Programs

Add to your list(s) Download to your calendar using vCal

• Wolfgang Thomas, RWTH Aachen University
• Wednesday 18 April 2007, 14:15-15:15
• Lecture Theatre 1, Computer Laboratory.

If you have a question about this talk, please contact Timothy G. Griffin.

Host: Anuj Dawar. NOTE: This talk is OUT-OF-TERM

Church’s Problem (1960) asks for the construction of a finite-state procedure that transforms any input sequence X letter by letter into an output sequence Y such that the pair (X,Y) satisfies a given specification. Even after the solution by Buechi and Landweber in 1969 (for specifications in monadic second-order logic), the problem has stimulated research in automata theory for decades, in recent years mainly in the algorithmic study of infinite games. In the talk we present a modern solution which is fairly self-contained and which provides additional insight into the memory structure of the synthesized finite-state transducers. We close with remarks on perspectives in algorithmic program synthesis.

This talk is part of the Computer Laboratory Wednesday Seminars series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Chris Davis' list
• Computer Laboratory Wednesday Seminars
• Computer Laboratory talks
• Graduate-Seminars
• Guy Emerson's list
• Interested Talks
• Lecture Theatre 1, Computer Laboratory
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• computer science
• se393's list

Note that ex-directory lists are not shown.