University of Cambridge > Talks.cam > Wednesday Seminars - Department of Computer Science and Technology > Church's Problem on the Synthesis of Nonterminating Programs

  Browse A-Z

Log in

Googledetails Microsoftdetails

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

Church's Problem on the Synthesis of Nonterminating Programs

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 Wednesday Seminars - Department of Computer Science and Technology series.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Program verification reading group. ZOOM ID, TBA Bateman Auditorium, Gonville & Caius

Other talks

Together Now: Cooperation and Collaboration in Social Art Practice Title to be confirmed Studying viruses to understand what makes pandemic viruses special and how innate immunity works Seminars in Cancer Title to be confirmed TBC
 

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