Mode-directed preferences for logic programs

ABSTRACT

Preference logic programming (PLP) is an extension of constraint logic programming for declaratively specifying problems requiring optimization or comparison and selection among alternative solutions to a query. PLP essentially separates the programming of a problem itself from the criteria specification of its solution selection. In this paper we provide a syntax for PLP based upon mode-directed preferences and a semantics based upon Herbrand models and fixed-point theory. Our method uses mode declarations to designate certain predicates as optimization predicates, and uses preference rules for stating the criteria for determining their optimal solutions. This paper also presents an elegant and easy method of executing preference logic programs in terms of tabled Prolog. Automatic transformation is applied to embed the preferences into the problem specification for efficient evaluation. We show that the procedural semantics of a preference logic program is equivalent to its declarative semantics.

REFERENCES

• 1: Weidong Chen , David S. Warren, Tabled evaluation with delaying for general logic programs, Journal of the ACM (JACM), v.43 n.1, p.20-74, Jan. 1996 [doi>10.1145/227595.227597]
• 2: Baoqiu Cui , Terrance Swift, Preference logic grammars: fixed point semantics and application to data standardization, Artificial Intelligence, v.138 n.1-2, p.117-147, June 2002 [doi>10.1016/S0004-3702(02)00185-6]
• 3: François Fages, On the Semantics of Optimization Predicates in CLP Languages, Proceedings of the 13th Conference on Foundations of Software Technology and Theoretical Computer Science, p.193-204, December 15-17, 1993
• 4: Sumit Ganguly , Sergio Greco , Carlo Zaniolo, Minimum and maximum predicates in logic programming, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.154-163, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113427]
• 5: K. Govindarajan, B. Jayaraman, and S. Mantha: Preference Logic Programming. In Proceedings of International Conference on Logic Programming (ICLP), pages 731--745, 1995.
• 6: Kannan Govindarajan , Bharat Jayaraman , Surya Mantha, Optimization and relaxation in constraint logic languages, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.91-103, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237735]
• 7: Hai-Feng Guo , Gopal Gupta, A Simple Scheme for Implementing Tabled Logic Programming Systems Based on Dynamic Reordering of Alternatives, Proceedings of the 17th International Conference on Logic Programming, p.181-196, November 26-December 01, 2001
• 8: Hai-Feng Guo and Gopal Gupta: Simplifying Dynamic Programming via Tabling. Practical Aspects of Declarative Languages (PADL), pages 163--177, 2004.
• 9: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 10: Bharat Jayaraman, Kannan Govindarajan, and Surya Mantha: Preference Logic Grammars. Computer Languages, 24(3): pages 179--196, 1998.
• 11: M. Wilson and A. Borning: Hierarchical Constraint Logic Programming Journal of Logic Programming, 16:277--318, 1993.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages

Keywords:
preference logic programming, tabled resolution