On the decision problem for the guarded fragment with transitivity

The guarded fragment with transitive guards, [GF+TG], is an extension of GF in which certain relations 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. This answers the question posed in (Ganzinger et al., 1999). Moreover, we show that the problem is 2EXPTIME-complete. This result is optimal since the satisfiability problem for GF is 2EXPTIME-complete (Gradel, 1999). 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 pr…

On Horn spectra

Abstract A Horn spectrum is a spectrum of a Horn sentence. We show that to solve Asser's problem, and consequently the EXPTIME = ? NEXPTIME question it suffices to consider the class of Horn spectra. We also pose the problem whether or not the generator of every Horn spectrum is a spectrum. We prove that from a negative solution of the generator problem, a negative answer for the EXPTIME = ? NEXPTIME question follows. Some other relations between the generator problem and Asser's problem are given. Finally, the relativized version of the generator problem is formulated and it is shown that it has an affirmative solution for some oracles, and a negative solution for some others.

The fluted fragment revisited

AbstractWe study the fluted fragment, a decidable fragment of first-order logic with an unbounded number of variables, motivated by the work of W. V. Quine. We show that the satisfiability problem for this fragment has nonelementary complexity, thus refuting an earlier published claim by W. C. Purdy that it is in NExpTime. More precisely, we consider ${\cal F}{{\cal L}^m}$, the intersection of the fluted fragment and the m-variable fragment of first-order logic, for all $m \ge 1$. We show that, for $m \ge 2$, this subfragment forces $\left\lfloor {m/2} \right\rfloor$-tuply exponentially large models, and that its satisfiability problem is $\left\lfloor {m/2} \right\rfloor$-NExpTime-hard. We…

On the Finite Satisfiability Problem for the Guarded Fragment with Transitivity

We study the finite satisfiability problem for the guarded fragment with transitivity. We prove that in case of one transitive predicate the problem is decidable and its complexity is the same as the general satisfiability problem, i.e. 2Exptime-complete. We also show that finite models for sentences of GF with more transitive predicate letters used only in guards have essentially different properties than infinite ones.

On the generator problem

On the satisfiability problem for fragments of two-variable logic with one transitive relation

Abstract We study the satisfiability problem for two-variable first-order logic over structures with one transitive relation. We show that the problem is decidable in 2-NExpTime for the fragment consisting of formulas where existential quantifiers are guarded by transitive atoms. As this fragment enjoys neither the finite model property nor the tree model property, to show decidability we introduce a novel model construction technique based on the infinite Ramsey theorem. We also point out why the technique is not sufficient to obtain decidability for the full two-variable logic with one transitive relation; hence, contrary to our previous claim, [FO$^2$ with one transitive relation is deci…

A NOTE ON THE ASYMPTOTIC PROBABILITIES OF EXISTENTIAL SECOND-ORDER MINIMAL GÖDEL SENTENCES WITH EQUALITY

The minimal Gödel class is the class of first-order prenex sentences whose quantifier prefix consists of two universal quantifiers followed by just one existential quantifier. We prove that asymptotic probabilities of existential second-order sentences, whose first-order part is in the minimal Gödel class, form a dense subset of the unit interval.

The guarded fragment with transitive guards

The guarded fragment with transitive guards, (GF+TG), is an extension of the guarded frag- ment of 9rst-order logic, GF, in which certain predicates are required to be transitive, transitive predicate letters appear only in guards of the quanti9ers 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 satis9ability problem for GF is 2EXPTIME-complete (J. Symbolic Logic 64 (1999) 1719-1742). We also show that the satis- 9ability problem for two-variable (GF+TG) is NEXPTIME-hard in contrast to GF with bounded number of variables for which the satis9ability …