Complexity of the Guarded Two-variable Fragment with Counting Quantifiers

DOI10.1093/logcom/exl034zbMath1118.03006arXivcs/0601112OpenAlexW1993151238MaRDI QIDQ3437261

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) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Logic with extra quantifiers and operators (03C80) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items (6)

The two‐variable fragment with counting and equivalence ⋮ Data-complexity of the two-variable fragment with counting quantifiers ⋮ Completing the Picture: Complexity of Graded Modal Logics with Converse ⋮ Saturation-based Boolean conjunctive query answering and rewriting for the guarded quantification fragments ⋮ One-variable logic meets Presburger arithmetic ⋮ 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