Linear Datalog and Bounded Path Duality of Relational Structures

DOI10.2168/LMCS-1(1:5)2005MaRDI QIDQ5310636zbMATH OpenOpenAlexWikidataFDO

Authors Víctor 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

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

Recommendations

• scientific article; zbMATH DE number 2086640
• On constraint satisfaction problems below P
• On constraint satisfaction problems below P
• CSP duality and trees of bounded pathwidth
• Majority constraints have bounded pathwidth duality

Cited in

(30)

• 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
• Datalog and constraint satisfaction with infinite templates
• A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\)
• On Maltsev digraphs
• Majority constraints have bounded pathwidth duality
• On constraint satisfaction problems below P
• Caterpillar dualities and regular languages
• On constraint satisfaction problems below P
• Near unanimity constraints have bounded pathwidth duality
• On Maltsev digraphs
• The complexity of approximately counting stable roommate assignments
• The complexity of approximately counting stable matchings
• \(n\)-permutability and linear Datalog implies symmetric Datalog
• scientific article; zbMATH DE number 2086640 (Why is no real title available?)
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Robust algorithms with polynomial loss for near-unanimity CSPs
• Dualities for Constraint Satisfaction Problems
• The dual of a logical linear programme
• The smallest hard trees
• The pebble-relation comonad in finite model theory
• The pebble-relation comonad in finite model theory
• Linear arboreal categories
• The complexity of the list homomorphism problem for graphs
• Maximal digraphs with respect to primitive positive constructability
• Symmetric linear arc monadic Datalog and gadget reductions
• Symmetric linear arc monadic Datalog and gadget reductions
• Homomorphism indistinguishability and game comonads for restricted conjunction and requantification
• CSP duality and trees of bounded pathwidth

Describes a project that uses

Uses Software

• Datalog

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

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