Equivalence closure in the two-variable guarded fragment
Copyright policy )Equivalence closure in the two-variable guarded fragment
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.
- University of Wrocław Poland
- University of Manchester United Kingdom
- University of Manchester United Kingdom
- University of Opole Poland
- Polish Academy of Sciences Poland
satisfiability problem,, computational complexity, computational complexity,, guarded fragment, satisfiability problem, decidability, equivalence closure
satisfiability problem,, computational complexity, computational complexity,, guarded fragment, satisfiability problem, decidability, equivalence closure
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!