Constraint Hierarchies as Semiring-Based CSPs
Constraint Hierarchies as Semiring-Based CSPs
复制标题
作为基于半环的 CSP 的约束层次结构
DOI：
10.1109/ictai.2009.43
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Hiroshi Hosobe
中科院分区：
文献类型：
--
作者：
Alexandre Goldsztejn;Olivier Mullier;Damien Eveillard;Hiroshi Hosobe;Hiroshi Hosobe
约束为各种问题的高层建模和推理提供了有效的手段。特别是，软约束很有用，因为它们处理现实应用程序中自然出现的过度约束问题。因此，研究人员一直在探索软约束的框架。基于半环的约束满足问题框架可以表示多种软约束，如加权约束满足问题和模糊约束满足问题。约束层次框架强调软约束的层次偏好。尽管基于半环的CSP被认为是相当通用的，但它们是否能够表示约束层次尚不清楚。本文证明了一类合理的约束层次可以看作是基于半环的CSP的一个实例。
Constraints provide an effective means for the high-level modeling and reasoning of various problems. In particular, soft constraints are useful since they treat over-constrained problems that naturally arise in real-life applications. Therefore, researchers have been exploring frameworks for soft constraints. The framework of semiring-based constraint satisfaction problems (CSPs) can express many kinds of soft constraints such as weighted CSPs and fuzzy CSPs. The framework of constraint hierarchies emphasizes hierarchical preferences of soft constraints. Although semiring-based CSPs are known to be considerably general, it has been unclear whether they can express constraint hierarchies. In this paper, we show that a reasonable class of constraint hierarchies can be regarded as an instance of semiring-based CSPs.