An algebraic characterization of tractable constraints

DOI10.1007/BFB0030886MaRDI QIDQ6085763zbMATH OpenOpenAlexFDO

Authors P. Jeavons, David A. Cohen

Publication date 12 December 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bfb0030886

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Closure properties of constraints
• Classifying the Complexity of Constraints Using Finite Algebras
• Characterising tractable constraints
• scientific article; zbMATH DE number 1670830
• scientific article; zbMATH DE number 1008453

Cites work

• A generic arc-consistency algorithm and its specializations
• A sufficient condition for backtrack-bounded search
• Characterising tractable constraints
• Closed systems of functions and predicates
• Consistency in networks of relations
• Constraint relaxation may be perfect
• Decomposing constraint satisfaction problems using database techniques
• Fast parallel constraint satisfaction
• scientific article; zbMATH DE number 3853164 (Why is no real title available?)
• scientific article; zbMATH DE number 3972930 (Why is no real title available?)
• scientific article; zbMATH DE number 3977070 (Why is no real title available?)
• scientific article; zbMATH DE number 3987347 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Network-based heuristics for constraint-satisfaction problems
• Networks of constraints: Fundamental properties and applications to picture processing
• On binary constraint problems
• Structure identification in relational data
• The complexity of satisfiability problems
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Tractable constraints on ordered domains

Cited in

(2)

• Algebraic properties of multilinear constraints
• Direct application of constraints to symmetric algebraic systems

This page was built for publication: An algebraic characterization of tractable constraints

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