Construction and Optimization of a Parallel Engine for Answer Set Programming

  • Enrico Pontelli
  • Omar El-Khatib
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 1990)


In this paper we study the use of parallelism to speed up execution of Answer Set Programs (ASP). ASP is an emerging programming paradigm which combines features from constraint programming, logic programming, and non-monotonic reasoning, and has found relevant applications in areas such as planning and intelligent agents. We propose different methodologies to parallelize execution of ASP programs, and we describe a prototype which exploits one form of parallelism.


Logic Program Shared Memory Logic Programming Choice Point Stable Model Semantic 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    K.A.M. Ali and R. Karlsson. The Muse Or-parallel Prolog Model and its Performance. In N. American Conf. on Logic Prog., MIT Press, 1990.Google Scholar
  2. 2.
    C. Baral and M. Gelfond. Logic Programming and Knowledge Representation. J. of Logic Progr., 19/20:73–148, 1994.CrossRefMathSciNetGoogle Scholar
  3. 3.
    C. Bell et al. Implementing Stable Semantics by Linear Programming. In Logic Programming and Non-monotonic Reasoning, MIT Press, 1993.Google Scholar
  4. 4.
    W. Chen and D.S. Warren. Computation of Stable Models and its Integration with Logical Query Processing. Trans. on Knowledge and Data Engineering, 8(5), 1996.Google Scholar
  5. 5.
    P. Cholewinski, V.W. Marek, and M. Truszczynski. Default Reasoning System DeReS. In Int. Conf. on Principles of Knowledge Repr. and Reasoning, 1996.Google Scholar
  6. 6.
    W.F. Dowling and J.H. Gallier. Linear-time Algorithms for Testing the Satisfiability of Propositional Horn Formulae. J. of Logic Programming, 3:267–289, 1984.CrossRefMathSciNetGoogle Scholar
  7. 7.
    T. Eiter et al. The KR System dlv: Progress Report, Comparisons, and Benchmarks. In Int. Conf. on Principles of Knowledge Repr. and Reasoning, 1998.Google Scholar
  8. 8.
    M. Gelfond and V. Lifschitz. The Stable Model Semantics for Logic Programs. In Int. Symposium on Logic Programming, MIT Press, 1988.Google Scholar
  9. 9.
    G. Gupta, E. Pontelli et al. Parallel Execution of Prolog Programs: a Survey. Technical report, New Mexico State University, 2000.Google Scholar
  10. 10.
    V. Lifschitz. Answer Set Planning. In Logic Programming and Non-monotonic Reasoning, Springer Verlag, 1999.Google Scholar
  11. 11.
    V.W. Marek and M. Truszczynski. Stable Models and an Alternative Logic Programming Paradigm. In The Logic Programming Paradigm. Springer Verlag, 1999.Google Scholar
  12. 12.
    I. Niemela. Logic Programs with Stable Model Semantics as a Constraint Programming Paradigm. Annals of Mathematics and AI, (to appear).Google Scholar
  13. 13.
    I. Niemela and P. Simons. An Implementation of the Stable Model and Well-Founded Semantics for Normal LP. In LPNMR, Springer Verlag, 1997.Google Scholar
  14. 14.
    D. Ranjan, E. Pontelli, and G. Gupta. On the Complexity of Or-Parallelism. New Generation Computing, 17(3):285–308, 1999.CrossRefGoogle Scholar
  15. 15.
    P. Rao et al. XSB: A System for Efficiently Computing WFS. In Logic Programming and Non-monotonic Reasoning. Springer Verlag, 1997.Google Scholar
  16. 16.
    C. Schulte. Compairing Trailing and Copying for Constraint Programming. In International Conference on Logic Programming, pages 275–289. MIT Press, 1999.Google Scholar
  17. 17.
    A. Van Gelder, K.A. Ross, and J.S. Schlipf. The Well-Founded Semantics for General Logic Programs. Journal of the ACM, 38(3):620–650, 1991.zbMATHCrossRefGoogle Scholar
  18. 18.
    P. Van Hentenryck. Parallel Constraint Satisfaction in Logic Programming. In Proc. Int. Conf. on Logic Programming. MIT Press, 1989.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2001

Authors and Affiliations

  • Enrico Pontelli
    • 1
  • Omar El-Khatib
    • 1
  1. 1.Laboratory for Logic, DBs, and Advanced Programming, Department of Computer ScienceState UniversityNew Mexico

Personalised recommendations