Decidability of absorption in relational structures of bounded width.

DOI10.1007/S00012-014-0283-2MaRDI QIDQ2510713zbMATH OpenOpenAlexFDO

Authors 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 semidistributivitynear unanimity operationJónsson ideals

Mathematics Subject Classification ID

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

Recommendations

• Bounded width problems and algebras
• On tractability and congruence distributivity
• Graphs of relational structures: restricted types
• OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
• Asking the Metaquestions in Constraint Tractability
• scientific article; zbMATH DE number 1944123
• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• Solving CSPs using weak local consistency
• On the reduction of the CSP dichotomy conjecture to digraphs
• Finitely related algebras in congruence distributive varieties have near unanimity terms

Cites work

• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• Bounded width problems and algebras
• Classifying the Complexity of Constraints Using Finite Algebras
• Congruence distributivity implies bounded width
• Constraint Satisfaction Problems of Bounded Width
• Finitely related algebras in congruence distributive varieties have near unanimity terms
• Mal'tsev conditions, lack of absorption, and solvability.
• On the (un)decidability of a near-unanimity term
• On the reduction of the CSP dichotomy conjecture to digraphs
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory

Cited in

(12)

• OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
• Graphs of relational structures: restricted types
• Deciding absorption
• Testing for edge terms is decidable
• Absorption and directed Jónsson terms
• Congruence distributivity implies bounded width
• CD(4) has bounded width
• Bounded width problems and algebras
• On absorption in semigroups and \(n\)-ary semigroups.
• Deciding absorption in relational structures
• Absorption in universal algebra and CSP
• Algebra and the complexity of digraph CSPs: a survey

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

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