University of Cambridge > > Logic and Semantics Seminar (Computer Laboratory) > Model theoretic tools for deciding boundedness of fixed points

Model theoretic tools for deciding boundedness of fixed points

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2023, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity