Efficient Algorithms for Description Problems over Finite Totally Ordered Domains
Efficient Algorithms for Description Problems over Finite Totally Ordered Domains
复制标题
有限全序域描述问题的高效算法
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
B. Zanuttini
中科院分区：
文献类型：
--
作者：
À. Gil;M. Hermann;G. Salzer;B. Zanuttini
给定有限全序域上的有限向量集，我们研究以合取范式计算约束的问题，使得产生的约束的解集与原始集相同。我们针对一般情况开发了一种高效的多项式时间算法，然后是特定的多项式时间算法，分别为在合取、析取和中值运算下闭合的向量集生成 Horn、对偶 Horn 和双合公式。我们的结果概括了 Dechter 和 Pearl 在关系数据方面的工作，以及 Hebrard 和 Zanuttini 的论文。他们补充了 Hahnle 等人的结果。关于多值逻辑和 Jeavons 等人。关于约束的代数方法。
Given a finite set of vectors over a finite totally ordered domain, we study the problem of computing a constraint in conjunctive normal form such that the set of solutions for the produced constraint is identical to the original set. We develop an efficient polynomial-time algorithm for the general case, followed by specific polynomial-time algorithms producing Horn, dual Horn, and bijunctive formulas for sets of vectors closed under the operations of conjunction, disjunction, and median, respectively. Our results generalize the work of Dechter and Pearl on relational data, as well as the papers by Hebrard and Zanuttini. They complement the results of Hahnle et al. on multivalued logics and Jeavons et al. on the algebraic approach to constraints.