scientific article; zbMATH DE number 6876264
From MaRDI portal
DOI10.23638/LMCS-14(2:3)2018zbMath1476.68107arXiv1508.05766MaRDI QIDQ4643956
Publication date: 30 May 2018
Full work available at URL: https://arxiv.org/abs/1508.05766
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Logic programming (68N17)
Related Items
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, Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Universal algebra and hardness results for constraint satisfaction problems
- Symmetric space-bounded computation
- On \(n\)-permutable congruences
- On digraph coloring problems and treewidth duality
- Closed systems of functions and predicates
- Near Unanimity Constraints Have Bounded Pathwidth Duality
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- Directed st-Connectivity Is Not Expressible in Symmetric Datalog
- Undirected ST-connectivity in log-space
- ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Finitely Related Algebras In Congruence Distributive Varieties Have Near Unanimity Terms
- Linear Datalog and Bounded Path Duality of Relational Structures
- Computational Complexity
- Robust satisfiability of constraint satisfaction problems
- Dualities for Constraint Satisfaction Problems