Abstract
Some initial motivations for the Guarded Fragment still seem of interest in carrying its program further. First, we stress the equivalence between two perspectives: (a) satisfiability on standard models for guarded first-order formulas, and (b) satisfiability on general assignment models for arbitrary first-order formulas. In particular, we give a new straightforward reduction from the former notion to the latter. We also show how a perspective shift to general assignment models provides a new look at the fixed-point extension LFP(FO) of first-order logic, making it decidable. Next, we relate guarded syntax to earlier quantifier restriction strategies for achieving effective axiomatizability in second-order logic – pointing at analogies with ‘persistent’ formulas, which are essentially in the Bounded Fragment of many-sorted first-order logic. Finally, we look at some further unexplored directions, including the systematic use of ‘quasi-models’ as a semantics by itself.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Andréka, H., van Benthem, J., and Németi, I., 1998, “Modal languages and bounded fragments of predicate logic,” Journal of Philosophical Logic 27, 217–274.
Andréka, H., Hodkinson, I., and Németi, I., 1999, “Finite algebras of relations are representable on finite sets,” Journal of Symbolic Logic 64, 243–267.
Andréka, H., Madarasz, J., and Németi, I., to appear, “Logics of relativistic space-time,” in M. Aiello, J. van Benthem and I. Pratt (eds.), Handbook of Spatial Reasoning, Kluwer-Springer Academic Publishers, Dordrecht.
Andréka, H. and Németi, I., 2005, private communication.
Feferman, S., 1969, “Persistent and invariant formulas for outer extensions,” Compositio Mathematica 20, 29–52.
Grädel, E., 1999A, “Decision procedures for guarded logics,” in Automated Deduction – Proceedings CADE 16, Lecture Notes in Computer Science 1632, Springer Verlag, Berlin, 31–51.
Grädel, E., 1999B, “On the restraining power of guards,” Journal of Symbolic Logic 64, 1719-1742.
Grädel, E., 1999C, “The decidability of guarded fixed point logic,” in J. Gerbrandy, M. Marx, M. de Rijke, and Y. Venema (eds.), JFAK Essays Dedicated to Johan van Benthem on the Occasion of his 50th Birthday, CD-ROM http://turing.wins.uva.nl/~j50/cdrom/, Amsterdam University Press.
Hoogland, E. and Marx, M., 2002, “Interpolation and definability in guarded fragments,” Studia Logica 70, 373–409.
Hoogland, E., Marx, M., and Otto, M., 1999, “Beth definability for the guarded fragment,” in H. Ganzinger, D. McAllester, and A. Voronkov (eds.), Logic for Programming and Automated Reasoning, LPAR 6, Springer Lecture Notes in AI 1705, 273–285, Springer, Berlin.
Kerdiles, G., 2001, Saying it with Pictures: A Logical Landscape of Conceptual Graphs, Dissertation DS-2001-09, Institute for Logic, Language and Computation, University of Amsterdam.
Marx, M., 2001, “Tolerance logic,” Journal of Logic, Language and Information 10, 353–373.
Marx, M. and Venema, Y., 1997, Multi-Dimensional Modal Logic, Kluwer, Dordrecht.
Montague, R., 1970, “Pragmatics and intensional logic,” Synthese 22, 68–94.
Németi, I., 1985, “Cylindric-relativized set algebras have strong amalgamation,” Journal of Symbolic Logic 50(3), 689–700.
Németi, I., 1995, “Decidability of weakened versions of first-order logic,” in Logic Colloquium 92, CSLI Publications, Stanford, pp. 177–241.
Németi, I., 1996, “Fine-structure analysis of first-order logic,” in M. Marx, M. Masuch, and L. Pólos (eds.), Arrow Logic and Multi-Modal Logic, CSLI Publications, Stanford, 221–247.
ten Cate, B., 2005, Model Theory for Extended Modal Languages, Dissertation, Institute for Logic, Language and Computation, University of Amsterdam.
van Benthem, J., 1983, Modal Logic and Classical Logic, Bibliopolis, Napoli.
van Benthem, J., 1996A, “Complexity of contents versus complexity of wrappings,” in M. Marx, M. Masuch, and L. Pólos (eds.), Arrow Logic and Multimodal Logic, Studies in Logic, Language and Information, CSLI Publications, Stanford and Cambridge University Press, 203–219.
van Benthem, J., 1996B, Exploring Logical Dynamics, CSLI Publications, Stanford.
van Benthem, J., 1997, “Dynamic bits and pieces,” Report LP-97-01, Institute for Logic, Language and Computation, University of Amsterdam.
van Benthem, J., 1999, “The range of modal logic,” Journal of Applied Non-Classical Logics 9(2/3), 407–442.
van Benthem, J., 2001, “Modal logic in two gestalts,” in M. de Rijke, H. Wansing and M. Zakharyashev (eds.), Advances in Modal Logic, Vol. II, Uppsala 1998, CSLI Publications, Stanford, 73–100.
van der Hoek, W. and de Rijke, M., 1993, “Generalized quantifiers and modal logic,” Journal of Logic, Language, and Information 2, 19–50.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
van Benthem, J. Guards, Bounds, and Generalized Semantics. J Logic Lang Inf 14, 263–279 (2005). https://doi.org/10.1007/s10849-005-5786-y
Issue Date:
DOI: https://doi.org/10.1007/s10849-005-5786-y