The Weighted CFG Constraint

2009/09/24 by George Katsirelos, Katsirelos, George, Nina Narodytska +3
Computer Science · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #I.2.4 #cs.AI

paper · pdf · doi:10.48550/arxiv.0909.4456

Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 5th International Conference, CPAIOR 2008, Paris, France, May 20-23, 2008, Proceedings

arxiv created 2009/09/24 · arxiv updated 2009/12/01

Abstract

We introduce the weighted CFG constraint and propose a propagation algorithm that enforces domain consistency in O(n³|G|) time. We show that this algorithm can be decomposed into a set of primitive arithmetic constraints without hindering propagation.

Related

• The Rough Guide to Constraint Propagation
• The Essence of Constraint Propagation
• Flow-Based Propagators for the SEQUENCE and Related Global Constraints
• Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
• The Propagation Depth of Local Consistency