Bounds in ontology-based data access via circuit complexity

DOI10.1007/s00224-016-9707-zzbMath1378.68038OpenAlexW2522992825MaRDI QIDQ2411040

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Towards more expressive ontology languages: the query answering problem
• Data exchange: semantics and query answering
• Boolean function complexity. Advances and frontiers.
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• The monotone circuit complexity of Boolean functions
• Monotone separation of logarithmic space from logarithmic depth
• On datalog vs polynomial time
• The price of query rewriting in ontology-based data access
• Tractable reasoning and efficient query answering in description logics: The DL-Lite family
• Exponential Lower Bounds and Separation for Query Rewriting
• Circuit Complexity Meets Ontology-Based Data Access
• Parity, circuits, and the polynomial-time hierarchy
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• The DL-Lite Family and Relations
• Nondeterministic Space is Closed under Complementation
• Ontology-Mediated Queries
• Tree-like Queries in OWL 2 QL: Succinctness and Complexity Results
• Linking Data to Ontologies
• Elements of Information Theory

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