×

Inflationary fixed points in modal logic. (English) Zbl 0999.03019

Fribourg, Laurent (ed.), Computer science logic. 15th international workshop, CSL 2001, 10th annual conference of the EACSL, Paris, France, September 10-13, 2001. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2142, 277-291 (2001).
Summary: We consider an extension of modal logic with an operator for constructing inflationary fixed points, just as the modal \(\mu\)-calculus extends basic modal logic with an operator for least fixed points. Least and inflationary fixed point operators have been studied and compared in other contexts, particularly in finite model theory, where it is known that the logics IFP and LFP that result from adding such fixed point operators to first order logic have equal expressive power. As we show, the situation in modal logic is quite different, as the modal iteration calculus (MIC) we introduce has much greater expressive power than the \(\mu\)-calculus. Greater expressive power comes at a cost: the calculus is algorithmically much less manageable.
For the entire collection see [Zbl 0971.00033].

MSC:

03B45 Modal logic (including the logic of norms)
03D15 Complexity of computation (including implicit computational complexity)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDFBibTeX XMLCite
Full Text: Link