The weighted Grammar constraint |
| |
Authors: | George Katsirelos Nina Narodytska Toby Walsh |
| |
Affiliation: | 1. University of New South Wales and NICTA, Sydney, Australia
|
| |
Abstract: | We introduce the WeightedGrammar constraint and propose propagation algorithms based on the CYK parser and the Earley parser. We show that the traces of these algorithms can be encoded as a weighted negation normal form (WNNF), a generalization of NNF that allows nodes to carry weights. Based on this connection, we prove the correctness and complexity of these algorithms. Specifically, these algorithms enforce domain consistency on the WeightedGrammar constraint in time O(n 3). Further, we propose that the WNNF constraint can be decomposed into a set of primitive arithmetic constraint without hindering propagation. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|