We prove ExpTime-membership of the satisfiability problem for loosely ∀-guarded first-order formulas with a bounded number of variables and an unbounded number of constants. Guarded fragments with constants are interesting by themselves and because of their connection to hybrid logic.

The guarded fragment (GF) was introduced by Andréka, van Benthem and Németi as a fragment of first order logic which combines a great expressive power with nice, modal behavior. It consists of relational first order formulas whose quantifiers are relativized by atoms in a certain way. Slightly generalizing the admissible relativizations yields the packed fragment (PF). In this paper we investigate interpolation and definability in these fragments. We first show that the interpolation property of first order logic fails in restriction (...) to GF and PF. However, each of these fragments turns out to have an alternative interpolation property that closely resembles the interpolation property usually studied in modal logic. These results are strong enough to entail the Beth definability property for GF and PF. Even better, every guarded or packed finite variable fragment has the Beth property. For interpolation, we characterize exactly which finite variable fragments of GF and PF enjoy this property. (shrink)

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. (shrink)

This book offers a comprehensive treatment of the classical decision problem of mathematical logic and of the role of the classical decision problem in modern computer science. The text presents a revealing analysis of the natural order of decidable and undecidable cases and includes a number of simple proofs and exercises.

This paper is about the good side of modal logic, the bad side of modal logic, and how hybrid logic takes the good and fixes the bad.In essence, modal logic is a simple formalism for working with relational structures . But modal logic has no mechanism for referring to or reasoning about the individual nodes in such structures, and this lessens its effectiveness as a representation formalism. In their simplest form, hybrid logics are upgraded modal logics in which reference to (...) individual nodes is possible.But hybrid logic is a rather unusual modal upgrade. It pushes one simple idea as far as it will go: represent all information as formulas. This turns out to be the key needed to draw together a surprisingly diverse range of work . Moreover, it displays a number of knowledge representation issues in a new light, notably the importance of sorting. (shrink)

We expand first order models with a tolerance relation on thedomain. Intuitively, two elements stand in this relation if they arecognitively close for the agent who holds the model. This simplenotion turns out to be very powerful. It leads to a semanticcharacterization of the guarded fragment of Andréka, van Benthemand Németi, and highlights the strong analogies between modallogic and this fragment. Viewing the resulting logic – tolerance logic– dynamically it is a resource-conscious information processingalternative to classical first order logic. The (...) differences areindicated by several examples. (shrink)

The guarded fragment (GF) was introduced by Andréka, van Benthem and Németi as a fragment of first order logic which combines a great expressive power with nice, modal behavior. It consists of relational first order formulas whose quantifiers are relativized by atoms in a certain way. Slightly generalizing the admissible relativizations yields the packed fragment (PF). In this paper we investigate interpolation and definability in these fragments. We first show that the interpolation property of first order logic fails in restriction (...) to GF and PF. However, each of these fragments turns out to have an alternative interpolation property that closely resembles the interpolation property usually studied in modal logic. These results are strong enough to entail the Beth definability property for GF and PF. Even better, every guarded or packed finite variable fragment has the Beth property. For interpolation, we characterize exactly which finite variable fragments of GF and PF enjoy this property. (shrink)

Several extensions of the basic modal language are characterized in terms of interpolation. Our main results are of the following form: Language ℒ' is the least expressive extension of ℒ with interpolation. For instance, let ℳ be the extension of the basic modal language with a difference operator [7]. First-order logic is the least expressive extension of ℳ with interpolation. These characterizations are subsequently used to derive new results about hybrid logic, relation algebra and the guarded fragment.

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 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 and the loosely guarded fragment 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. (shrink)