Back to Search
Start Over
Equivalence closure in the two-variable guarded fragment
- 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.
- Subjects :
- Computational complexity theory
Logic
computational complexity
guarded fragment
satisfiability problem
Binary number
Theoretical Computer Science
Combinatorics
Arts and Humanities (miscellaneous)
Computer Science::Logic in Computer Science
Closure operator
Equivalence (formal languages)
Mathematics
Discrete mathematics
decidability
equivalence closure
Satisfiability
Decidability
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
Closure (computer programming)
Hardware and Architecture
TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS
Boolean satisfiability problem
Software
Subjects
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