University of Cambridge > Talks.cam > Computer Laboratory Wednesday Seminars > Church's Problem on the Synthesis of Nonterminating Programs

Church's Problem on the Synthesis of Nonterminating Programs

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity