Search

The fluted fragment is a fragment of first-order logic (without equality) in which, roughly speaking, the order of quantification of variables coincides with the order in which those variables appear as arguments of predicates. It is known that this fragment has the finite model property. We consider extensions of the fluted fragment with various numbers of transitive relations, as well as the equality predicate. In the presence of one transitive relation (together with equality), the finite model property is lost; nevertheless, we show that the satisfiability and finite satisfiability problems for this extension remain decidable. We also show that the corresponding problems in the presence of two transitive relations (with equality) or three transitive relations (without equality) are undecidable, even for the two-variable sub-fragment. [ABSTRACT FROM AUTHOR]

The guarded fragment with transitive guards, [GF+TG], is an extension of the guarded fragment of first-order logic, GF, in which certain predicates are required to be transitive, transitive predicate letters appear only in guards of the quantifiers and the equality symbol may appear everywhere. We prove that the decision problem for [GF+TG] is decidable. Moreover, we show that the problem is in 2EXPTIME. This result is optimal since the satisfiability problem for GF is 2EXPTIME-complete (J. Symbolic Logic 64 (1999) 1719–1742). We also show that the satisfiability problem for two-variable [GF+TG] is NEXPTIME-hard in contrast to GF with bounded number of variables for which the satisfiability problem is EXPTIME-complete. [Copyright &y& Elsevier]

Abstract: We analyse the complexity of finite model reasoning in the description logic , i.e., augmented with qualifying number restrictions, inverse roles, and general TBoxes. It turns out that all relevant reasoning tasks such as concept satisfiability and ABox consistency are ExpTime-complete, regardless of whether the numbers in number restrictions are coded unarily or binarily. Thus, finite model reasoning with is not harder than standard reasoning with . [Copyright &y& Elsevier]

Let C[SUBp,SUP2] denote the class of first-order sentences with two variables and with additional quantifiers "there exists exactly (at most, at least) i" for i ≤p, and let C[SUP2] be the union of C[SUBp,SUP2] taken over all integers p. We prove that the satisfiability problem for C[SUP2] 1 sentences is NEXPTIME-complete. This strengthens the results by [E. Grädel, Ph. Kolaitis, and M. Vardi, Bull. Symbolic Logic, 3 (1997), pp. 53-69], who showed that the satisfiability problem for the first-order two-variable logic L[SUP2] is NEXPTIME-complete and by [E. Grädel, M. Otto, and E. Rosen, 12th Annual IEEE Symposium on Logic in Computer Science, 1997, pp. 306-317], who proved the decidability of C[SUP2]. Our result easily implies that the satisfiability problem for C[SUP2] is in nondeterministic, doubly exponential time. It is interesting that C[SUP2] 1 is in NEXPTIME in spite of the fact that there are sentences whose minimal (and only) models are of doubly exponential size. It is worth noticing that by a recent result of [E. Grädel, M. Otto, and E. Rosen, Proceedings of 14th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Comput. Sci. 1200, Springer-Verlag, Berlin, 1997], extensions of two-variable logic L[SUP2] by a weak access to cardinalities through the Härtig (or equicardinality) quantifier is undecidable. [ABSTRACT FROM AUTHOR]

We consider the satisfiability and finite satisfiability problems for extensions of the two-variable fragment of first-order logic in which an equivalence closure operator can be applied to a fixed number of binary predicates. We show that the satisfiability problem for two-variable, first-order logic with equivalence closure applied to two binary predicates is in 2-NEXPTIME, and we obtain a matching lower bound by showing that the satisfiability problem for two-variable first-order logic in the presence of two equivalence relations is 2-NEXPTIME-hard. The logics in question lack the finite model property; however, we show that the same complexity bounds hold for the corresponding finite satisfiability problems. We further show that the satisfiability (= finite satisfiability) problem for the two-variable fragment of first-order logic with equivalence closure applied to a single binary predicate is NEXPTIME complete. [ABSTRACT FROM AUTHOR]