Nothing Special   »   [go: up one dir, main page]

Skip to main content

A Default Approach to Semantics of Logic Programs with Constraint Atoms

  • Conference paper
Logic Programming and Nonmonotonic Reasoning (LPNMR 2009)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 5753))

Abstract

We define the semantics of logic programs with (abstract) constraint atoms in a way closely tied to default logic. Like default logic, formulas in rules are evaluated using the classical entailment relation, so a constraint atom can be represented by an equivalent propositional formula. Therefore, answer sets are defined in a way closely related to default extensions. The semantics defined this way enjoys two properties generally considered desirable for answer set programming − minimality and derivability. The derivability property is very important because it guarantees free of self-supporting loops in answer sets. We show that when restricted to basic logic programs, this semantics agrees with the conditional-satisfaction based semantics. Furthermore, answer sets by the minimal-model based semantics can be recast in our approach. Consequently, the default approach gives a unifying account of the major existing semantics for logic programs with constraint atoms. This also makes it possible to characterize, in terms of the minimality and derivability properties, the precise relationship between them and contrast with others.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Marriott, K., Stuckey, P.: Programming with Constraints. MIT Press, Cambridge (1998)

    MATH  Google Scholar 

  2. Kemp, D., Stuckey, P.: Semantics of logic programs with aggregates. In: Proc. Int’l Symposium on Logic Programming, pp. 387–401. MIT Press, Cambridge (1991)

    Google Scholar 

  3. Calimeri, F., Faber, W., Leone, N., Perri, S.: Declarative and computational properties of logic programs with aggregates. In: IJCAI 2005, pp. 406–411 (2005)

    Google Scholar 

  4. 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)

    Chapter  Google Scholar 

  5. Faber, W., Pfeifer, G., Leone, N., Dell’Armi, T., Ielpa, G.: Design and implementation of aggregate functions in the dlv system. TPLP 8(5) (2008)

    Google Scholar 

  6. 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)

    Chapter  Google Scholar 

  7. Lee, J., Lifschitz, V., Palla, R.: A reductive semantics for counting and choice in answer set programming. In: AAAI 2008, pp. 472–479 (2008)

    Google Scholar 

  8. Liu, L., Truszczynski, M.: Properties and applications of programs with monotone and convex constraints. JAIR 7, 299–334 (2006)

    MathSciNet  MATH  Google Scholar 

  9. Liu, L., Pontelli, E., Son, T., Truszczynski, M.: Logic programs with abstract constraint atoms: the role of computations. In: Dahl, V., Niemelä, I. (eds.) ICLP 2007. LNCS, vol. 4670, pp. 286–301. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  10. Marek, V.W., Remmel, J.B.: Set constraints in logic programming. In: Lifschitz, V., Niemelä, I. (eds.) LPNMR 2004. LNCS (LNAI), vol. 2923, pp. 167–179. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  11. Marek, V.W., Truszczynski, M.: Logic programs with abstract constraint atoms. In: AAAI 2004, pp. 86–91 (2004)

    Google Scholar 

  12. Pelov, W., Denecker, M., Bruynooghe, M.: Well-founded and stable semantics of logic programs with aggregates. TPLP 7(3), 301–353 (2007)

    MathSciNet  MATH  Google Scholar 

  13. Shen, Y.D., You, J.H.: A generalized Gelfond-Lifschitz transformation for logic programs with abstract constraints. In: AAAI 2007, pp. 483–488 (2007)

    Google Scholar 

  14. Simons, P., Niemela, I., Soininen, T.: Extending and implementing the stable model semantics. Artificial Intelligence 138(1-2), 181–234 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  15. Son, T.C., Pontelli, E., Tu, P.H.: Answer sets for logic programs with arbitrary abstract constraint atoms. JAIR 29, 353–389 (2007)

    MathSciNet  MATH  Google Scholar 

  16. Reiter, R.: A logic for default reasoning. Artificial Intelligence 13, 81–132 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  17. Lifschitz, V., Pearce, D., Valverde, A.: Strongly equivalent logic programs. ACM Transactions on Computational Logic 2(4), 526–541 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  18. Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming. In: ICLP 1988, pp. 1070–1080 (1988)

    Google Scholar 

  19. Gelfond, M.: Answer sets. Handbook of Knowledge Representation. Elsevier, Amsterdam (2008)

    Google Scholar 

  20. van Gelder, A.: The alternating fixpoint of logic programs with negation. In: PODS, pp. 1–10 (1989)

    Google Scholar 

  21. Son, T.C., Pontelli, E.: A constructive semantic characterization of aggregates in answer set programming. TPLP 7(3), 355–375 (2007)

    MathSciNet  MATH  Google Scholar 

  22. Denecker, M., Pelov, N., Bruynooghe, M.: Ultimate well-founded and stable semantics for logic programs with aggregates. In: Codognet, P. (ed.) ICLP 2001. LNCS, vol. 2237, pp. 212–226. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  23. Liu, G.H., 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)

    Chapter  Google Scholar 

  24. 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)

    Chapter  Google Scholar 

  25. Denecker, M., Vennekens, J.: Building a knowledge base sysem for an integration of logic programmng and classical logic. In: ICLP 2009, pp. 71–76 (2009)

    Google Scholar 

  26. Eiter, T., Ianni, G., Lukasiewicz, T., Schindlauer, R., Tompits, H.: Combining answer set programming with description logics for the semantic web. Artif. Intell. 172(12-13), 1495–1539 (2008)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Shen, YD., You, JH. (2009). A Default Approach to Semantics of Logic Programs with Constraint Atoms. In: Erdem, E., Lin, F., Schaub, T. (eds) Logic Programming and Nonmonotonic Reasoning. LPNMR 2009. Lecture Notes in Computer Science(), vol 5753. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04238-6_24

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-04238-6_24

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-04237-9

  • Online ISBN: 978-3-642-04238-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics