On computing minimal models. (English) Zbl 0891.68109
Summary: 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 first group are efficient 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 efficient 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 finding minimal models.
Keywords:
CNF propositional theoryReferences:
| [1] | R. Ben-Eliyahu and L. Palopoli, Reasoning with minimal models: Efficient algorithms and applications, in:KR-94: Proceedings of the Fourth International Conference on Principles of Knowledge Representation and Reasoning, eds. J. Doyle, E. Sandewall and P. Torasso (Morgan-Kaufmann, San Francisco, CA, 1994) pp. 39–50. |
| [2] | C. Beeri, R. Fagin, D. Maier and M. Yannakakis, On the desirability of acyclic database schemes,J. ACM 30(3) (1983) 479–513. · Zbl 0624.68087 · doi:10.1145/2402.322389 |
| [3] | C. Bell, A. Nerode, R.T. Ng and V.S. Subrahmanian, Computation and implementation of nonmonotonic deductive databases, Technical Report CS-TR-2801, University of Maryland (1991). |
| [4] | M. Cadoli, On the complexity of model finding for nonmonotonic propositional logics, in:Proceedings of the 4th Italian Conference on Theoretical Computer Science, eds. A.M. Spaccamela, P. Mentrasti and M. Venturini Zilli (World Scientific Publishing Co., October 1992) pp. 125–139. |
| [5] | R. Dechter and A. Dechter, Structure-driven algorithms for truth maintenance, Technical Report R-182, Cognitive Systems Laboratory, Computer Science Department, UCLA (August 1994). A preliminary version in:AAAI-88: Proceedings of 7th National Conference on Artificial Intelligence, under the title ”Belief maintenance in dynamics constraint networks”. |
| [6] | M. Dalal and D.W. Etherington, A hierarchy of tractable satisfiability problems,Information Processing Letters 44 (1992) 173–180. · Zbl 0774.68057 · doi:10.1016/0020-0190(92)90081-6 |
| [7] | R. Dechter, Enhancement schemes for constraint processing: Backjumping, learning, and cutset decomposition,Artificial Intelligence 41 (1990) 273–312. · doi:10.1016/0004-3702(90)90046-3 |
| [8] | R. Dechter, Constraint networks, in:Encyclopedia of Artificial Intelligence, ed. S.C. Shapiro (John Wiley, 2nd edition, 1992) pp. 276–285. |
| [9] | W.F. Dowling and J.H. Gallier, Linear time algorithms for testing the satisfiability of propositional Horn formulae,Journal of Logic Programming 3 (1984) 267–284. · Zbl 0593.68062 · doi:10.1016/0743-1066(84)90014-1 |
| [10] | J. de Kleer, A.K. Mackworth and R. Reiter, Characterizing diagnosis and systems,Artificial Intelligence 56 (1992) 197–222. · Zbl 0772.68085 · doi:10.1016/0004-3702(92)90027-U |
| [11] | J. de Kleer and B.C. Williams, Diagnosis multiple faults,Artificial Intelligence 32 (1987) 97–130. · Zbl 0642.94045 · doi:10.1016/0004-3702(87)90063-4 |
| [12] | R. Dechter and J. Pearl, Network-based heuristics for constraint satisfaction problems,Artificial Intelligence 34 (1988) 1–38. · Zbl 0643.68156 · doi:10.1016/0004-3702(87)90002-6 |
| [13] | R. Dechter and J. Pearl, Tree clustering for constraint networks,Artificial Intelligence 38 (1989) 353–366. · Zbl 0665.68084 · doi:10.1016/0004-3702(89)90037-4 |
| [14] | S. Even, A. Itai and A. Shamir, On the complexity of timetable and multi-commodity flow,SIAM Journal of Computing 5 (1976) 691–703. · Zbl 0358.90021 · doi:10.1137/0205048 |
| [15] | Y. El Fattah and R. Dechter, Diagnosing tree-decomposable circuits, Technical Report 94-18, University of California, Irvine (April 1994). A preliminary version in:DX-92: Proceedings of Workshop on Principles of Diagnosis (October 1992). |
| [16] | E.C. Freuder, A sufficient condition for backtrack-bounded search,Journal of the ACM 32(4) (1985) 755–761. · Zbl 0633.68096 · doi:10.1145/4221.4225 |
| [17] | F. Gavril, in:Computers and Intractability, A Guide to the Theory of NP-completeness, eds. M.R. Garey and D.S. Johnson (W.H. Freeman, 1979) p. 134. · Zbl 0411.68039 |
| [18] | M. Gelfond and V. Lifschitz, Classical negation in logic programs and disjunctive databases,New Generation Computing 9 (1991) 365–385. · Zbl 0735.68012 · doi:10.1007/BF03037169 |
| [19] | J. Grant and J. Minker, Deductive database systems, in:Encyclopedia of Artificial Intelligence, ed. S.C. Shapiro (John Wiley, 2nd edition, 1992) pp. 320–328. |
| [20] | G. Gallo and M. Grazia Scutella, Polynomially solvable satisfiability problems,Information Processing Letters 29 (1988) 221–227. · Zbl 0662.68037 · doi:10.1016/0020-0190(88)90113-5 |
| [21] | A. Itai and J.A. Makowsky, Unification as a complexity measure for logic programming,Journal of Logic Programming 4 (1987) 105–117. · Zbl 0641.68143 · doi:10.1016/0743-1066(87)90014-8 |
| [22] | R.M. Karp, Reducibility among combinatorial problems, in:Complexity of Computer Computations, eds. R.E. Miller and J.W. Thatcher (Plenum Press, New York, 1972). |
| [23] | R.A. Kowalski and C.J. Hogger, Logic programming, in:Encyclopedia of Artificial Intelligence, ed. S.C. Shapiro (John Wiley, 2nd edition, 1992) pp. 873–891. |
| [24] | V. Lifshitz, Computing circumscription, in:IJCAI-85: Proceedings of the International Joint Conference on Al (1985) pp. 121–127. |
| [25] | D.W. Loveland, Near-Horn prolog and beyond,Journal of Automated Reasoning 7 (1991) 1–26. · Zbl 0723.68029 · doi:10.1007/BF00249353 |
| [26] | D. Maier,The Theory of Relational Databases (Computer Science Press, Rockville, MD, 1983). · Zbl 0519.68082 |
| [27] | J. McCarthy, Circumscription – a form of non-monotonic reasoning,Artificial Intelligence 13 (1980) 27–39. · Zbl 0435.68073 · doi:10.1016/0004-3702(80)90011-9 |
| [28] | J. McCarthy, Application of circumscription to formalizing common-sense knowledge,Artificial Intelligence 28 (1986) 89–116. · doi:10.1016/0004-3702(86)90032-9 |
| [29] | J. Minker, On indefinite databases and the closed world assumption, in:Proceedings of 6th Conference on Automated Deduction, Lecture Notes in Computer Science, Vol. 138 (Springer-Verlag, 1982) pp. 292–308. · Zbl 0481.68087 · doi:10.1007/BFb0000066 |
| [30] | R. Reiter, A theory of diagnosis from first principles,Artificial Intelligence 32 (1987) 57–95. · Zbl 0643.68122 · doi:10.1016/0004-3702(87)90062-2 |
| [31] | D.W. Reed, D.W. Loveland and B.T. Smith, The near-Horn approach to disjunctive logic programming, in:Proceedings of 2nd Workshop on Extensions of Logic Programming, Lecture Notes in Artificial Intelligence, Vol. 596 (Springer-Verlag, 1992). |
| [32] | R.E. Tarjan and M. Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs and selectively reduce acyclic hypergraphs,SIAM Journal on Computing 13(3) (1984) 566–579. · Zbl 0545.68062 · doi:10.1137/0213035 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
