Absorption in universal algebra and CSP

DOI10.4230/DFU.VOL7.15301.45MaRDI QIDQ4993595zbMATH OpenFDO

Authors Libor Barto, Marcin Kozik

Publication date 15 June 2021

Full work available at URL https://doi.org/10.4230/DFU.VOL7.15301.45

zbMATH Keywords

absorptionalgebraic approachconstraint satisfaction problem

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Analysis of algorithms and problem complexity (68Q25) Computational aspects of satisfiability (68R07)

Recommendations

• On the scope of the universal-algebraic approach to constraint satisfaction
• Constraints and universal algebra
• Decidability of absorption in relational structures of bounded width.
• The complexity of constraint satisfaction: an algebraic approach
• scientific article; zbMATH DE number 1670830

Cites work

• H-coloring dichotomy revisited
• A Simple Algorithm for Mal'tsev Constraints
• A strong Mal'cev condition for locally finite varieties omitting the unary type
• A Subalgebra Intersection Property for Congruence Distributive Varieties
• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• Absorption and directed Jónsson terms
• Algebras Whose Congruence Lattices are Distributive.
• Bounded width problems and algebras
• Characterizations of several Maltsev conditions.
• Classifying the Complexity of Constraints Using Finite Algebras
• Closed systems of functions and predicates
• Closure properties of constraints
• Complexity of conservative constraint satisfaction problems
• Conservative constraint satisfaction re-revisited
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Constraint Satisfaction Problems with Infinite Templates
• Cyclic terms for \(\text{SD}_{\vee}\) varieties revisited
• Existence theorems for weakly symmetric operations
• Finitely related algebras in congruence distributive varieties have near unanimity terms
• Finitely related algebras in congruence modular varieties have few subpowers
• scientific article; zbMATH DE number 4035895 (Why is no real title available?)
• scientific article; zbMATH DE number 1487982 (Why is no real title available?)
• scientific article; zbMATH DE number 3336786 (Why is no real title available?)
• scientific article; zbMATH DE number 3019695 (Why is no real title available?)
• scientific article; zbMATH DE number 3091018 (Why is no real title available?)
• Mal'tsev conditions, lack of absorption, and solvability.
• Near unanimity constraints have bounded pathwidth duality
• On the algebraic structure of combinatorial problems
• On the complexity of H-coloring
• Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties.
• Polynomial interpolation and the Chinese remainder theorem for algebraic systems
• Robust algorithms with polynomial loss for near-unanimity CSPs
• Robust satisfiability of constraint satisfaction problems
• The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems
• The collapse of the bounded width hierarchy
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The constraint satisfaction problem and universal algebra
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The structure of finite algebras
• The weakest nontrivial idempotent equations
• The wonderland of reflections
• Varieties Obeying Homotopy Laws
• Weak consistency notions for all the CSPs of bounded width

Cited in

(20)

• On the complexity of \(\mathbb{H}\)-coloring for special oriented trees
• Mitschke's theorem is sharp
• On a stronger reconstruction notion for monoids and clones
• Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting)
• Loop conditions
• The number of clones determined by disjunctions of unary relations
• Deciding absorption
• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• On absorption in semigroups and n-ary semigroups.
• Smooth digraphs modulo primitive positive constructability and cyclic loop conditions
• Loop conditions for strongly connected digraphs
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• THE DISTRIBUTIVITY SPECTRUM OF BAKER’S VARIETY
• Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
• Between an n-ary and an n + 1-ary near-unanimity term
• The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation
• SDPs and robust satisfiability of promise CSP
• Approximate graph colouring and the hollow shadow
• Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
• Sensitive instances of the constraint satisfaction problem

This page was built for publication: Absorption in universal algebra and CSP

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