Guarded quantification in least fixed point logic

Journal of Logic, Language and Information 13 (1):61-110 (2004)
  Copy   BIBTEX


We develop a variant of Least Fixed Point logic based on First Orderlogic with a relaxed version of guarded quantification. We develop aGame Theoretic Semantics of this logic, and find that under reasonableconditions, guarding quantification does not reduce the expressibilityof Least Fixed Point logic. But we also find that the guarded version ofa least fixed point algorithm may have a greater time complexity thanthe unguarded version, by a linear factor.



    Upload a copy of this work     Papers currently archived: 86,592

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

The expressive power of fixed-point logic with counting.Martin Otto - 1996 - Journal of Symbolic Logic 61 (1):147-176.
Guards, Bounds, and generalized semantics.Johan van Benthem - 2005 - Journal of Logic, Language and Information 14 (3):263-279.
Fixed point logics.Anuj Dawar & Yuri Gurevich - 2002 - Bulletin of Symbolic Logic 8 (1):65-88.
The semijoin algebra and the guarded fragment.Dirk Leinders, Maarten Marx, Jerzy Tyszkiewicz & Jan Van den Bussche - 2005 - Journal of Logic, Language and Information 14 (3):331-343.
Comparing fixed-point and revision theories of truth.Philip Kremer - 2009 - Journal of Philosophical Logic 38 (4):363-403.
Yet another hierarchy theorem.Max Kubierschky - 2000 - Journal of Symbolic Logic 65 (2):627-640.


Added to PP

28 (#468,932)

6 months
3 (#343,082)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

[Omnibus Review].Yiannis N. Moschovakis - 1968 - Journal of Symbolic Logic 33 (3):471-472.
Query.[author unknown] - 1989 - Newsletter of the Society for the Advancement of American Philosophy 17 (52):9-9.

View all 18 references / Add more references