The complexity of reverse engineering problems for conjunctive queries

DOI10.4230/LIPICS.ICDT.2017.7MaRDI QIDQ3174895zbMATH OpenFDO

Authors Pablo Barceló, Miguel Romero

Publication date 18 July 2018

Full work available at URL https://arxiv.org/abs/1606.01206

zbMATH Keywords

treewidthconjunctive queriesdefinabilityreverse engineeringcomplexity of pebble gamesquery by example

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Database theory (68P15)

Recommendations

• The Complexity of Conjunctive Query Answering in Expressive Description Logics
• A more general theory of static approximations for conjunctive queries
• A trichotomy in the complexity of counting answers to conjunctive queries
• When is the evaluation of conjunctive queries tractable?
• A more general theory of static approximations for conjunctive queries

Cited in

(7)

• Conjunctive queries: unique characterizations and exact learnability
• Learning concepts definable in first-order logic with counting
• A logic-based framework for characterizing nexus of similarity within knowledge bases
• The parameterized complexity of learning monadic second-order logic
• The complexity of acyclic conjunctive queries
• Regularizing conjunctive features for classification
• Logical separability of labeled data examples under ontologies

This page was built for publication: The complexity of reverse engineering problems for conjunctive queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3174895)