Normal Form Nested Programs

• Autorzy: Bria A. , Faber W. , Leone N.
• Języki publikacji: EN

Abstrakty

EN

Disjunctive logic programming under the answer set semantics (DLP, ASP) has been acknowledged as a versatile formalism for knowledge representation and reasoning during the last decades. Lifschitz, Tang, and Turner have introduced an extended language of DLP, called Nested Logic Programming (NLP), in 1999 [12]. It often allows for more concise representations by permitting a richer syntax in rule heads and bodies. However, that language is propositional and thus does not allow for variables, one of the strengths of DLP. In this paper, we introduce a language similar to NLP, called Normal Form Nested (NFN) programs, which does allow for variables, and present the syntax and semantics. However, with the introduction of variables an important issue arises: domain independence, the question of whether the semantics of a program is independent of the considered domain (given that it is sufficiently rich). Domain independence, originally studied for logic-based database query languages, is desirable because it guarantees that the semantics remains equal if unrelated information is added and also ensures finiteness of intended models even if infinite domains are considered. With the presence of variables, NFN programs in general are not domain independent. We study this issue in depth and define the class of safe NFN programs, which are guaranteed to be domain independent. Moreover, we show that for those NFN programs, which are also NLPs, our semantics coincides with the one of [12], while keeping the standard meaning of answer sets on DLP programs with variables. We also show that our semantics coincides with Herbrand stable models as defined in [6] of formulas corresponding to NFN programs. Finally, we provide an algorithm which transforms NFN programs into DLP programs in a correct and efficient way. We have implemented this algorithm, which provides an effective implementation of the NFN language, using existing DLP systems as a back-end.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 96, nr 3
• Strony: 271--295
• Opis fizyczny: Bibliogr. 16 poz., tab.

Twórcy

autor

Bria A.

autor

Faber W.

autor

Leone N.

• Department of Mathematics University of Calabria, Italy Via P. Bucci, cubo 30b, 87036 Rende (CS), Italy,

Bibliografia

• [1] Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases, 1995.
• [2] Baral, C.: Knowledge Representation, Reasoning and Declarative Problem Solving, Cambridge University Press, 2003, ISBN 0-52181802-8.
• [3] Bertossi, L. E.: Consistent query answering in databases, SIGMOD Record, 35(2), 2006, 68-76.
• [4] Eiter, T., Gottlob, G., Mannila, H.: Disjunctive Datalog, ACM TODS, 22(3), 1997, 364-418.
• [5] Faber, W., Leone, N., Pfeifer, G.: Recursive Aggregates in Disjunctive Logic Programs: Semantics and Complexity, JELIA 2004 (J. J. Alferes, J. Leite, Eds.), 3229, 2004.
• [6] Ferraris, P., Lee, J., Lifschitz, V.: A New Perspective on Stable Models, Twentieth International Joint Conference on Artificial Intelligence (IJCAI-07), 2007.
• [7] Gelfond, M., Lifschitz, V.: Classical Negation in Logic Programs and Disjunctive Databases, NGC, 9, 1991, 365-385.
• [8] Janhunen, T., Niemelä, I.: GNT - A Solver for Disjunctive Logic Programs, LPNMR-7 (V. Lifschitz, I. Niemelä, Eds.), 2923, 2004, ISBN 3-540-20721-X.
• [9] Lee, J., Lifschitz, V., Palla, R.: Safe Formulas in the General Theory of Stable Models (Preliminary Report), Proceedings of the 24th International Conference on Logic Programming (ICLP 2008), 5366, 2008.
• [10] Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S., Scarcello, F.: The DLV System for Knowledge Representation and Reasoning, ACM TOCL, 7(3), 2006, 499-562.
• [11] Lierler, Y.: Disjunctive Answer Set Programming via Satisfiability, LPNMR'05 (C. Baral, G. Greco, N. Leone, G. Terracina, Eds.), 3662, 2005, ISBN 3-540-28538-5.
• [12] Lifschitz, V., Tang, L. R., Turner, H.: Nested Expressions in Logic Programs, AMAI, 25(3-4), 1999, 369-389.
• [13] Pearce, D., Sarsakov, V., Schaub, T., Tompits, H., Woltran, S.: A Polynomial Translation of Logic Programs with Nested Expressions into Disjunctive Logic Programs: Preliminary Report, ICLP 2002, 2401, 2002.
• [14] Plaisted, D. A., Greenbaum, S.: A Structure-Preserving Clause Form Translation, Journal of Symbolic Computation, 2(3), 1986, 293-304.
• [15] Przymusinski, T. C.: Stable Semantics for Disjunctive Programs, NGC, 9, 1991, 401-424.
• [16] Stewart, I. A.: Complete Problems Involving Boolean Labelled Structures and Projection Transactions, Journal of Logic and Computation, 1(6), 1991, 861-882.