Abstract
Logic programming under the stable model semantics has been extended to arbitrary formulas. A question of interest is how to characterize the property of well-supportedness, in the sense of Fages, which has been considered a cornerstone in answer set programming. In this paper, we address this issue by considering general logic programs, which consist of disjunctive rules with arbitrary propositional formulas in rule bodies. We define the justified stable semantics for these programs, propose a general notion of well-supportedness, and show the relationships between the two. We address the issue of computational complexity for various classes of general programs. Finally, we show that previously proposed well-supported semantics for aggregate programs and description logic programs are rooted in the justified stable semantics of general programs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P.F.: The Description Logic Handbook: Theory, Implementation and Applications. Cambridge University Press (2003)
Bartholomew, M., Lee, J., Meng, Y.: First-order extension of the flp stable model semantics via modified circumscription. In: Proc. IJCAI 2011, pp. 724–730 (2011)
Calimeri, F., Faber, W., Leone, N., Perri, S.: Declarative and computational properties of logic programs with aggregates. In: Proc. IJCAI 2005, Edinburgh, Scotland, UK, pp. 406–411. Professional Book Center (2005)
Chen, Y., Wan, H., Zhang, Y., Zhou, Y.: dl2asp: Implementing default logic via answer set programming. In: Proceedings 12th European Conference on Logics in Artificial Intelligence, pp. 104–116 (2010)
Dantsin, E., Eiter, T., Gottlob, G., Voronkov, A.: Complexity and expressive power of logic programming. ACM Computing Survey 33(3), 374–425 (2001)
Denecker, M., Marek, V.W., Truszczynski, M.: Ultimate approximation and its application in nonmonotonic knowledge representation systems. Information and Computation 192(1), 84–121 (2004)
Eiter, T., Gottlob, G.: On the computational cost of disjunctive logic programming: Propositional case. Annals of Mathematics and Artificial Intelligence 15(3-4), 289–323 (1995)
Eiter, T., Ianni, G., Lukasiewicz, T., Schindlauer, R., Tompits, H.: Combining answer set programming with description logics for the semantic web. Artifical Intelligence 172(12-13), 1495–1539 (2008)
Eiter, T., Ianni, G., Schindlauer, R., Tompits, H.: A uniform integration of higher-order reasoning and external evaluations in answer-set programming. In: Proc. IJCAI 2005, Edinburgh, Scotland, UK, pp. 90–96. Professional Book Center (2005)
Faber, W., Leone, N., Pfeifer, G.: Recursive Aggregates in Disjunctive Logic Programs: Semantics and Complexity. In: Alferes, J.J., Leite, J. (eds.) JELIA 2004. LNCS (LNAI), vol. 3229, pp. 200–212. Springer, Heidelberg (2004)
Faber, W., Pfeifer, G., Leone, N.: Semantics and complexity of recursive aggregates in answer set programming. Artificial Intelligence 175(1), 278–298 (2011)
Fages, F.: Consistency of clark’s completion and existence of stable models. Journal of Methods of Logic in Computer Science 1, 51–60 (1994)
Ferraris, P.: Answer Sets for Propositional Theories. In: Baral, C., Greco, G., Leone, N., Terracina, G. (eds.) LPNMR 2005. LNCS (LNAI), vol. 3662, pp. 119–131. Springer, Heidelberg (2005)
Ferraris, P., Lee, J., Lifschitz, V.: Stable models and circumscription. Artificial Intelligence 175(1), 236–263 (2011)
Gelfond, M., Lifschitz, V.: Classical negation in logic programs and disjunctive databases. New Generation Computing 9, 365–385 (1991)
Gottlob, G.: Complexity results for nonmonotonic logics. Journal of Logic and Computation 2(3), 397–425 (1992)
Lifschitz, V.: Twelve Definitions of a Stable Model. In: Garcia de la Banda, M., Pontelli, E. (eds.) ICLP 2008. LNCS, vol. 5366, pp. 37–51. Springer, Heidelberg (2008)
Lifschitz, V., Tang, L.R., Turner, H.: Nested expressions in logic programs. Annals of Mathematics and Artificial Intelligence 25(3-4), 369–389 (1999)
Liu, G., You, J.-H.: Lparse Programs Revisited: Semantics and Representation of Aggregates. In: Garcia de la Banda, M., Pontelli, E. (eds.) ICLP 2008. LNCS, vol. 5366, pp. 347–361. Springer, Heidelberg (2008)
Pelov, N., Denecker, M., Bruynooghe, M.: Well-founded and stable semantics of logic programs with aggregates. Theory and Practice of Logic Programming 7, 301–353 (2007)
Pelov, N., Denecker, M., Bruynooghe, M.: Partial Stable Models for Logic Programs with Aggregates. In: Lifschitz, V., Niemelä, I. (eds.) LPNMR 2004. LNCS (LNAI), vol. 2923, pp. 207–219. Springer, Heidelberg (2003)
Reiter, R.: A logic for default reasoning. Artificial Intelligence 13(1-2), 81–132 (1980)
Schwarz, G., Truszczynski, M.: Nonmonotonic reasoning is sometimes simpler! Journal of Logic and Computation 6(2), 295–308 (1996)
Shen, Y.-D.: Well-supported semantics for description logic programs. In: Proc. IJCAI 2011, IJCAI/AAAI, pp. 1081–1086, Barcelona, Spain (2011)
Shen, Y.-D., You, J.-H.: A Default Approach to Semantics of Logic Programs with Constraint Atoms. In: Erdem, E., Lin, F., Schaub, T. (eds.) LPNMR 2009. LNCS, vol. 5753, pp. 277–289. Springer, Heidelberg (2009)
Son, T.C., Pontelli, E.: A constructive semantic characterization of aggregates in answer set programming. Theory and Practice of Logic Programming 7, 355–375 (2007)
Son, T.C., Pontelli, E., Tu, P.H.: Answer sets for logic programs with arbitrary abstract constraint atoms. Journal of Artificial Intelligence Research 29, 353–389 (2007)
Truszczynski, M.: Modal interpretations of default logic. In: Proc. IJCAI 1991, pp. 393–398 (1991)
Truszczynski, M.: Reducts of propositional theories, satisfiability relations, and generalizations of semantics of logic programs. Artificial Intelligence 174(16-17), 1285–1306 (2010)
Van Gelder, A., Ross, K.A., Schlipf, J.S.: The well-founded semantics for general logic programs. J. ACM 38(3), 620–650 (1991)
You, J.-H., Yuan, L.-Y., Liu, G., Shen, Y.-D.: Logic Programs with Abstract Constraints: Representaton, Disjunction and Complexities. In: Baral, C., Brewka, G., Schlipf, J. (eds.) LPNMR 2007. LNCS (LNAI), vol. 4483, pp. 228–240. Springer, Heidelberg (2007)
Zhou, Y., Zhang, Y.: Progression semantics for disjunctive logic programs. In: Proc. AAAI 2011, pp. 286–291 (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
You, JH., Shen, YD., Wang, K. (2012). Well-Supported Semantics for Logic Programs with Generalized Rules. In: Erdem, E., Lee, J., Lierler, Y., Pearce, D. (eds) Correct Reasoning. Lecture Notes in Computer Science, vol 7265. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30743-0_39
Download citation
DOI: https://doi.org/10.1007/978-3-642-30743-0_39
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30742-3
Online ISBN: 978-3-642-30743-0
eBook Packages: Computer ScienceComputer Science (R0)