Complexity of the Two-Variable Fragment with (Binary-Coded) Counting Quantifiers

Abstract

We show that the satisfiability and finite satisfiability problems for the two-variable fragment of first-order logic with counting quantifiers are both in NEXPTIME, even when counting quantifiers are coded succinctly.

24 pages, 1 pstex_t figure

References in corpus (1)

• Complexity of the Guarded Two-Variable Fragment with Counting Quantifiers

Cited by in corpus (33)

• Querying the Guarded Fragment
• Nominals, Inverses, Counting, and Conjunctive Queries or: Why Infinity is your Friend!
• Complexity of the Guarded Two-Variable Fragment with Counting Quantifiers
• The Complexity of Circumscription in DLs
• On the Complexity of the Numerically Definite Syllogistic and Related Fragments
• Data-Complexity of the Two-Variable Fragment with Counting Quantifiers
• Type-elimination-based reasoning for the description logic SHIQbs using decision diagrams and disjunctive datalog
• Two-variable Logic with Counting and a Linear Order
• Adding Path-Functional Dependencies to the Guarded Two-Variable Fragment with Counting
• Satisfiability and Containment of Recursive SHACL
• A system of relational syllogistic incorporating full Boolean reasoning
• Interleaving Logic and Counting
• Computational Aspects of Dependence Logic
• Ontology Focusing: Knowledge-enriched Databases on Demand
• Finite Satisfiability of the Two-Variable Guarded Fragment with Transitive Guards and Related Variants
• A Double Team Semantics for Generalized Quantifiers
• KF metamodel formalization
• Algebraic classifications for fragments of first-order logic and beyond
• Worst-case Optimal Query Answering for Greedy Sets of Existential Rules and Their Subclasses
• Completing the Picture: Complexity of Graded Modal Logics with Converse
• On the uniform one-dimensional fragment
• Complexity and Expressivity of Uniform One-Dimensional Fragment with Equality
• Satisfiability of Modal Inclusion Logic: Lax and Strict Semantics
• Towards a more efficient approach for the satisfiability of two-variable logic
• On two-variable guarded fragment logic with expressive local Presburger constraints
• Hybrid Modal Operators for Definite Descriptions
• Managing Change in Graph-structured Data Using Description Logics (long version with appendix)
• Complexity of two-variable Dependence Logic and IF-Logic
• SHACL Satisfiability and Containment (Extended Paper)
• Decidable fragments of first-order modal logics with counting quantifiers over varying domains
• Shape and Content: Incorporating Domain Knowledge into Shape Analysis
• Extending Two-Variable Logic on Trees
• Finite Model Reasoning in Expressive Fragments of First-Order Logic