Stable models and non-determinism in logic programs with negation

ABSTRACT

Previous researchers have proposed generalizations of Horn clause logic to support negation and non-determinism as two separate extensions. In this paper, we show that the stable model semantics for logic programs provides a unified basis for the treatment of both concepts. First, we introduce the concepts of partial models, stable models, strongly founded models and deterministic models and other interesting classes of partial models and study their relationships. We show that the maximal deterministic model of a program is a subset of the intersection of all its stable models and that the well-founded model of a program is a subset of its maximal deterministic model. Then, we show that the use of stable models subsumes the use of the non-deterministic choice construct in LDL and provides an alternative definition of the semantics of this construct. Finally, we provide a constructive definition for stable models with the introduction of a procedure, called backtracking fixpoint, that non-deterministically constructs a total stable model, if such a model exists.

REFERENCES

• AV: S. Abiteboul , V. Vianu, Fixpoint extensions of first-order logic and datalog-like languages, Proceedings of the Fourth Annual Symposium on Logic in computer science, p.71-79, June 1989, Pacific Grove, California, United States
• ABW: K. R. Apt , H. A. Blair , A. Walker, Towards a theory of declarative knowledge, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• CH: Chandra, A., Harel, D., "Horn Clauses and Generalization", Journal of Logic Programming 2, 1, 1985, pp. 320-340.
• GL: Gelfond, M., Lifschitz, V., "The Stable Model Semantics for Logic Programming", Proc. 5th Int. Conf. and Symp. on Logic Programming, MIT Press, Cambridge, Ma, 1988, pp. 1070- 1080.
• KN: Krishnamurthy, R. and Naqvi, S.A., "Non- Deterministic Choice in Datalog", Proc. 3rd Int. Conf. on Data and Knowledge Bases, Morgan Kaufmann Pub., Los Altos, 1988, pp. 416-424.
• KP: Phokion G. Kolaitis , Christos H. Papadimitriou, Why not negation by fixpoint?, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.231-239, March 1988, Austin, Texas, United States [doi>10.1145/308386.308446]
• L: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• N: Naqvi, S.A., "A Logic for Negation in Database Systems," in Foundations of Deductive Databases and Logic Programming, (Minker, J. ed.), Morgan Kaufman, Los Altos, 1987.
• NT: S. Naqvi , S. Tsur, A logical language for data and knowledge bases, Computer Science Press, Inc., New York, NY, 1989
• P1: Przymusinski, T.C., "On the Semantics of Stratified Deductive Databases and Logic Programs", Journal of Automated Reasoning, to appear.
• P2: T. C. Przymusinski, On the declarative semantics of deductive databases and logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• P3: Przymusinski, T.C., "Perfect Model Semantics", Proc. 5th Int. Conf. and Symp. on Logic Programming, MIT Press, Cambridge, Ma, 1988, pp. 1081-1096.
• P4: T. C. Przymusinski, Every logic program has a natural stratification and an iterated least fixed point model, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.11-21, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73723]
• P5: Przymusinski, T.C., "Well-Founded Models are Intersections of 3-Valued Stable Models," email communication, April 1989.
• PP: Przymusinska, H, Przymusinski, T.C., "Weakly Perfect Model Semantics for Logic Programs", Proc. 5th Int. Conf. and Symp. on Logic Programming, MIT Press, Cambridge, Ma, 1988, pp. 1106-1120.
• R: K. A. Ross, A procedural semantics for well founded negation in logic programs, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.22-33, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73724]
• SZ: Sacc~ D. and C. Zaniolo, "Partial Models, Stable Models and Non-Determinism in Logic Programs with Negation," MCC/ACT Technical Report, January 1990.
• U: UUman, J.D., Principles of Database and Knowledge-Base Systems, Vol. 1 and 2, Computer Science Press, Rockville, Md., 1989.
• V1: Van Gelder, A., "Negation as Failure Using Tight Derivations for Logic Programs," Proc. 3rd IEEE Syrup. on Logic Programming, Springer-Verlag, 1986, pp. 127-138.
• V2: A. Van Gelder, The alternating fixpoint of logic programs with negation, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-10, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73722]
• VRS: Allen Van Gelder , Kenneth Ross , John S. Schlipf, Unfounded sets and well-founded semantics for general logic programs, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.221-230, March 1988, Austin, Texas, United States [doi>10.1145/308386.308444]
• Z: Zaniolo, C. "Object Identity and Inheritance in Dexlucfive Databases: an Evolutionary Approach," Procs. 1st Int. Conf. on Deductive and Object-Oriented Databases, Kyoto, Japan, 1989.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Alternation and nondeterminism
  F.3 LOGICS AND MEANINGS OF PROGRAMS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming

General Terms:
Design, Languages, Management, Performance, Reliability, Theory, Verification