Data-complexity of the two-variable fragment with counting quantifiers

DOI10.1016/j.ic.2009.02.004zbMath1183.68254OpenAlexW2163231487MaRDI QIDQ2389348

Ian Pratt-Hartmann

Publication date: 15 July 2009

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2009.02.004

zbMATH Keywords

query answeringdata-complexitytwo-variable fragment with counting

Mathematics Subject Classification ID

Database theory (68P15) Data structures (68P05)

Related Items (4)

Reasoning and Query Answering in Description Logics ⋮ Query Answering in Description Logics: The Knots Approach ⋮ Logical separability of labeled data examples under ontologies ⋮ First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queries

Cites Work

• Unnamed Item
• Unnamed Item
• Data complexity of query answering in expressive description logics via tableaux
• On logics with two variables
• Reasoning in description logics by a reduction to disjunctive datalog
• Complexity of the two-variable fragment with counting quantifiers
• Integer Programming with a Fixed Number of Variables
• Complexity of the Guarded Two-variable Fragment with Counting Quantifiers
• Complexity Results for First-Order Two-Variable Logic with Counting
• Logics in Artificial Intelligence
• STACS 2005

This page was built for publication: Data-complexity of the two-variable fragment with counting quantifiers