Linear Datalog and Bounded Path Duality of Relational Structures

DOI10.2168/LMCS-1(1:5)2005zbMath1125.68408OpenAlexW3104030884WikidataQ113366395 ScholiaQ113366395MaRDI QIDQ5310636

Victor Dalmau

Publication date: 11 October 2007

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2168/lmcs-1(1:5)2005

Mathematics Subject Classification ID

Database theory (68P15) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Logic programming (68N17)

Related Items (16)

A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\) ⋮ Unnamed Item ⋮ The smallest hard trees ⋮ Majority constraints have bounded pathwidth duality ⋮ The complexity of approximately counting stable roommate assignments ⋮ The complexity of approximately counting stable matchings ⋮ On Maltsev Digraphs ⋮ The complexity of the list homomorphism problem for graphs ⋮ On Maltsev digraphs ⋮ CSP duality and trees of bounded pathwidth ⋮ Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs ⋮ Universal algebra and hardness results for constraint satisfaction problems ⋮ Affine systems of equations and counting infinitary logic ⋮ The complexity of satisfiability problems: Refining Schaefer's theorem ⋮ Dualities for Constraint Satisfaction Problems ⋮ Unnamed Item

Uses Software

• Datalog

This page was built for publication: Linear Datalog and Bounded Path Duality of Relational Structures