n-permutability and linear Datalog implies symmetric Datalog

DOI10.23638/LMCS-14(2:3)2018MaRDI QIDQ4643956zbMATH OpenFDO

Authors Alexandr Kazda

Publication date 30 May 2018

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

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Logic programming (68N17) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On constraint satisfaction problems below P
• On constraint satisfaction problems below P
• Linear Datalog and Bounded Path Duality of Relational Structures
• Datalog and Constraint Satisfaction with Infinite Templates
• Datalog and constraint satisfaction with infinite templates

Cites work

• A course in combinatorics.
• Closed systems of functions and predicates
• Computational Complexity
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Directed st-Connectivity Is Not Expressible in Symmetric Datalog
• Dualities for Constraint Satisfaction Problems
• Finitely related algebras in congruence distributive varieties have near unanimity terms
• scientific article; zbMATH DE number 1670830 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• Linear Datalog and Bounded Path Duality of Relational Structures
• Near unanimity constraints have bounded pathwidth duality
• On \(n\)-permutable congruences
• On digraph coloring problems and treewidth duality
• ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
• Robust satisfiability of constraint satisfaction problems
• Symmetric space-bounded computation
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Undirected ST-connectivity in log-space
• Universal algebra and hardness results for constraint satisfaction problems

Cited in

(9)

• A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\)
• Directed st-Connectivity Is Not Expressible in Symmetric Datalog
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Robust algorithms with polynomial loss for near-unanimity CSPs
• The smallest hard trees
• Maximal digraphs with respect to primitive positive constructability
• Local consistency as a reduction between constraint satisfaction problems
• Symmetric linear arc monadic Datalog and gadget reductions
• Symmetric linear arc monadic Datalog and gadget reductions

Describes a project that uses

Uses Software

• Datalog

This page was built for publication: \(n\)-permutability and linear Datalog implies symmetric Datalog

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