Complexity of the two-variable fragment with counting quantifiers

DOI10.1007/S10849-005-5791-1MaRDI QIDQ2567347zbMATH OpenOpenAlexFDO

Authors Ian Pratt-Hartmann

Publication date 4 October 2005

Published in Journal of Logic, Language and Information (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10849-005-5791-1

zbMATH Keywords

complexitycounting quantifierssatisfiabilitytwo-variable fragment of first-order logic

Mathematics Subject Classification ID

Subsystems of classical logic (including intuitionistic logic) (03B20) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)

Cites work

• Complexity Results for First-Order Two-Variable Logic with Counting
• On logics with two variables
• On the complexity of integer programming

Cited in

(33)

• A system of relational syllogistic incorporating full Boolean reasoning
• Data-complexity of the two-variable fragment with counting quantifiers
• Expressive probabilistic description logics
• Combining answer set programming with description logics for the semantic web
• Modal inclusion logic: being lax is simpler than being strict
• Graphs identified by logics with counting
• A double team semantics for generalized quantifiers
• Quantitative logic reasoning
• The two-variable fragment with counting and equivalence
• Cheap Boolean Role Constructors for Description Logics
• THE COMPLEXITY OF SATISFIABILITY FOR FRAGMENTS OF CTL AND CTL⋆
• Combining theories with shared set operations
• On fixed-point logic with counting
• Complexity of two-variable dependence logic and IF-logic
• Complexity Results for First-Order Two-Variable Logic with Counting
• Expressivity and Complexity of Dependence Logic
• Regular graphs and the spectra of two-variable logic with counting
• On the decidability of elementary modal logics
• Two-variable logic with counting and trees
• On the Computational Complexity of the Numerically Definite Syllogistic and Related Logics
• A description logic based situation calculus
• Completing the Picture: Complexity of Graded Modal Logics with Converse
• INTERLEAVING LOGIC AND COUNTING
• Hybrid modal operators for definite descriptions
• Datalog rewritability and data complexity of \(\mathcal{ALCHOIQ}\) with closed predicates
• Two variable logic with ultimately periodic counting
• On two-variable guarded fragment logic with expressive local Presburger constraints
• Modal syllogistic
• Two variable logic with ultimately periodic counting
• On the complexity of convex and reverse convex prequadratic constraints
• Fluted logic with counting
• Deciding expressive description logics in the framework of resolution
• A resolution-based decision procedure for \({\mathcal{SHOIQ}}\).

This page was built for publication: Complexity of the 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 Q2567347)