Lics

IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Sixteenth Annual IEEE Symposium on

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 Symposium on Logic in Computer Science (LICS 2001)},
    year =	 {2001},
    month =	 {June}, 
    pages =      {147--156},
    location =   {Boston, MA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }
   

Last modified: 2018-06-2121:59
Andrzej Murawski