Abstract
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.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
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.
C. Beeri, R. Fagin, D. Maier and M. Yannakakis, On the desirability of acyclic database schemes,J. ACM 30(3) (1983) 479–513.
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).
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.
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”.
M. Dalal and D.W. Etherington, A hierarchy of tractable satisfiability problems,Information Processing Letters 44 (1992) 173–180.
R. Dechter, Enhancement schemes for constraint processing: Backjumping, learning, and cutset decomposition,Artificial Intelligence 41 (1990) 273–312.
R. Dechter, Constraint networks, in:Encyclopedia of Artificial Intelligence, ed. S.C. Shapiro (John Wiley, 2nd edition, 1992) pp. 276–285.
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.
J. de Kleer, A.K. Mackworth and R. Reiter, Characterizing diagnosis and systems,Artificial Intelligence 56 (1992) 197–222.
J. de Kleer and B.C. Williams, Diagnosis multiple faults,Artificial Intelligence 32 (1987) 97–130.
R. Dechter and J. Pearl, Network-based heuristics for constraint satisfaction problems,Artificial Intelligence 34 (1988) 1–38.
R. Dechter and J. Pearl, Tree clustering for constraint networks,Artificial Intelligence 38 (1989) 353–366.
S. Even, A. Itai and A. Shamir, On the complexity of timetable and multi-commodity flow,SIAM Journal of Computing 5 (1976) 691–703.
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).
E.C. Freuder, A sufficient condition for backtrack-bounded search,Journal of the ACM 32(4) (1985) 755–761.
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.
M. Gelfond and V. Lifschitz, Classical negation in logic programs and disjunctive databases,New Generation Computing 9 (1991) 365–385.
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.
G. Gallo and M. Grazia Scutella, Polynomially solvable satisfiability problems,Information Processing Letters 29 (1988) 221–227.
A. Itai and J.A. Makowsky, Unification as a complexity measure for logic programming,Journal of Logic Programming 4 (1987) 105–117.
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).
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.
V. Lifshitz, Computing circumscription, in:IJCAI-85: Proceedings of the International Joint Conference on Al (1985) pp. 121–127.
D.W. Loveland, Near-Horn prolog and beyond,Journal of Automated Reasoning 7 (1991) 1–26.
D. Maier,The Theory of Relational Databases (Computer Science Press, Rockville, MD, 1983).
J. McCarthy, Circumscription — a form of non-monotonic reasoning,Artificial Intelligence 13 (1980) 27–39.
J. McCarthy, Application of circumscription to formalizing common-sense knowledge,Artificial Intelligence 28 (1986) 89–116.
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.
R. Reiter, A theory of diagnosis from first principles,Artificial Intelligence 32 (1987) 57–95.
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).
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.
Author information
Authors and Affiliations
Additional information
This work was partially supported by an IBM graduate fellowship to the first author, by NSF grants IRI-9157636 and IRI-9200918, by Air Force Office of Scientific 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 first author was a graduate student at the Cognitive Systems Laboratory, Computer Science Department, University of California, Los Angeles, California, USA.
Rights and permissions
About this article
Cite this article
Ben-Eliyahu, R., Dechter, R. On computing minimal models. Ann Math Artif Intell 18, 3–27 (1996). https://doi.org/10.1007/BF02136172
Issue Date:
DOI: https://doi.org/10.1007/BF02136172