Complexity of the Guarded Two-variable Fragment with Counting Quantifiers

DOI10.1093/LOGCOM/EXL034MaRDI QIDQ3437261zbMATH OpenOpenAlexFDO

Authors Ian Pratt-Hartmann

Publication date 14 May 2007

Published in Journal Of Logic And Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0601112

zbMATH Keywords

guarded fragmentcounting quantifierstwo-variable fragmentfinite satisfiability problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic with extra quantifiers and operators (03C80) Subsystems of classical logic (including intuitionistic logic) (03B20) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)

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

(9)

• Data-complexity of the two-variable fragment with counting quantifiers
• The two-variable fragment with counting and equivalence
• Two variable logic with ultimately periodic counting
• Saturation-based Boolean conjunctive query answering and rewriting for the guarded quantification fragments
• One-variable logic meets Presburger arithmetic
• On two-variable guarded fragment logic with expressive local Presburger constraints
• Equivalence closure in the two-variable guarded fragment
• Completing the Picture: Complexity of Graded Modal Logics with Converse
• Exploiting forwardness: satisfiability and query-entailment in forward guarded fragment

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)