A Predicate-Transition Net Model for Parallel Interpretation of Logic Programs

ABSTRACT

This paper presents a predicate/transition net model for a subset of Horn clause logic programs. The paper discusses the syntax, transformation procedure, semantics. and deduction process for the net model. A possible parallel implementation for the net model is described, which is based on the concepts of communicating processes and relations. The proposed net model offers a syntactical variant of Horn clause logic and has two distinctions from other existing schemes for the logic programs: representation formalism and the deduction method. The significance of the work is that the net model provides an approach towards the solutions of the separation of logic from control and the improvement of the execution efficiency through parallel processing for the logic programs. The abstract nature of the net model also lends itself to differentimplementation strategies.

REFERENCES

• 1: Krzysztof R. Apt , M. H. van Emden, Contributions to the Theory of Logic Programming, Journal of the ACM (JACM), v.29 n.3, p.841-862, July 1982 [doi>10.1145/322326.322339]
• 2: Avron Barr , Edward A. Feigenbaum, Handbook of AI, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: {3} L. Bic, "A data-driven model for parallel interpretation of logic programs," in <i>Proc. Int. Conf. 5th Generation Comput. Syst.</i>, Tokyo, Japan, 1984, pp. 517-523.
• 4: Chin-Liang Chang , Richard C. Lee , Richard Char-Tung Lee, Symbolic Logic and Mechanical Theorem Proving, Academic Press, Inc., Orlando, FL, 1997
• 5: {5} J. H. Chang, A. M. Despain, and D. DeGroot, "AND-parallelism of logic programs based on static data dependency analysis," in <i>Proc. IEEE-CO-MPCON, 1985</i>, pp. 218-225.
• 6: {6} A. Ciepielewski and S. Haridi. "A formal model for OR-parallel execution of logic programs," in <i>Proc. IFIP Conf., 1983</i>, pp. 299-305.
• 7: Keith Clark , Steve Gregory, PARLOG: parallel programming in logic, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.1, p.1-49, Jan. 1986 [doi>10.1145/5001.5390]
• 8: {8} J. S. Conery and D. F. Kibler, "AND parallelism and nondeterminism in logic programs," <i>New Generation Comput.</i>, vol 3, pp. 43- 70, 1985.
• 9: John S. Conery, Parallel execution of logic programs, Kluwer Academic Publishers, Norwell, MA, 1986
• 10: {10} J. L. Darlinton, "A net based theorem prover for program verification and synthesis," GMD-IST Internal Rep.. Dec. 1978.
• 11: {11} D. DeGroot, "Restricted AND-parallelism," in <i>Proc. Int. Conf. 5th Generation Comput. Syst.</i>, Tokyo, Japan, 1984, pp. 471-478.
• 12: Amaryllis Deliyanni , Robert A. Kowalski, Logic and semantic networks, Communications of the ACM, v.22 n.3, p.184-192, March 1979 [doi>10.1145/359080.359090]
• 13: {13} K. Furukawa, K. Nitta, and Y. Matsumoto, "A backup parallel interpreter for prolog programs," in <i>Logic Programming and Its Appllications </i>. M. van Caneghem and D. H. D. Warren, Eds. Norwood, NJ: Ablex, 1986, pp. 91-102.
• 14: Herve Gallaire , Jack Minker , Jean-Marie Nicolas, Logic and Databases: A Deductive Approach, ACM Computing Surveys (CSUR), v.16 n.2, p.153-185, June 1984 [doi>10.1145/356924.356929]
• 15: {15} H. J. Genrich and G. Thieler-Mevissen, "The calculus of facts," in <i>Lecture Notes in Computer Science, vol. 45, 1976</i>, pp. 588-595.
• 16: {16} H. J. Genrich and K. Lautenbach, "Facts in place/transition nets," in <i>Lecture Notes in Computer Science</i>, vol. 64, 1978. pp. 213-231.
• 17: {17} H. J. Genrich and K. Lautenbach, "The analysis of distributed systems by means of predicate/ transition nets," in <i>Lecture Notes in Computer Science</i>. vol. 70, 1979, pp. 125-146.
• 18: Hartmann J. Genrich , Kurt Lautenbach , P. S. Thiagarajan, Elements of General Net Theory, Proceedings of the Advanced Course on General Net Theory of Processes and Systems: Net Theory and Applications, p.21-163, October 08-19, 1979
• 19: {19} H. J. Genrich and K. Lautenbach, "System modelling with high-level Petri nets," <i>Theoretical Comput. Sci.</i>, vol. 13, pp. 109-136, 1981.
• 20: {20} H. J. Genrich and K. Lautenbach, "S-invariance in predicate/transition nets," GMD Internal Rep., 1982.
• 21: A. Giordana , L. Saitta, Modeling production rules by means of predicate transition networks, Information Sciences: an International Journal, v.35 n.1, p.1-41, March 1985 [doi>10.1016/0020-0255(85)90039-8]
• 22: {22} R. Hasegawa and M. Amamiya, "Parallel execution of logic programs based on dataflow concept," in <i>Proc. Int. Conf. 5th Generation Comput. Syst.</i>, Tokyo, Japan, 1984, pp. 507-516.
• 23: Christopher John Hogger, Introduction to logic programming, Academic Press Professional, Inc., San Diego, CA, 1984
• 24: {24} K. Jensen, "Coloured Petri nets and the invariant method," <i>Theoretical Comput. Sci.</i>, vol. 14, pp. 317-336, 1981.
• 25: Kurt Jensen, How to Find Invariants for Coloured Petri Nets, Proceedings on Mathematical Foundations of Computer Science, p.327-338, August 31-September 04, 1981
• 26: {26} W. E. Kluge and H. Schlutter, "Petri net model for the evaluation of applicative programs based on X-expressions," <i>IEEE Trans. Software Eng.</i>, vol. SE-9, pp. 415-427, 1983.
• 27: {27} R. Kowalski, "Predicate logic as programming language," in <i>Proc. IFIP Conf.</i>, 1974, pp. 569-574.
• 28: Robert Kowalski, Algorithm = logic + control, Communications of the ACM, v.22 n.7, p.424-436, July 1979 [doi>10.1145/359131.359136]
• 29: Robert A. Kowalski, Logic for Problem Solving, Prentice Hall PTR, Upper Saddle River, NJ, 1979
• 30: {30} R. Kowalski, "Logic programming," in <i>Proc. IFIP Conf., 1983</i>, pp. 133- 145.
• 31: {31} R. Kowalski, "Directions for logic programming," in <i>Proc. 2nd IEEE Int. Symp. Logic Programming</i>, 1985, pp. 2-7.
• 32: {32} K. Lautenbach and A. Pagnoni, "Invariance and duality in predicate/ transition nets and in colored nets," GMD Internal Rep. 1985.
• 33: {33} K. Lautenbach, "On logical and linear dependencies," GMD Internal Rep., 1985.
• 34: {34} G. Lindstmm and P. Panangaden, "Stream based execution of logic programs," in <i>Proc. 1st IEEE Int. Symp. Logic Programming, 1984</i>, pp. 168-176.
• 35: {35} G. J. Lipovski and M. V. Hermenegildo, "B-log: A branch and bound methodology for the parallel execution of logic programs," in <i>Proc. IEEE Int. Conf. Parallel Processing</i>. 1985, pp. 560-567.
• 36: J. W. Lloyd, Foundations of logic programming, Springer-Verlag New York, Inc., New York, NY, 1984
• 37: Eliezer L. Lozinskii, A problem-oriented inferential database system, ACM Transactions on Database Systems (TODS), v.11 n.3, p.323-356, Sept. 1986 [doi>10.1145/6314.6419]
• 38: J. Martinez , Manuel Silva, A Simple and Fast Algorithm to Obtain All Invariants of a Generalized Petri Net, Selected Papers from the First and the Second European Workshop on Application and Theory of Petri Nets, p.301-310, September 28-30, 1980
• 39: {39} T. Murata, "Modeling and analysis of concurrent systems," in <i>Handbook of Software Engineering</i>, C. R. Vick and C. V. Ramamoorthy, Eds. New York: van Nostrand Reinhold, 1984, pp. 39- <i>63</i>.
• 40: {40} T. Murata and D. Zhang, "A high-level Petri net model for parallel interpretation of logic programs," in <i>Proc. IEEE Int. Conf. Comput. Lang.</i>, 1986, pp. 123-132.
• 41: {41} T. Murata and G. Peterka, "Application of colored Petri net T-invariants to logic programming," in <i>Proc. 5th Int. Conf. Syst. Eng.</i>, 1987.
• 42: Y. Narahari , N. Viswanadham, On the invariants of coloured Petri nets, Advances in Petri Nets 1985, covers the 6th European Workshop on Applications and Theory in Petri Nets-selected papers, p.330-345, June 01, 1985
• 43: N. J. Nilsson, Principles of artificial intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1980
• 44: Luis Moniz Pereira , Luis Monteiro , Jose Cunha , Joaquim N Aparicio, Delta Prolog: a distributed backtracking extension with events, Proceedings on Third international conference on logic programming, p.69-83, September 1986, London, United Kingdom
• 45: {45} J. L. Peterson and T. H. Bredt, "A comparison of models of parallel computation," in <i>Proc. IFIP Conf.</i>, 1974, pp. 466-470.
• 46: James L. Peterson, Petri Nets, ACM Computing Surveys (CSUR), v.9 n.3, p.223-252, Sept. 1977 [doi>10.1145/356698.356702]
• 47: James Lyle Peterson, Petri Net Theory and the Modeling of Systems, Prentice Hall PTR, Upper Saddle River, NJ, 1981
• 48: {48} R. J. Popplestone, "Relational programming," in <i>Machine Intelligence </i>, vol. 9, J. E. Hayes, D. Michie, and L. I. Mikulich. Eds. Edinburgh, Scotland: Edinburgh University Press, 1979, pp. 3-26.
• 49: {49} W. Reisig, <i>Petri Nets</i>. New York: Springer-Verlag, 1985.
• 50: J. A. Robinson, A Machine-Oriented Logic Based on the Resolution Principle, Journal of the ACM (JACM), v.12 n.1, p.23-41, Jan. 1965 [doi>10.1145/321250.321253]
• 51: {51} J. A. Robinson, "Automatic deduction with hyper-resolution," <i>Int. J. Comput. Math., vol. I</i>, pp. 227-234, 1965.
• 52: {52} J. A. Robinson, "Logic programming: Past, present and future." ICOT, Tech. Rep. TR-015, 1983.
• 53: {53} E. Y. Shapiro, "A subset of concurrent Prolog and its interpreter," ICOT, Tech. Rep. TR-003, 1983.
• 54: {54} S. Sickel, "A search technique for clause interconnectivity graphs," <i>IEEE Trans. Comput.</i>, vol. C-25, pp. 823-835, 1976.
• 55: {55} M. Silva, J. Martinez, P. Ladet, and H. Alla, "Generalized inverses and the calculation of symbolic invariants for colored Petri nets," <i>Technique et Science Informatiques</i>, vol. 4, no. 1, pp. 113-126, 1985.
• 56: {56} R. Steinmetz and S. Theissen, "Integration of Petri nets into a tool for consistency checking of expert systems with rule-based knowledge representation," in <i>Proc. 6th European Workshop Applications and Theory of Petri Nets</i>, 1985, pp. 35-52.
• 57: {57} L. Sterling and E. Shapiro, <i>The Art of Prolog</i>. Cambridge, MA: MIT Press, 1986.
• 58: {58} S. A. Tarnlund, "Logic programming: From a logic point of view," in <i>Proc. 3rd IEEE Int. Symp. Logic Programming</i>, 1986, pp. 96-103.
• 59: {59} S. Taylor <i>et al.</i>, "Logic programming using parallel associative operations," in <i>Proc. 1st IEEE Int. Symp. Logic Programming</i>, 1984, pp. 58-68.
• 60: {60} G. Thieler-Mevissen, "The Petri net calculus of predicate logic," GMD Int. Rep.. 1976.
• 61: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 62: Gordon J. VanderBrug , Jack Minker, State-space problem-reduction, and theorem proving—some relationships, Communications of the ACM, v.18 n.2, p.107-119, Feb. 1975 [doi>10.1145/360666.360672]
• 63: M. H. Van Emden , R. A. Kowalski, The Semantics of Predicate Logic as a Programming Language, Journal of the ACM (JACM), v.23 n.4, p.733-742, Oct. 1976 [doi>10.1145/321978.321991]
• 64: {64} D. Zhang and T. Murata, "Fixpoint semantics for Petri net model of Horn clause logic programs," Univ. Illinois at Chicago. 1987, Tech. Rep. UIC-EECS87-2 also submitted for publication.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

General Terms:
Algorithms, Languages, Theory

Keywords:
AND/OR parallelisms, communicating processes, deduction process, fixpoint semantics, Horn clause logic programs, logic programming, Petri nets, predicate/transition nets, relational operations.