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

DOI10.1016/J.IC.2009.02.004zbMATH Open1183.68254OpenAlexW2163231487MaRDI QIDQ2389348FDOQ2389348

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

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

Cites Work

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

Cited In (5)

• First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queries
• Reasoning and Query Answering in Description Logics
• Two variable logic with ultimately periodic counting
• Query Answering in Description Logics: The Knots Approach
• Logical separability of labeled data examples under ontologies

This page was built for publication: Data-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 Q2389348)