Complexity of the Guarded Two-variable Fragment with Counting Quantifiers
From MaRDI portal
Subsystems of classical logic (including intuitionistic logic) (03B20) Decidability of theories and sets of sentences (03B25) Logic with extra quantifiers and operators (03C80) Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)
Abstract: We show that the finite satisfiability problem for the guarded two-variable fragment with counting quantifiers is in EXPTIME. The method employed also yields a simple proof of a result recently obtained by Y. Kazakov, that the satisfiability problem for the guarded two-variable fragment with counting quantifiers is in EXPTIME.
Cited in
(12)- One-variable logic meets Presburger arithmetic
- Exploiting forwardness: satisfiability and query-entailment in forward guarded fragment
- Data-complexity of the two-variable fragment with counting quantifiers
- Equivalence closure in the two-variable guarded fragment
- The two-variable fragment with counting and equivalence
- Completing the Picture: Complexity of Graded Modal Logics with Converse
- Saturation-based Boolean conjunctive query answering and rewriting for the guarded quantification fragments
- Two variable logic with ultimately periodic counting
- On two-variable guarded fragment logic with expressive local Presburger constraints
- Two variable logic with ultimately periodic counting
- Are targeted messages more effective?
- About the expressive power and complexity of order-invariance with two variables
This page was built for publication: Complexity of the Guarded Two-variable Fragment with Counting Quantifiers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3437261)
