Model theoretic tools for deciding boundedness of fixed points

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

• Martin Otto, Darmstadt
• Friday 02 November 2007, 14:00-15:00
• Room FW11, Computer Laboratory, William Gates Building.

If you have a question about this talk, please contact Matthew Parkinson.

Boundedness concerns the question whether a given monotone/positive first-order inductive definition converges to its fixed point within a uniformly bounded number of steps. This is equivalent to the question whether the fixed point is itself first-order, by a classical theorem of Barwise and Moschovakis. The corresponding decision problem is undecidable for all but very limited fragments of first-order logic. I want to focus on the decidability frontier for monadic fixed points and to discuss some old and new results and techniques that suggest to look for a model theoretic divide between decidable and undecidable cases.

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Computer Laboratory talks
• Computing and Mathematics
• Logic and Semantics Seminar (Computer Laboratory)
• Room FW11, Computer Laboratory, William Gates Building
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.