Name
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1093/logcom/exv075 | JOURNAL OF LOGIC AND COMPUTATION |
Keywords | Field | DocType |
Satisfiability problem,computational complexity,decidability,guarded fragment,equivalence closure | Discrete mathematics,Combinatorics,Closure operator,Boolean satisfiability problem,Satisfiability,Algorithm,Decidability,Equivalence (measure theory),Predicate (grammar),Mathematics,Binary number,Computational complexity theory | Journal |
Volume | Issue | ISSN |
27 | 4 | 0955-792X |
Citations | PageRank | References |
0 | 0.34 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Emanuel Kieronski | 1 | 114 | 13.85 |
| Ian Pratt-Hartmann | 2 | 347 | 35.43 |
| Lidia Tendera | 3 | 220 | 20.80 |