Combinatorial problems raised from 2-semilattices

DOI10.1016/j.jalgebra.2004.07.044zbMath1110.08001OpenAlexW2040102827MaRDI QIDQ2496183

Andrei A. Bulatov

Publication date: 12 July 2006

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

Full work available at URL: https://ora.ox.ac.uk/objects/uuid:4c35dcb3-e436-4144-a4bd-b3c19915165f

zbMATH Keywords

groupoidconstraint satisfaction problemminimal clone2-semilattice

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics of partially ordered sets (06A07) Applications of universal algebra in computer science (08A70) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Operations and polynomials in algebraic structures, primal algebras (08A40) Semilattices (06A12)

Related Items (20)

Tractability in constraint satisfaction problems: a survey ⋮ Sherali-Adams Relaxations for Valued CSPs ⋮ The complexity of constraint satisfaction games and QCSP ⋮ Constraint Satisfaction Problems Solvable by Local Consistency Methods ⋮ Testing list \(H\)-homomorphisms ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Unnamed Item ⋮ Some structural and residual properties of 2-semilattices ⋮ Quantified Constraints in Twenty Seventeen ⋮ Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms ⋮ There are no pure relational width 2 constraint satisfaction problems ⋮ A new tractable class of constraint satisfaction problems ⋮ THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA ⋮ Dichotomy for finite tournaments of mixed-type ⋮ Existentially restricted quantified constraint satisfaction ⋮ Minimization of locally defined submodular functions by optimal soft arc consistency ⋮ Approximability of the Maximum Solution Problem for Certain Families of Algebras ⋮ Recent Results on the Algebraic Approach to the CSP ⋮ Dualities for Constraint Satisfaction Problems ⋮ Commutative idempotent groupoids and the constraint satisfaction problem.

Cites Work

• Network-based heuristics for constraint-satisfaction problems
• An optimal k-consistency algorithm
• From local to global consistency
• Consistency in networks of relations
• Temporal constraints: A survey
• Constraints, consistency and closure
• On the algebraic structure of combinatorial problems
• Constraints and universal algebra
• Networks of constraints: Fundamental properties and applications to picture processing
• Minimal clones generated by majority operations
• Equations of tournaments are not finitely based
• Structure-driven algorithms for truth maintenance
• The complexity of constraint satisfaction revisited
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• On binary constraint problems
• Representation of undirected graphs by anticommutative conservative groupoids
• Closure properties of constraints
• MINIMAL CLONES OF CONSERVATIVE FUNCTIONS
• The complexity of maximal constraint languages
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Principles and Practice of Constraint Programming – CP 2003
• Tractable constraints on ordered domains
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Combinatorial problems raised from 2-semilattices