Graphs and Colorings for Answer Set Programming with Preferences

• Autorzy: Konczak K. , Schaub T. , Linke T.
• Języki publikacji: EN

Abstrakty

EN

The integration of preferences into answer set programming constitutes an important practical device for distinguishing certain preferred answer sets from non-preferred ones. To this end, we elaborate upon rule dependency graphs and their colorings for characterizing different preference handling strategies found in the literature. We start from a characterization of (three types of) preferred answer sets in terms of totally colored dependency graphs. In particular, we demonstrate that this approach allows us to capture all three approaches to preferences in a uniform setting by means of the concept of a height function. In turn, we exemplarily develop an operational characterization of preferred answer sets in terms of operators on partial colorings for one particular strategy. In analogy to the notion of a derivation in proof theory, our operational characterization is expressed as a (non-deterministically formed) sequence of colorings, gradually turning an uncolored graph into a totally colored one.

Słowa kluczowe

EN

graphic method; mathematical programming; coloring matter; proof theory; computer science

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 57, nr 2-4
• Strony: 393--421
• Opis fizyczny: Bibliogr. 18 poz.

Twórcy

autor

Konczak K.

• Institut für Informatik, Universität Potsdam, Postfach 90 03 27, D-14439 Potsdam, Germany

autor

Schaub T.

• Institut für Informatik, Universität Potsdam, Postfach 90 03 27, D-14439 Potsdam, Germany

autor

Linke T.

• Institut für Informatik, Universität Potsdam, Postfach 90 03 27, D-14439 Potsdam, Germany

Bibliografia

• [1] Anger, C., Konczak, K., Linke, T.: NoMoRe : Non-monotonic reasoning with logic programs, Proceedings of the Eighth European Conference on Logics in Artificial Intelligence (JELIA’02) (S. Flesca, S. Greco, N. Leone, G. Ianni, Eds.), 2424, Springer-Verlag, 2002.
• [2] Brewka, G.: Well-Founded Semantics for Extended Logic Programs with Dynamic Preferences, Journal of Artificial Intelligence Research, 4, 1996, 19-36.
• [3] Brewka, G., Eiter, T.: Preferred Answer Sets for Extended Logic Programs, Artificial Intelligence, 109(1-2), 1999, 297-356.
• [4] Brignoli, G., Costantini, S., D’Antona, O., Provetti, A.: Characterizing and computing stable models of logic programs: the non-stratified case, Proceedings of the Conference on Information Technology, Bhubaneswar, India (C. Baral, H. Mohanty, Eds.), AAAI Press, 1999.
• [5] Delgrande, J., Schaub, T., Tompits, H.: A Framework for Compiling Preferences in Logic Programs, Theory and Practice of Logic Programming, 3(2), March 2003, 129-187.
• [6] Eiter, T., Faber, W., Leone, N., Pfeifer, G.: Computing preferred answer sets by meta-interpretation in answer set programming, Theory and Practice of Logic Programming, 3(4-5), 2003, 463-498.
• [7] Gelfond, M., Son, T.: Reasoning with Prioritized Defaults., Third International Workshop on Logic Programming and Knowledge Representation (J. Dix, L. Pereira, T. Przymusinski, Eds.), 1471, Springer-Verlag, 1997.
• [8] Grosof, B.: Prioritized Conflict Handling for Logic Programs, Logic Programming: Proceedings of the 1997 International Symposium (J. Maluszynsk, Ed.), The MIT Press, 1997.
• [9] Konczak, K., Linke, T., Schaub, T.: Graphs and colorings for answer set programming, 2003, In preparation.
• [10] Konczak, K., Linke, T., Schaub, T.: Graphs and colorings for answer set programming: Abridged report, Answer Set Programming: Advances in Theory and Implementation (ASP03) (M. D. Voss, A. Provetti, Eds.), 78, CEUR Workshop Proceedings, Messina, 2003.
• [11] Leone, N., Faber, W., Pfeifer, G., Eiter, T., Gottlob, G., Koch, C., Mateis, C., Perri, S., Scarcello, F.: The DLV System for Knowledge Representation and Reasoning, ACM Transactions on Computational Logic, 2003, To appear.
• [12] Linke, T.: Graph Theoretical Characterization and Computation of Answer Sets, Proceedings of the International Joint Conference on Artificial Intelligence (B. Nebel, Ed.), Morgan Kaufmann Publishers, 2001.
• [13] Lloyd, J.: Foundations of Logic Programming, Symbolic Computation, 2nd edition, Springer-Verlag, 1987.
• [14] Niemelä, I., Simons, P., Soininen, T.: Extending and implementing the stable model semantics, Artificial Intelligence, 138(1-2), 2002, 181-234.
• [15] Sakama, C., Inoue, K.: Prioritized Logic Programming and its Application to Commonsense Reasoning, Artificial Intelligence, 123(1-2), 2000, 185-222.
• [16] Schaub, T., Wang, K.: A semantic framework for preference handling in answer set programming, Theory and Practice of Logic Programming, 3(4-5), 2003, 569-607.
• [17] Wang, K., Zhou, L., Lin, F.: Alternating fixpoint theory for logic programs with priority, Proceedings of the First International Conference on Computational Logic, 1861, Springer-Verlag, 2000.
• [18] Zhang, Y.: Two results for prioritized logic programming, Theory and Practice of Logic Programming, 3(2), 2003, 223-242.