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

DOI10.1016/J.IC.2009.02.004MaRDI QIDQ2389348zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• The two-variable fragment with counting and equivalence
• Complexity Results for First-Order Two-Variable Logic with Counting
• Two-variable logic with counting and a linear order
• The two-variable fragment with counting revisited
• On the Decision Problem for Two-Variable First-Order Logic

Cites work

• scientific article; zbMATH DE number 965572 (Why is no real title available?)
• Complexity Results for First-Order Two-Variable Logic with Counting
• Complexity of the Guarded Two-variable Fragment with Counting Quantifiers
• Complexity of the two-variable fragment with counting quantifiers
• Conjunctive query answering for the description logic SHIQ
• Data complexity of query answering in expressive description logics via tableaux
• Integer Programming with a Fixed Number of Variables
• Logics in Artificial Intelligence
• On logics with two variables
• Reasoning in description logics by a reduction to disjunctive datalog
• STACS 2005

Cited in

(7)

• Logical separability of labeled data examples under ontologies
• Reasoning and query answering in description logics
• Two variable logic with ultimately periodic counting
• First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queries
• On the complexity of the Bernays-Schönfinkel class with Datalog
• Query Answering in Description Logics: The Knots Approach
• Weighted first-order model counting in the two-variable fragment with counting quantifiers

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)