Back to Search Start Over

Equivalence closure in the two-variable guarded fragment

Authors :
Ian Pratt-Hartmann
Lidia Tendera
Emanuel Kieronski
Source :
Kieronski, E, Pratt-Hartmann, I & Tendera, L 2015, ' Equivalence closure in the two-variable guarded fragment ', Journal of Logic and Computation, vol. 27, no. 4, pp. 999-1021 . https://doi.org/10.1093/logcom/exv075
Publication Year :
2015
Publisher :
Oxford University Press (OUP), 2015.

Abstract

We consider the satisfiability and finite satisfiability problems for the extension of the two-variable guarded fragment in which an equivalence closure operator can be applied to two distinguished binary predicates. We show that the satisfiability and finite satisfiability problems for this logic are 2-ExpTime-complete. This contrasts with an earlier result that the corresponding problems for the full two-variable logic with equivalence closures of two binary predicates are 2-NExpTime-complete.

Details

ISSN :
1465363X and 0955792X
Database :
OpenAIRE
Journal :
Journal of Logic and Computation
Accession number :
edsair.doi.dedup.....a4277928b0832ce3efeffc874804cf14
Full Text :
https://doi.org/10.1093/logcom/exv075