![]() |
COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. | ![]() |
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 ProgramsAdd 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. This talk is included in these lists:
Note that ex-directory lists are not shown. |
Other listsClimate week Seminar Microfluidics Cambridge Endangered Languages and Cultures GroupOther talksOncological Imaging: introduction and non-radionuclide techniques & radionuclide techniques Computer vision techniques for measuring deformation A novel aspect of Macrophage biology: learning from the great opportunist HIV-1 Recent Advances in Solid State Batteries and Beyond Li Technologies - Challenges for Fundamental Science Atmospheric Retrieval A cabinet of natural history: the long-lost Paston collection |