6533b7d1fe1ef96bd125cd15
RESEARCH PRODUCT
On the decision problem for the guarded fragment with transitivity
Lidia TenderaWiesław Szwastsubject
CombinatoricsDiscrete mathematicsTransitive relationComputational complexity theoryComputabilityBounded functionPredicate (mathematical logic)Decision problemBoolean satisfiability problemDecidabilityMathematicsdescription
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 problem is EXPTIME-complete.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2002-11-13 |