Complexity of the Guarded Two-Variable Fragment with Counting Quantifiers

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.

20 pages, 3 figures

References in corpus (1)

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

Cited by in corpus (11)

• Complexity of the Two-Variable Fragment with (Binary-Coded) Counting Quantifiers
• Querying the Guarded Fragment
• On the Complexity of the Numerically Definite Syllogistic and Related Fragments
• Data-Complexity of the Two-Variable Fragment with Counting Quantifiers
• Adding Path-Functional Dependencies to the Guarded Two-Variable Fragment with Counting
• Dichotomies in Ontology-Mediated Querying with the Guarded Fragment
• Finite Satisfiability of the Two-Variable Guarded Fragment with Transitive Guards and Related Variants
• Ontology Focusing: Knowledge-enriched Databases on Demand
• Towards a more efficient approach for the satisfiability of two-variable logic
• On two-variable guarded fragment logic with expressive local Presburger constraints
• Finite Model Reasoning in Expressive Fragments of First-Order Logic