Negation as a Resource: a Novel View on Answer Set Semantics

• Autorzy: Costantini S. , Formisano A.

Identyfikatory

DOI

10.3233/FI-2015-1255

• Konferencja: Italian Conference on Computational Logic, CILC 2013, (25-27.09.2013; Catania, Italy)
• Języki publikacji: EN

Abstrakty

EN

In recent work, we provided a formulation of ASP programs in terms of linear logic theories. Answer sets were characterized in terms of maximal tensor conjunctions provable from such theories. In this paper, we propose a full comparison between Answer Set Semantics and its variation obtained by interpreting literals (including negative literals) as resources, which leads to a different interpretation of negation. We argue that this novel view can be of both theoretical and practical interest, and we propose a modified Answer Set Semantics that we call Resource-based Answer Set Semantics. An advantage is that of avoiding inconsistencies, as every program has a (possibly empty) resource-based answer set. This implies however the introduction of a different way of representing constraints. We provide a characterization of the new semantics as a variation of the answer set semantics, and also in terms of Autoepistemic Logic. The latter characterization leads to a way of computing resource-based answer set via answer set solvers.

Słowa kluczowe

EN

answer set programming; default negation; linear logic; autoepistemic logic

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 140, nr 3/4
• Strony: 279--305
• Opis fizyczny: Bibliogr. 48 poz.

Twórcy

autor

Costantini S.

• DISIM, Universit`a di L’Aquila, Italy

autor

Formisano A.

• DMI, Universit`a di Perugia, Italy

Bibliografia

