David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Symbolic Logic 64 (4):1719-1742 (1999)
Guarded fragments of first-order logic were recently introduced by Andreka, van Benthem and Nemeti; they consist of relational first-order formulae whose quantifiers are appropriately relativized by atoms. These fragments are interesting because they extend in a natural way many propositional modal logics, because they have useful model-theoretic properties and especially because they are decidable classes that avoid the usual syntactic restrictions (on the arity of relation symbols, the quantifier pattern or the number of variables) of almost all other known decidable fragments of first-order logic. Here, we investigate the computational complexity of these fragments. We prove that the satisfiability problems for the guarded fragment (GF) and the loosely guarded fragment (LGF) of first-order logic are complete for deterministic double exponential time. For the subfragments that have only a bounded number of variables or only relation symbols of bounded arity, satisfiability is EXPTIME-complete. We further establish a tree model property for both the guarded fragment and the loosely guarded fragment, and give a proof of the finite model property of the guarded fragment. It is also shown that some natural, modest extensions of the guarded fragments are undecidable
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
Savas Konur (2011). An Event-Based Fragment of First-Order Logic Over Intervals. Journal of Logic, Language and Information 20 (1):49-68.
Ian Hodkinson (2006). Complexity of Monodic Guarded Fragments Over Linear and Real Time. Annals of Pure and Applied Logic 138 (1):94-125.
Martin Otto (2004). Modal and Guarded Characterisation Theorems Over Finite Transition Systems. Annals of Pure and Applied Logic 130 (1-3):173-205.
Wiesław Szwast & Lidia Tendera (2004). The Guarded Fragment with Transitive Guards. Annals of Pure and Applied Logic 128 (1-3):227-276.
Similar books and articles
Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi (1997). On the Decision Problem for Two-Variable First-Order Logic. Bulletin of Symbolic Logic 3 (1):53-69.
Antje Nowack (2005). A Guarded Fragment for Abstract State Machines. Journal of Logic, Language and Information 14 (3):345-368.
Stéphane Demri & Hans De Nivelle (2005). Deciding Regular Grammar Logics with Converse Through First-Order Logic. Journal of Logic, Language and Information 14 (3):289-329.
Roman Kontchakov, Carsten Lutz, Frank Wolter & Michael Zakharyaschev (2004). Temporalising Tableaux. Studia Logica 76 (1):91 - 134.
Ian Hodkinson & Martin Otto (2003). Finite Conformal Hypergraph Covers and Gaifman Cliques in Finite Structures. Bulletin of Symbolic Logic 9 (3):387-405.
Johan van Benthem (2005). Guards, Bounds, and Generalized Semantics. Journal of Logic, Language and Information 14 (3):263-279.
Ian Hodkinson (2002). Loosely Guarded Fragment of First-Order Logic has the Finite Model Property. Studia Logica 70 (2):205 - 240.
Balder ten Cate & Massimo Franceschet (2005). Guarded Fragments with Constants. Journal of Logic, Language and Information 14 (3):281-288.
Balder ten Cate & Massimo Franceschet (2005). Guarded Fragments with Constants. Journal of Logic 14 (3):281-288.
Eva Hoogland & Maarten Marx (2002). Interpolation and Definability in Guarded Fragments. Studia Logica 70 (3):373 - 409.
Added to index2009-01-28
Total downloads10 ( #156,754 of 1,139,979 )
Recent downloads (6 months)1 ( #157,515 of 1,139,979 )
How can I increase my downloads?