Level Mapping Induced Loop Formulas for Weight Constraint and Aggregate Logic Programs

• Autorzy: Liu G. , You J-H.
• Języki publikacji: EN

Abstrakty

EN

Level mapping and loop formulas are two different means to justify and characterize answer sets for normal logic programs. Both of them specify conditions under which a supported model is an answer set. Though serving a similar purpose, in the past the two have been studied largely in isolation with each other. In this paper, we study level mapping and loop formulas for weight constraint and aggregate (logic) programs. We show that, for these classes of programs, loop formulas can be devised from level mapping characterizations. First, we formulate a level mapping characterization of stable models and show that it leads to a new formulation of loop formulas for arbitrary weight constraint programs, without using any new atoms. This extends a previous result on loop formulas for weight constraint programs, where weight constraints contain only positive literals. Second, since aggregate programs are closely related to weight constraint programs, we further use level mapping to characterize the underlying answer set semantics based on which we formulate loop formulas for aggregate programs. The main result is that for aggregate programs not involving the inequality comparison operator, the dependency graphs can be built in polynomial time. This compares to the previously known exponential time method.

Słowa kluczowe

EN

logic programs; answer sets; weight constraints; aggregates; loop formulas

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 101, nr 3
• Strony: 237--255
• Opis fizyczny: Bibliogr. 32 poz.

Twórcy

autor

Liu G.

autor

You J-H.

• Department of Computing Science, University of Alberta, Edmonton, Canada,

Bibliografia

• [1] Clark, K. L.: Negation as failure, Logics and Databases, 1978, 293-322.
• [2] Dell'Armi, T., Faber, W., Lelpa, G., Leone, N.: Aggregate functions in disjunctive logic programming: semantics, complexity, and implementation in DLV, Proc. IJCAI'03, 2003.
• [3] Elkabani, I., Pontelli, E., Son, T.: SmodelsA - A system for computing answer sets of logic programs with aggregates, Proc. LPNMR'05, 2005.
• [4] Erdem, E., Lifschitz, V.: Tight Logic Programs, Theory and Practice of Logic Programming, 3(4), 2003, 499-518.
• [5] Faber, W., Leone, N., Pfeifer, G.: Recursive aggregates in disjunctive logic programs, Proc. JELIA'04, 2004.
• [6] Fages, F.: Consistency of Clark's completion and existence of stable models, Journal of Methods of Logic in Computer Science,1, 1994, 51-60.
• [7] Ferraris, P.: Answer sets for propositional theories, Proc. LPNMR'05, 2005.
• [8] Gebser, M., Kaufmann, B., Schaub, T.: The conflict-driven answer set solver clasp: progress report, Proc. LPNMR'09, 2009.
• [9] Gebser, M., Liu, L., Namasivayam, G., Neumann, A., Schaub, T., Truszczyński, M.: The first snswer set programming system competition, Proc. LPNMR'07, 2007.
• [10] Gelfond, M., Lifschitz, V.: The Stable Model Semantics for Logic Programming, Proc. 5th ICLP, 1988.
• [11] Giunchiglia, L., Lierler, Y., Maratea, M.: Cmodles-2: SAT-based answer set programming, Proc. AAAI'04, 2004.
• [12] Huang, G.-S., Jia, X., Liau, C.-J., You, J.-H.: Two-literal logic programs and satisfiability representation of stable models: A comparison, Proc. Canadian Artificial Intelligence, 2002.
• [13] Janhunen, T., Niemelä, I., Sevalnev, M.: Computing stable models via reductions to difference logic, Proc. LPNMR'09, 2009.
• [14] Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S., Scarcello, F.: The DLV system for knowledge representation and reasoning, ACM Transactions on Computational Logic, 7(3), 2006, 1-57.
• [15] Lin, F., Zhao, Y.: ASSAT: Computing answer sets of a logic programby SAT solvers, Artificial Intelligence, 157(1-2), 2004, 115-137.
• [16] Liu, G.: Level mapping induced loop formulas for weight constraint and aggregate programs, Proc. LPNMR' 09, 2009.
• [17] Liu, G., You, J.: Lparse programs revisited: semantics and representation of aggregates, Proc. ICLP'08, 2008.
• [18] Liu, L., Truszczyński, M.: Properties and applications of programs with monotone and convex constraints, Journal of Artificial Intelligence Research, 7, 2006, 299-334.
• [19] Marek, V., Niemelä, I., Truszczyński,M.: Logic programs with monotone abstract constraint atoms, Theory and Practice of Logic Programming, 8(2), 2007, 167-199.
• [20] Marek, V., Remmel, J. B.: Set constraints in logic programming, Proc. LPNMR'04, 2004.
• [21] Marek, V., Truszczyński,M.: Logic programs with abstract constraint atoms, Proc. AAAI'04, 2004.
• [22] Niemelä, I.: Stable models and difference logic, Ann. Math. Artif. Intell., 53(1-4), 2008, 313-329.
• [23] Niemelä, I., Simons, P., Soininen, T.: Stable model semantics of weight constraint rules, Proc. LPNMR'99, 1999.
• [24] Pelov, N., Denecker, M., Bruynooghe, M.: Well-founded and stable semantics of logic programs with aggregates, Theory and Practice of Logic Programming, 7, 2007, 301-353.
• [25] Shen, Y., You, J.: A generalized Gelfond-Lifschitz transformation for logic programs with abstract constraints, Proc. AAAI'07, 2007.
• [26] Simons, P., Niemelä, I., Soininen, T.: Extending and implementing the stable model semantics, Artificial Intelligence, 138(1-2), 2002, 181-234.
• [27] Soininen, T., Niemelä, I.: Developing a declarative rule language for applications in product configuration, Proc. PADL'99, 1999.
• [28] Son, T., Pontelli, E.: A constructive semantic characterization of aggregates in answer set programming, Theory and Practice of Logic Programming, 7, 2006, 355-375.
• [29] Son, T., Pontelli, E., Tu, P. H.: Answer sets for logic programs with arbitrary abstract constraint atoms, Journal of Artificial Intelligence Research, 29, 2007, 353-389.
• [30] Wang, Y., You, J., Yuan, L., Zhang, M.: Weight constraint programs with functions, Proc. LPNMR'09, 2009.
• [31] You, J., Liu, G.: Loop formulas for logic programs with arbitrary constraint atoms, Proc. AAAI'08, 2008.
• [32] You, J., Yuan, L., Zhang,M.: On the equivalence between answer sets and models of competioln for nested logic programs, Proc. IJCAI'03, 2003.