• [1] Apt, K. R., Bol, R. N.: Logic Programming and Negation: A Survey, Journal of Logic Programming, 19/20, 1994, 9–71.
• [2] Baral, C.: Knowledge representation, reasoning and declarative problem solving, Cambridge University Press, 2003.
• [3] Brewka, G., Niemelä, I., Truszczyński, M.: Answer Set Optimization, IJCAI-03, Proc. of the Eighteenth Intl. Joint Conference on Artificial Intelligence (G. Gottlob, T. Walsh, Eds.), Morgan Kaufmann, 2003.
• [4] Cerrito, S.: A Linear Axiomatization of Negation as Failure, Journal of Logic Programming, 12(1&2), 1992, 1–24.
• [5] Cholewinski, P., Truszczyński, M.: Extremal Problems in Logic Programming and Stable Model Computation, Journal of Logic Programming, 38(2), 1999, 219–242.
• [6] Costantini, S.: Contributions to the Stable Model Semantics of Logic Programs with Negation, Theoretical Computer Science, 149(2), 1995, 231–255.
• [7] Costantini, S.: On the existence of stable models of non-stratified logic programs, Theory and Practice of Logic Programming, 6(1-2), 2006.
• [8] Costantini, S., Formisano, A.: Modeling preferences and conditional preferences on resource consumption and production in ASP, Journal of Algorithms in Cognition, Informatics and Logic, 64(1), 2009, 3–15.
• [9] Costantini, S., Formisano, A.: Answer Set Programming with Resources, Journal of Logic and Computation, 20(2), 2010, 533–571.
• [10] Costantini, S., Formisano, A.: Augmenting Weight Constraints with Complex Preferences, AAAI Spring Symposium: Logical Formalizations of Commonsense Reasoning, AAAI Press, 2011, Tech. report SS-11-06.
• [11] Costantini, S., Formisano, A.: Weight Constraints with Preferences in ASP, Proc. of Intl. Conf. on Logic Programming and Nonmonotonic Reasoning LPNMR’11, 6645, Springer-Verlag, 2011.
• [12] Costantini, S., Formisano, A.: Negation as a Resource: A Novel View on Answer Set Semantics, Logic Programming and Nonmonotonic Reasoning, 12th International Conference, LPNMR 2013 (P. Cabalar, T. C. Son, Eds.), 8148, Springer, 2013.
• [13] Costantini, S., Formisano, A.: Nested Weight Constraints in ASP, Fundamenta Informaticae, 124(4), 2013, 449–464.
• [14] Costantini, S., Formisano, A.: RASP and ASP as a Fragment of Linear Logic, Journal of Applied Non-Classical Logics (JANCL), 23(1-2), 2013, 49–74, Special Issue on Equilibrium Logic and Answer Set Programming in Honor of David Pearce.
• [15] Costantini, S., Formisano, A.: Query Answering in Resource-Based Answer Set Semantics, Proceedings of the 7thWorkshop on Answer Set Programming and Other Computing Paradigms ASPOCP 2014 (D. Inclezan, M. Maratea, Eds.), 2014.
• [16] Costantini, S., Formisano, A., Petturiti, D.: Extending and Implementing RASP, Fundamenta Informaticae, 105(1-2), 2010, 1–33.
• [17] Dantsin, E., Eiter, T., Gottlob, G., Voronkov, A.: Complexity and Expressive Power of Logic Programming, ACM Computing Surveys, 33(3), 2001, 374–425.
• [18] Dix, J.: A Classification Theory of Semantics of Normal Logic Programs I-II., Fundamenta Informaticae, 22(3), 1995, 227–255 and 257–288.
• [19] Gebser, M., Gharib, M., Mercer, R. E., Schaub, T.: Monotonic Answer Set Programming, Journal of Logic Computation, 19(4), 2009, 539–564.
• [20] Gelfond, M.: On Stratified Autoepistemic Theories, AAAI, Proceedings of the 6th National Conference on Artificial Intelligence (K. D. Forbus, H. E. Shrobe, Eds.), 1987.
• [21] Gelfond,M.: Answer Sets, in: Handbook of Knowledge Representation. Chapter 7, Elsevier, 2007.
• [22] Gelfond,M., Lifschitz, V.: The Stable Model Semantics for Logic Programming, Proc. of the 5th Intl. Conf. and Symposium on Logic Programming (R. Kowalski, K. Bowen, Eds.), MIT Press, 1988.
• [23] Gelfond, M., Lifschitz, V.: Classical negation in logic programs and disjunctive databases, New Generation Computing, 9, 1991, 365–385.
• [24] Girard, J.-Y.: Linear Logic, Theoretical Computer Science, 50, 1987, 1–102.
• [25] Hughes, G., Cresswell, M.: A companion to modal logic, Methuen and Co. Ltd., London, 1984.
• [26] Kanovich,M. I.: The Complexity of Horn Fragments of Linear Logic, Ann. Pure Appl. Logic, 69(2-3), 1994, 195–241.
• [27] Konolige, K.: On the Relation Between Default and Autoepistemic Logic, Artif. Intell., 35(3), 1988, 343–382.
• [28] Leone, N.: Logic Programming and Nonmonotonic Reasoning: From Theory to Systems and Applications, Logic Programming and Nonmonotonic Reasoning, 9th Intl. Conference, LPNMR 2007 (C. Baral, G. Brewka, J. Schlipf, Eds.), 2007.
• [29] Lifschitz, V.: Twelve Definitions of a StableModel, Proc. of the 24th Intl. Conference on Logic Programming (M. Garcia de la Banda, E. Pontelli, Eds.), 5366, Springer, 2008.
• [30] Lifschitz, V., Turner, H.: Splitting a Logic Program, Proc. of ICLP’94, Intl. Conference on Logic Programming, 1994.
• [31] Lin, F., Zhao, X.: On Odd and Even Cycles in Normal Logic Programs, Proceedings of the Nineteenth National Conference on Artificial Intelligence AAAI 2004 (D. L. McGuinness, G. Ferguson, Eds.), AAAI Press / The MIT Press, 2004.
• [32] Lloyd, J. W.: Foundations of Logic Programming, Springer-Verlag, 1987.
• [33] Marek, V. W., Truszczyński,M.: Autoepistemic Logic, Journal of the ACM, 38(3), 1991, 587–618.
• [34] Marek, V. W., Truszczyński, M.: Nonmonotonic logic, context-dependent reasoning, Artificial intelligence, Springer, 1993.
• [35] Marek, V. W., Truszczyński, M.: Reflective Autoepistemic Logic and Logic Programming, LPNMR, Logic Programming and Non-monotonic Reasoning, Proceedings of the Second International Workshop (A. Nerode, L. M. Pereira, Eds.), The MIT Press, 1993.
• [36] Marek, V. W., Truszczynski, M.: Stable models and an alternative logic programming paradigm, in: The Logic Programming Paradigm: A 25-Year Perspective (K. R. Apt, D. S. Warren, M. Truszczynski, Eds.), 1st edition, Springer, 1999, ISBN 3540654631.
• [37] McCarthy, J.: Elaboration tolerance, Proc. of Commonsense’98, 1998, Available at http://wwwformal.stanford.edu/jmc/ elaboration.html.
• [38] Niemelä, I., Simons, P., Soininen, T.: Stable model semantics of weight constraint rules, Proc. of the 5th Intl. Conference on Logic Programming and Nonmonotonic Reasoning LPNMR’99, number 1730 in LNAI, Springer-Verlag, 1999.
• [39] Osorio, M., López, A.: Expressing the Stable Semantics in Terms of the Pstable Semantics, Proc. of the LoLaCOM06 Workshop, 220, CEUR-WS.org, 2006.
• [40] Osorio, M., Pérez, J. A. N., Ramírez, J. R. A., Macías, V. B.: Logics with Common Weak Completions, Journal of Logic Computation, 16(6), 2006, 867–890.
• [41] Pereira, L.M., Pinto, A.M.: Revised StableModels - A Semantics for Logic Programs, Progress in Artificial Intelligence, Proc. of EPIA 2005 (C. Bento, A. Cardoso, G. Dias, Eds.), 3808, Springer, 2005.
• [42] Pereira, L. M., Pinto, A. M.: Tight Semantics for Logic Programs, Tech. Comm. of the 26th Intl. Conference on Logic Programming, ICLP 2010 (M. V. Hermenegildo, T. Schaub, Eds.), 7, 2010.
• [43] Schwarz, G.: Autoepistemic Logic of Knowledge, LPNMR, Logic Programming and Non-monotonic Reasoning, Proceedings of the First InternationalWorkshop (A. Nerode, V. Subrahmanian, Eds.), TheMIT Press, 1991.
• [44] Schwarz, G.: Reflexive Autoepistemic Logic, Fundamenta Informaticae, 17(1-2), 1992, 157–173.
• [45] Simons, P., Niemelä, I., Soininen, T.: Extending and Implementing the Stable Model Semantics, Artificial Intelligence, 138(1-2), 2002, 181–234.
• [46] Truszczyński,M.: Logic Programming for Knowledge Representation, Logic Programming, 23rd Intl. Conference, ICLP 2007 (V. Dahl, I. Niemelä, Eds.), 2007.
• [47] Van Gelder, A., Ross, K. A., Schlipf, J. S.: The Well-Founded Semantics for General Logic Programs, Journal of the ACM, 38(3), 1991, 620–650.
• [48] Web references of ASP solvers: Clasp: potassco.sourceforge.net; Cmodels: www.cs.utexas.edu/users/tag/cmodels; DLV: www.dbai.tuwien.ac.at/proj/dlv; Smodels: www.tcs.hut.fi/Software/smodels.