Decidability of absorption in relational structures of bounded width.

DOI10.1007/s00012-014-0283-2zbMath1307.08008OpenAlexW1967577938MaRDI QIDQ2510713

Jakub Bulín

Publication date: 1 August 2014

Published in: Algebra Universalis (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00012-014-0283-2

zbMATH Keywords

constraint satisfaction problemfinitely related algebrasabsorbing subuniversesalgebras of bounded widthcongruence meet semidistributivityJónsson idealsnear unanimity operation

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Equational logic, Mal'tsev conditions (08B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Congruence modularity, congruence distributivity (08B10)

Related Items (3)

Deciding absorption in relational structures ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ Testing for edge terms is decidable

Cites Work

• Mal'tsev conditions, lack of absorption, and solvability.
• Bounded width problems and algebras
• On the (un)decidability of a near-unanimity term
• Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
• Congruence Distributivity Implies Bounded Width
• 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
• Constraint Satisfaction Problems of Bounded Width
• Classifying the Complexity of Constraints Using Finite Algebras
• On the Reduction of the CSP Dichotomy Conjecture to Digraphs

This page was built for publication: Decidability of absorption in relational structures of bounded width.