Abstract

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 2E. This result is optimal since the satisfiability problem for GF is 2E-complete 1719–1742). We also show that the satisfiability problem for two-variable [GF+TG] is N-hard in contrast to GF with bounded number of variables for which the satisfiability problem is E-complete