6 Other Related Work
6 Other Related Work
复制标题
6 其他相关工作
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
David W. Etherington
中科院分区：
文献类型：
--
作者：
David W. Reed;D. Loveland;M. Garey;W. H. Freeman;M. Gelfond;S. Shapiro;David W. Etherington
本文研究了给定CNF命题理论的最小模型的计算问题。我们提出了两组算法。当理论几乎是Horn时，即当非Horn子句很少和/或在任何非Horn子句中显示为正的所有字面量的集合很小时，其余组中的算法是有效的。当理论可以表示为低密度关系的无循环网络时，另一组算法是有效的。我们的算法提出了解决最小模型问题的可处理子集的几个特征。2关于计算最小模型Rachel Ben-Eliyahu计算机科学系以色列理工学院海法32000以色列rachelb@cs.technion.ac.il Rina Dechter信息与计算机科学加州大学欧文分校美国加州92717 dechter@ics.uci.edu 1994年9月18日这项工作得到了IBM第一作者研究生奖学金的部分支持，由美国国家科学基金会资助IRI-9157636和IRI-9200918，由空军科学研究资助AFOSR 900136，由施乐帕洛阿尔托研究中心和美国东芝公司资助。这项工作的一部分是在第一作者是美国加州大学洛杉矶分校计算机科学系认知系统实验室的研究生时完成的。1
This paper addresses the problem of computing the minimal models of a given CNF propositional theory. We present two groups of algorithms. Algorithms in the rst group are e cient when the theory is almost Horn, that is, when there are few non-Horn clauses and/or when the set of all literals that appear positive in any non-Horn clause is small. Algorithms in the other group are e cient when the theory can be represented as an acyclic network of low-arity relations. Our algorithms suggest several characterizations of tractable subsets for the problem of nding minimal models. 2 On computing minimal models Rachel Ben-Eliyahu Computer Science Department Technion | Israel Institute of Technology Haifa 32000 Israel rachelb@cs.technion.ac.il Rina Dechter Information & Computer Science University of California Irvine, California 92717 USA dechter@ics.uci.edu September 18, 1994 This work was partially supported by an IBM graduate fellowship to the rst author, by NSF grants IRI-9157636 and IRI-9200918, by Air Force O ce of Scienti c Research grant AFOSR 900136, by a grant from Xerox Palo Alto research center, and by Toshiba of America. Part of this work was done while the rst author was a graduate student at the Cognitive Systems Laboratory, Computer Science Department, University of California, Los Angeles, California, USA. 1