Logic in Computer Science (LICS 2001)

Paper: On the Decision Problem for the Guarded Fragment with Transitivity (at LICS 2001)

Authors: Wieslaw Szwast Lidia Tendera

Abstract

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 [11 ]. Moreover, we show that the problem is 2EXPTIME-complete. This result is optimal since satisfiability problem for GF is 2EXPTIME-complete [12 ]. 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.

BibTeX

  @InProceedings{SzwastTendera-OntheDecisionProble,
    author = 	 {Wieslaw Szwast and Lidia Tendera},
    title = 	 {On the Decision Problem for the Guarded Fragment with Transitivity},
    booktitle =  {Proceedings of the Sixteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2001},
    year =	 2001,
    editor =	 {Joseph Halpern},
    month =	 {June}, 
    pages =      {147--156},
    location =   {Boston, MA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }