BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Church's Problem on the Synthesis of Nonterminating Programs - Wol
 fgang Thomas\, RWTH Aachen University
DTSTART:20070418T131500Z
DTEND:20070418T141500Z
UID:TALK6894@talks.cam.ac.uk
CONTACT:Timothy G. Griffin
DESCRIPTION:Church's Problem (1960) asks for the construction of a finite-
 state\nprocedure that transforms any input sequence X letter by letter\nin
 to an output sequence Y such that the pair (X\,Y) satisfies\na given speci
 fication. Even after the solution by Buechi and Landweber\nin 1969 (for sp
 ecifications in monadic second-order logic)\, the\nproblem has stimulated 
 research in automata theory for decades\,\nin recent years mainly in the a
 lgorithmic study of infinite\ngames. In the talk we present a modern solut
 ion which is fairly\nself-contained and which provides additional insight 
 into the\nmemory structure of the synthesized finite-state transducers. We
 \nclose with remarks on perspectives in algorithmic program synthesis.\n
LOCATION:Lecture Theatre 1\, Computer Laboratory
END:VEVENT
END:VCALENDAR