A framework for prioritized reasoning based on the choice evaluation

ABSTRACT

This work addresses the issue of prioritized reasoning in the context of logic programming. The case of preference conditions involving atoms is considered and a refinement of the comparison method of the Answer Set Optimization semantics [4] is presented. The paper introduces the concept of choice, as a set of preference rules describing common choice options in different contexts. Thus, intuitively, in the proposed approach the preference rules are not evaluated separately; but the subset of rules, related to the same choice are individuated and the choice instead of rule satisfaction is considered. The role of constraints in the feasibility of choice options is then investigated and an alternative semantics, evaluating choices on the basis of their really possible (allowed) options, is developed. Complexity analysis is also performed showing that the introduction of choices does not increase the complexity of computing preferred stable models.

REFERENCES

• 1: Brewka, G., Well-Founded Semantics for Extended Logic Programs with Dynamic Preferences. Journal of Artificial Intelligence and Reasoning, 4: 19-36, 1996.
• 2: Gerhard Brewka , Thomas Eiter, Preferred answer sets for extended logic programs, Artificial Intelligence, v.109 n.1-2, p.297-356, April 1999 [doi>10.1016/S0004-3702(99)00015-6]
• 3: Gerhard Brewka, Logic programming with ordered disjunction, Eighteenth national conference on Artificial intelligence, p.100-105, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 4: Brewka, G., Niemela, I., Truszczynski, M., Answer Set Optimization. IJCAI, 867-872, 2003.
• 5: Brewka, G., Complex Preferences for Answer Set Optimization, KR, 213-223, 2004.
• 6: Delgrande, J., P., Schaub, T., Tompits, H., Logic Programs with Compiled Preferences. ECAI, 464-468, 2000.
• 7: James P. Delgrande , Torsten Schaub , Hans Tompits, A framework for compiling preferences in logic programs, Theory and Practice of Logic Programming, v.3 n.2, p.129-187, March 2003 [doi>10.1017/S1471068402001539]
• 8: Thomas Eiter , Georg Gottlob , Heikki Mannila, Disjunctive datalog, ACM Transactions on Database Systems (TODS), v.22 n.3, p.364-418, Sept. 1997 [doi>10.1145/261124.261126]
• 9: Gelfond, M., Lifschitz, V., The Stable Model Semantics for Logic Programming, ICLP, 1070--1080, 1988.
• 10: Gelfond, M., Lifschitz, V., Classical Negation in Logic Programs and Disjunctive Databases, New Generation Computing, 9:365-385, 1991.
• 11: Michael Gelfond , Tran Cao Son, Reasoning with Prioritized Defaults, Selected papers from the Third International Workshop on Logic Programming and Knowledge Representation, p.164-223, October 17, 1997
• 12: Papadimitriou, C. H., Computational Complexity. Addison-Wesley, 1994.
• 13: Chiaki Sakama , Katsumi Inoue, Prioritized logic programming and its application to commonsense reasoning, Artificial Intelligence, v.123 n.1-2, p.185-222, Oct. 2000 [doi>10.1016/S0004-3702(00)00054-0]
• 14: Schaub, T., Wang, K., A Comparative Study of Logic Programs with Preference. IJCAI, 597-602, 2001.
• 15: Davy Van Nieuwenborgh , Dirk Vermeir, Preferred Answer Sets for Ordered Logic Programs, Proceedings of the European Conference on Logics in Artificial Intelligence, p.432-443, September 23-26, 2002
• 16: Van Nieuwenborgh, D., Heymans, S., Vermeir, D., On Programs with Linearly Ordered Multiple Preferences. ICLP, 180-194, 2004.
• 17: Wakaki, T., Inoue, K., Sakama, C., Nitta, K., Computing Preferred Answer Sets in Answer Set Programming. LPAR, 259-273, 2003.
• 18: Kewen Wang , Lizhu Zhou , Fangzhen Lin, Alternating Fixpoint Theory for Logic Programs with Priority, Proceedings of the First International Conference on Computational Logic, p.164-178, July 01, 2000
• 19: Yan Zhang , Norman Y. Foo, Answer sets for prioritized logic programs, Proceedings of the 1997 international symposium on Logic programming, p.69-83, November 1997, Port Washington, New York, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.6 Logic Programming

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

General Terms:
Algorithms, Languages, Theory

Keywords:
answer set optimization, prioritized logic programming