Bounds in ontology-based data access via circuit complexity

DOI10.1007/S00224-016-9707-ZMaRDI QIDQ2411040zbMATH OpenOpenAlexFDO

Authors Vladimir V. Podolskii

Publication date 20 October 2017

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-016-9707-z

zbMATH Keywords

Boolean circuitsontology-based data access

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15)

Recommendations

• Circuit complexity meets ontology-based data access
• Ontology-based data access: a study through disjunctive Datalog, CSP, and MMSNP
• Ontology-mediated queries. Combined complexity and succinctness of rewritings via circuit complexity
• The price of query rewriting in ontology-based data access
• Query and predicate emptiness in ontology-based data access

Cites work

• scientific article; zbMATH DE number 4008289 (Why is no real title available?)
• scientific article; zbMATH DE number 4087055 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• Boolean function complexity. Advances and frontiers.
• Circuit complexity meets ontology-based data access
• Data exchange: semantics and query answering
• Elements of Information Theory
• Exponential lower bounds and separation for query rewriting
• Linking Data to Ontologies
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Monotone separation of logarithmic space from logarithmic depth
• Nondeterministic Space is Closed under Complementation
• On datalog vs polynomial time
• Ontology-mediated queries. Combined complexity and succinctness of rewritings via circuit complexity
• Parity, circuits, and the polynomial-time hierarchy
• The DL-Lite Family and Relations
• The monotone circuit complexity of Boolean functions
• The price of query rewriting in ontology-based data access
• Towards more expressive ontology languages: the query answering problem
• Tractable reasoning and efficient query answering in description logics: The DL-Lite family
• Tree-like queries in OWL 2 QL: succinctness and complexity results
• \(\Sigma_ 1^ 1\)-formulae on finite structures

Cited in

(1)

• Circuit complexity meets ontology-based data access

This page was built for publication: Bounds in ontology-based data access via circuit complexity

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