BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Model theoretic tools for deciding boundedness of fixed points - M
 artin Otto\, Darmstadt
DTSTART:20071102T140000Z
DTEND:20071102T150000Z
UID:TALK8701@talks.cam.ac.uk
CONTACT:Matthew Parkinson
DESCRIPTION:Boundedness concerns the question whether a given\nmonotone/po
 sitive first-order inductive definition\nconverges to its fixed point with
 in a uniformly bounded\nnumber of steps. This is equivalent to the questio
 n whether the\nfixed point is itself first-order\, by a classical theorem 
 of\nBarwise and Moschovakis.\nThe corresponding decision problem is undeci
 dable for all but\nvery limited fragments of first-order logic. I want to 
 focus on\nthe decidability frontier for monadic fixed points and to discus
 s\nsome old and new results and techniques that suggest to look for a\nmod
 el theoretic divide between decidable and undecidable cases.
LOCATION:Room FW11\, Computer Laboratory\, William Gates Building
END:VEVENT
END:VCALENDAR