The Weighted Cfg Constraint

Authors :: Toby Walsh
George Katsirelos
Nina Narodytska
Source :: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems ISBN: 9783540681540
Publication Year :: 2008
Publisher :: Springer Berlin Heidelberg, 2008.
Abstract: We introduce the weighted CFG constraint and propose a propagation algorithm that enforces domain consistency in O(n3|G|) time. We show that this algorithm can be decomposed into a set of primitive arithmetic constraints without hindering propagation.

Subjects :: Constraint (information theory)
Set (abstract data type)
Mathematical optimization
Consistency (database systems)
Regular language
Chomsky hierarchy
Algorithm
Mathematics
Domain (software engineering)

ISBN :: 978-3-540-68154-0
ISBNs :: 9783540681540
Database :: OpenAIRE
Journal :: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems ISBN: 9783540681540
Accession number :: edsair.doi...........6c7c2621df084b036993e7082adba819

Tools