×

zbMATH — the first resource for mathematics

RASP and ASP as a fragment of linear logic. (English) Zbl 1400.68047
Summary: RASP is a recent extension to Answer Set Programming (ASP) that permits declarative specification and reasoning on the consumption and production of resources. ASP can be seen as a particular case of RASP. In this paper, we study the relationship between linear logic and RASP problem specification. We prove that RASP programs can be translated into (a fragment of) linear logic, and vice versa. In doing so, we introduce a linear logic representation of default negation as understood in ASP. We are also able to establish a link between linear logic and here-and-there (HT) logic.

MSC:
68N17 Logic programming
03F52 Proof-theoretic aspects of linear logic and other substructural logics
68T27 Logic in artificial intelligence
Software:
ASP; RASP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Apt, K. R., & Bol, R. N. (1994). Logic programming and negation: A survey. The Journal of Logic Programming, 19/20, 9-71. · Zbl 0942.68518
[2] Baader, F, Calvanese, D, McGuinness, D, Nardi, D and Patel-Schneider, P. 2003. The description logic handbook, Cambridge: Cambridge University Press. · Zbl 1058.68107
[3] Baral, C. 2003. Knowledge representation, reasoning and declarative problem solving, Cambridge: Cambridge University Press. · Zbl 1056.68139
[4] Cerrito, S. 1992. A linear axiomatization of negation as failure. The Journal of Logic Programming, 12: 1-24. · Zbl 0754.68025
[5] Chintabathina, S., Gelfond, M., & Watson, R. (2007). Defeasible laws, parallel actions, and reasoning about resources. In E. Amir, V. Lifschitz, & R. Miller (Eds.), Proceedings of Commonsense’07, the 8th International Symposium on Logical For-malizations of Commonsense Reasoning, March 26-28 2007, Stanford University, California, USA. Menlo Park, CA: AAAI Press. (Technical, report SS-07-05).
[6] Costantini, S. 1995. Contributions to the stable model semantics of logic programs with negation. Theoretical Computer Science, 149: 231-255. · Zbl 0874.68193
[7] Costantini, S. 2006. On the existence of stable models of non-stratified logic programs. Theory and Practice of Logic Programming, 6: 169-212. · Zbl 1109.68027
[8] Costantini, S and Formisano, A. 2009. Modelling preferences and conditional preferences on resource consumption and production in ASP. Journal of Algorithms in Cognition, Informatics and Logic, 64: 3-15. · Zbl 1182.68037
[9] Costantini, S and Formisano, A. 2010. Answer set programming with resources. Journal of Logic and Computation, 20: 533-571. · Zbl 1200.68065
[10] Costantini, S., Formisano, A., & Pearce, D. (2012). Strong equivalence of RASP programs. In E. Erdem, J. Lee, Y. Lierler & D. Pearce (Eds.), Correct reasoning: Essays on logic-based AI in honour of Vladimir Lifschitz (pp. 149-163). Berlin: Springer. · Zbl 1357.68030
[11] Costantini, S, Formisano, A and Petturiti, D. 2010. Extending and implementing RASP. Fundamenta Informaticae, 105: 1-33. · Zbl 1211.68059
[12] Dantsin, E, Eiter, T, Gottlob, G and Voronkov, A. 2001. Complexity and expressive power of logic programming. ACM Computing Surveys, 33: 374-425.
[13] Dix, J. 1995. A classification theory of semantics of normal logic programs: I. Strong properties. Fundamenta Informaticae, 22: 227-255. · Zbl 0829.68021
[14] Dix, J. 1995. A classification theory of semantics of normal logic programs: II. Weak properties. Fundamenta Informaticae, 22: 257-288. · Zbl 0829.68022
[15] Dovier, A, Formisano, A and Pontelli, E. 2009. An empirical study of constraint logic programming and answer set programming solutions of combinatorial problems. Journal of Experimental & Theoretical Artificial Intelligence, 21: 79-121. · Zbl 1193.68073
[16] Gelfond, M., & Lifschitz, V. (1988). The stable model semantics for logic programming. In R. Kowalski & K. Bowen (Eds.), Logic Programming, proceedings of the Fifth International Conference and Symposium, Seattle, Washington, August 15-19, 1988 (pp. 1070-1080). Cambridge, MA: The MIT Press.
[17] Gelfond, M., & Lifschitz, V. (1991). Classical negation in logic programs and disjunctive databases. New Generation Computing, 9, 365-385. · Zbl 0735.68012
[18] Gelfond, M and Lifschitz, V. 1998. Action languages. Electronic Transactions on AI, 2: 193-210.
[19] Girard, J-Y. 1987. Linear logic. Theoretical Computer Science, 50: 1-102. · Zbl 0625.03037
[20] Girard, J.-Y. (1995). Linear logic: Its syntax and semantics. In J.-Y. Girard, Y. Lafont & L. Regnier (Eds.), Advances in linear logic (pp. 1-42). Cambridge: Cambridge University Press. · Zbl 0828.03003
[21] Harland, J., Pym, D. J., & Winikoff, M. (1995). Programming in Lygon: A brief overview. In John W. Lloyd (Ed.), Logic Programming, proceedings of the 1995 International Symposium, December 4-7, 1995, Portland, Oregon (p. 636). Cambridge, MA: MIT Press.
[22] Hodas, J. S., & Miller, D. (1994). Logic programming in a fragment of intuitionistic linear logic. Information and Computation, 110, 327-365. · Zbl 0807.68016
[23] Kanovich, MI. 1994. The complexity of Horn fragments of linear logic. Annals of Pure and Applied Logic, 69: 195-241. · Zbl 0812.03007
[24] Lifschitz, V. (2008). Twelve definitions of a stable model. In M. Garcia de la Banda & E. Pontelli (Eds.), Logic Programming, 24th International Conference, ICLP 2008, Udine, Italy, December 9-13 2008, proceedings (pp. 37-51). Berlin: Springer. · Zbl 1185.68166
[25] Lifschitz, V, Pearce, D and Valverde, A. 2001. Strongly equivalent logic programs. ACM Transactions on Computational Logic, 2: 526-541. · Zbl 1365.68149
[26] Lincoln, P. 1992. Linear logic. ACM SIGACT News, 23(2): 29-37.
[27] Lincoln, P, Mitchell, JC, Scedrov, A and Shankar, N. 1990. Decision problems for propositional linear logic. Annals of Pure and Applied Logic, 56: 239-311. · Zbl 0768.03003
[28] Lloyd, JW. 1987. Foundations of logic programming, Berlin: Springer.
[29] Miller, D. (2004). Overview of linear logic programming. In T. Ehrhard, J.-Y. Girard, P. Ruet, and P. Scott (Eds.), Linear Logic in Computer Science, London Mathematical Society Lecture Note Vol. 316 (pp. 119-150). Cambridge: Cambridge University Press. · Zbl 1079.03019
[30] Niemelä I., Simons, P., & Soininen, T. (1999). Stable model semantics of weight constraint rules. In M. Gelfond, N. Leone, & G. Pfeifer (Eds.), Logic Programming and Nonmonotonic Reasoning, 5th International Conference, LPNMR’99, El Paso, Texas, USA, December 2-4, 1999, proceedings (pp. 317-331). Berlin:Springer. · Zbl 0952.68029
[31] Osorio, M., Arrazola-Ramírez, J. R., & Palacios-Pérez, J. J. (2002). Towards a framework for answer set programming as provability in linear logic. In J. B. Diaz (Ed.), Proceedings of the First IDEIA Workshop (in conjunction with IBERAMIA 2002), Sevilla, Spain (pp. 121-131). Berlin: Springer.
[32] Palacios-Pérez, J. J. (2006). On strong negation as linear duality. In M. Osorio, C. Zepeda, P. Pozos-Parra, & G. DeIta-Luna (Eds.), Latin-American Workshop on Non-Monotonic Reasoning, proceedings of the LA-NMR06 Workshop, Facultad de Ingeniería de la Universidad Auónoma de San Luis Potí, San Luis Potosí, Mexico, September 18, 2006. Tilburg: CEUR-WS.org. (Retrieved, 20 April 2013, from http://www.ceur-ws.org/Vol-217/p4.pdf)
[33] Pearce, D. (1997). A new logical characterization of stable models and answer sets. In J. Dix, L. M. Pereira & T. C. Przymusinski (Eds.), Non-Monotonic Extensions of Logic Programming, NMELP ’96, Bad Honnef, Germany, September 5-6, 1996, selected papers (pp. 55-70). Berlin: Springer.
[34] Pym, DJ and Harland, J. 1994. A uniform proof-theoretic investigation of linear logic programming. Journal of Logic and Computation, 4: 175-207. · Zbl 0797.03054
[35] Scedrov, A. (1993). A brief guide to linear logic. In G. Paun, G. Rozenburg, & A. Salomaa (Eds.), Current trends in theoretical computer science (pp. 377-394). Singapore: World Scientific. (Also published in (1990). EATCS, Bulletin, 41, 154-165.). · Zbl 0755.03005
[36] Scedrov, A. (1995). Linear logic and computation: A survey. In H. Schwichtenberg (Ed.), Proof and computation (pp. 379-395). Berlin: Springer. · Zbl 0828.03004
[37] Soininen, T and Niemelä, I. 1999. “Developing a declarative rule language for applications in product configuration”. In Practical Aspects of Declarative Languages, First International Workshop, PADL ’99, San Antonio, Texas, USA, January 18-19, 1999, proceedings, Edited by: Gupta, G. 305-319. Berlin: Springer.
[38] Soininen, T., Niemelä, I., Tiihonen, J., & Sulonen, R. (2001). Representing configuration knowledge with weight constraint rules. In A. Provetti & T. C. Son (Eds.), Answer Set Programming, Towards Eficient and Scalable Knowledge Representation and Reasoning, proceedings of the 1st Intl. ASP’01 Workshop, Stanford, March 26-28, 2001. Menlo Park, CA: AAAI Press. (Technical, report SS-01-01).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.