Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A Bird’s-Eye View of Forgetting in Answer-Set Programming

  • Conference paper
  • First Online:
Logic Programming and Nonmonotonic Reasoning (LPNMR 2017)

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

Abstract

Forgetting is an operation that allows the removal, from a knowledge base, of middle variables no longer deemed relevant, while preserving all relationships (direct and indirect) between the remaining variables. When investigated in the context of Answer-Set Programming, many different approaches to forgetting have been proposed, following different intuitions, and obeying different sets of properties.

This talk will present a bird’s-eye view of the complex landscape composed of the properties and operators of forgetting defined over the years in the context of Answer-Set Programming, zooming in on recent findings triggered by the formulation of the so-called strong persistence, a property based on the strong equivalence between an answer-set program and the result of forgetting modulo the forgotten atoms, which seems to best encode the requirements of the forgetting operation.

The author was partially supported by FCT UID/CEC/04516/2013. This paper is substantially based on [1, 2].

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

Access this chapter

Log in via an institution

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 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.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

Similar content being viewed by others

Notes

  1. 1.

    See Appendix for definitions and notation on Answer-Set Programming.

  2. 2.

    Unless stated otherwise, \(\mathsf {F}\) is a class of forgetting operators, and \(\mathcal {C}\) the class of programs over \(\mathcal {A}\) of a given \(\mathsf {f}\in \mathsf {F}\).

  3. 3.

    An additional set of properties was introduced in [29]. The reader is referred to [36, 37] for a detailed discussion regarding these properties.

  4. 4.

    (SP) \(_{\langle P,V\rangle }\) is a restriction of property (SP) to specific forgetting instances. A forgetting operator \({\mathsf {f}}\) over \(\mathcal {C}\) satisfies (SP) \(_{\langle P,V\rangle }\) if \(\mathcal {AS}(\mathsf {f}(P,V)\cup R)=\mathcal {AS}(P\cup R)_{\parallel V}\), for all programs \(R\in \mathcal {C}\) with \(\mathcal {A}(R)\subseteq \mathcal {A}\setminus V\).

  5. 5.

    Often, the term propositional variable is used synonymously.

  6. 6.

    Extended logic programs [44] are actually more expressive, but this form is sufficient here.

References

  1. Goncalves, R., Knorr, M., Leite, J.: The ultimate guide to forgetting in answer set programming. In: Baral, C., Delgrande, J., Wolter, F. (eds.) Proceedings of KR, pp. 135–144. AAAI Press (2016)

    Google Scholar 

  2. Gonçalves, R., Knorr, M., Leite, J.: You can’t always forget what you want: on the limits of forgetting in answer set programming. In: Fox, M.S., Kaminka, G.A. (eds.) Proceedings of ECAI. IOS Press (2016)

    Google Scholar 

  3. European Parliament: General data protection regulation. Official Journal of the European Union L119/59, May 2016

    Google Scholar 

  4. Lin, F., Reiter, R.: How to progress a database. Artif. Intell. 92(1–2), 131–167 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  5. Liu, Y., Wen, X.: On the progression of knowledge in the situation calculus. In: Walsh, T. (ed.) Proceedings of IJCAI, IJCAI/AAAI, pp. 976–982 (2011)

    Google Scholar 

  6. Rajaratnam, D., Levesque, H.J., Pagnucco, M., Thielscher, M.: Forgetting in action. In: Baral, C., Giacomo, G.D., Eiter, T. (eds.) Proceedings of KR. AAAI Press (2014)

    Google Scholar 

  7. Lang, J., Liberatore, P., Marquis, P.: Propositional independence: formula-variable independence and forgetting. J. Artif. Intell. Res. (JAIR) 18, 391–443 (2003)

    MathSciNet  MATH  Google Scholar 

  8. Zhang, Y., Foo, N.Y.: Solving logic program conflict through strong and weak forgettings. Artif. Intell. 170(8–9), 739–778 (2006)

    Article  MathSciNet  Google Scholar 

  9. Eiter, T., Wang, K.: Semantic forgetting in answer set programming. Artif. Intell. 172(14), 1644–1672 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  10. Lang, J., Marquis, P.: Reasoning under inconsistency: a forgetting-based approach. Artif. Intell. 174(12–13), 799–823 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  11. Wang, Z., Wang, K., Topor, R.W., Pan, J.Z.: Forgetting for knowledge bases in DL-Lite. Ann. Math. Artif. Intell. 58(1–2), 117–151 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  12. Kontchakov, R., Wolter, F., Zakharyaschev, M.: Logic-based ontology comparison and module extraction, with an application to dl-lite. Artif. Intell. 174(15), 1093–1141 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  13. Konev, B., Ludwig, M., Walther, D., Wolter, F.: The logical difference for the lightweight description logic EL. J. Artif. Intell. Res. (JAIR) 44, 633–708 (2012)

    MATH  Google Scholar 

  14. Konev, B., Lutz, C., Walther, D., Wolter, F.: Model-theoretic inseparability and modularity of description logic ontologies. Artif. Intell. 203, 66–103 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  15. Lewis, C.I.: A survey of symbolic logic. University of California Press (1918). Republished by Dover (1960)

    Google Scholar 

  16. Bledsoe, W.W., Hines, L.M.: Variable elimination and chaining in a resolution-based prover for inequalities. In: Bibel, W., Kowalski, R. (eds.) CADE 1980. LNCS, vol. 87, pp. 70–87. Springer, Heidelberg (1980). doi:10.1007/3-540-10009-1_7

    Google Scholar 

  17. Larrosa, J.: Boosting search with variable elimination. In: Dechter, R. (ed.) CP 2000. LNCS, vol. 1894, pp. 291–305. Springer, Heidelberg (2000). doi:10.1007/3-540-45349-0_22

    Chapter  Google Scholar 

  18. Larrosa, J., Morancho, E., Niso, D.: On the practical use of variable elimination in constraint optimization problems: ‘still-life’ as a case study. J. Artif. Intell. Res. (JAIR) 23, 421–440 (2005)

    MATH  Google Scholar 

  19. Middeldorp, A., Okui, S., Ida, T.: Lazy narrowing: strong completeness and eager variable elimination. Theor. Comput. Sci. 167(1&2), 95–130 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  20. Moinard, Y.: Forgetting literals with varying propositional symbols. J. Log. Comput. 17(5), 955–982 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  21. Weber, A.: Updating propositional formulas. In: Expert Database Conference, pp. 487–500 (1986)

    Google Scholar 

  22. Alferes, J.J., Leite, J.A., Pereira, L.M., Przymusinska, H., Przymusinski, T.C.: Dynamic updates of non-monotonic knowledge bases. J. Logic Program. 45(1–3), 43–70 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  23. Eiter, T., Fink, M., Sabbatini, G., Tompits, H.: On properties of update sequences based on causal rejection. Theor. Pract. Logic Program. (TPLP) 2(6), 721–777 (2002)

    MathSciNet  MATH  Google Scholar 

  24. Sakama, C., Inoue, K.: An abductive framework for computing knowledge base updates. Theor. Pract. Logic Program. (TPLP) 3(6), 671–713 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  25. Slota, M., Leite, J.: Robust equivalence models for semantic updates of answer-set programs. In: Brewka, G., Eiter, T., McIlraith, S.A. (eds.) Proceeding of KR, pp. 158–168. AAAI Press (2012)

    Google Scholar 

  26. Slota, M., Leite, J.: A unifying perspective on knowledge updates. In: Cerro, L.F., Herzig, A., Mengin, J. (eds.) JELIA 2012. LNCS, vol. 7519, pp. 372–384. Springer, Heidelberg (2012). doi:10.1007/978-3-642-33353-8_29

    Chapter  Google Scholar 

  27. Delgrande, J.P., Schaub, T., Tompits, H., Woltran, S.: A model-theoretic approach to belief change in answer set programming. ACM Trans. Comput. Log. 14(2), 14 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  28. Slota, M., Leite, J.: The rise and fall of semantic rule updates based on SE-models. TPLP 14(6), 869–907 (2014)

    MathSciNet  MATH  Google Scholar 

  29. Wong, K.S.: Forgetting in Logic Programs. Ph.D. thesis, The University of New South Wales (2009)

    Google Scholar 

  30. Wang, Y., Zhang, Y., Zhou, Y., Zhang, M.: Forgetting in logic programs under strong equivalence. In: Brewka, G., Eiter, T., McIlraith, S.A. (eds.) Proceedings of KR, pp. 643–647. AAAI Press (2012)

    Google Scholar 

  31. Wang, Y., Wang, K., Zhang, M.: Forgetting for answer set programs revisited. In: Rossi, F. (ed.) Proceedings of IJCAI, IJCAI/AAAI (2013)

    Google Scholar 

  32. Knorr, M., Alferes, J.J.: Preserving strong equivalence while forgetting. In: Fermé, E., Leite, J. (eds.) JELIA 2014. LNCS, vol. 8761, pp. 412–425. Springer, Cham (2014). doi:10.1007/978-3-319-11558-0_29

    Google Scholar 

  33. Wang, Y., Zhang, Y., Zhou, Y., Zhang, M.: Knowledge forgetting in answer set programming. J. Artif. Intell. Res. (JAIR) 50, 31–70 (2014)

    MathSciNet  MATH  Google Scholar 

  34. Delgrande, J.P., Wang, K.: A syntax-independent approach to forgetting in disjunctive logic programs. In: Bonet, B., Koenig, S. (eds.) Proceedings of AAAI, pp. 1482–1488. AAAI Press (2015)

    Google Scholar 

  35. Zhang, Y., Zhou, Y.: Knowledge forgetting: properties and applications. Artif. Intell. 173(16–17), 1525–1537 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  36. Gonçalves, R., Knorr, M., Leite, J.: Forgetting in ASP: the forgotten properties. In: Michael, L., Kakas, A. (eds.) JELIA 2016. LNCS, vol. 10021, pp. 543–550. Springer, Cham (2016). doi:10.1007/978-3-319-48758-8_37

    Chapter  Google Scholar 

  37. Gonçalves, R., Knorr, M., Leite, J.: On some properties of forgetting in ASP. In: Booth, R., Casini, G., Klarman, S., Richard, G., Varzinczak, I.J. (eds.) Proceedings of the International Workshop on Defeasible and Ampliative Reasoning (DARe-16). CEUR Workshop Proceedings, vol. 1626. CEUR-WS.org (2016)

    Google Scholar 

  38. Brass, S., Dix, J.: Semantics of (disjunctive) logic programs based on partial evaluation. J. Log. Program. 40(1), 1–46 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  39. Wong, K.S.: Sound and complete inference rules for SE-consequence. J. Artif. Intell. Res. (JAIR) 31, 205–216 (2008)

    MathSciNet  MATH  Google Scholar 

  40. Eiter, T., Fink, M., Woltran, S.: Semantical characterizations and complexity of equivalences in answer set programming. ACM Trans. Comput. Log. 8(3) (2007)

    Google Scholar 

  41. Lifschitz, V.: What is answer set programming? In: Fox, D., Gomes, C.P. (eds.) Proceedings of AAAI, pp. 1594–1597. AAAI Press (2008)

    Google Scholar 

  42. Sagiv, Y.: Optimizing datalog programs. In: Minker, J. (ed.) Foundations of Deductive Databases and Logic Programming, pp. 659–698. Morgan Kaufmann (1988)

    Google Scholar 

  43. Eiter, T., Fink, M.: Uniform equivalence of logic programs under the stable model semantics. In: Palamidessi, C. (ed.) ICLP 2003. LNCS, vol. 2916, pp. 224–238. Springer, Heidelberg (2003). doi:10.1007/978-3-540-24599-5_16

    Chapter  Google Scholar 

  44. Lifschitz, V., Tang, L.R., Turner, H.: Nested expressions in logic programs. Ann. Math. Artif. Intell. 25(3–4), 369–389 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  45. Lifschitz, V., Pearce, D., Valverde, A.: Strongly equivalent logic programs. ACM Trans. Comput. Log. 2(4), 526–541 (2001)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

I would like to thank my close colleagues Ricardo Gonçalves and Matthias Knorr for all their dedication and contributions to our joint projects, turning it into a more fun and rewarding ride.

Author information

Authors and Affiliations

  1. NOVA LINCS & Departamento de Informática, Universidade Nova de Lisboa, Lisbon, Portugal

    João Leite

Authors
  1. João Leite
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to João Leite .

Editor information

Editors and Affiliations

  1. Drexel University, Philadelphia, Pennsylvania, USA

    Marcello Balduccini

  2. Aalto University, Espoo, Finland

    Tomi Janhunen

A Answer-Set Programming

A Answer-Set Programming

We assume a propositional signature \(\mathcal {A}\), a finite set of propositional atomsFootnote 5. An (extended) logic program P over \(\mathcal {A}\) is a finite set of (extended) rules of the form

$$\begin{aligned} a_1 \vee \ldots \vee a_k&\leftarrow b_1,..., b_l, not\,c_{1},..., not\,c_m, not\,not\,d_1,..., not\,not\,d_n \; , \end{aligned}$$
(1)

where all \(a_1,\ldots ,a_k,b_1,\ldots , b_l,c_{1},\ldots , c_m\), and \(d_{1},\ldots , d_n\) are atoms of \(\mathcal {A}\).Footnote 6 Such rules r are also commonly written in a more succinct way as

$$\begin{aligned} A \leftarrow B, not\,C, not\,not\,D \; , \end{aligned}$$
(2)

where we have \( A = \{a_1,\ldots ,a_k\}\), \( B =\{b_1,\ldots , b_l\}\), \( C =\{c_{1},\ldots , c_m\}\), \( D =\{d_{1},\ldots , d_n\}\), and we will use both forms interchangeably. By \(\mathcal {A}(P)\) we denote the set of atoms appearing in P. This class of logic programs, \(\mathcal {C}_{e}\), includes a number of special kinds of rules r: if \(n=0\), then we call r disjunctive; if, in addition, \(k\le 1\), then r is normal; if on top of that \(m=0\), then we call r Horn, and fact if also \(l=0\). The classes of disjunctive, normal and Horn programs, \(\mathcal {C}_{d}\), \(\mathcal {C}_{n}\), and \(\mathcal {C}_{H}\), are defined resp. as a finite set of disjunctive, normal, and Horn rules. We also call extended rules with \(k\le 1\) non-disjunctive, thus admitting a non-standard class \(\mathcal {C}_{nd}\), called non-disjunctive programs, different from normal programs. Given a program P and a set I of atoms, the reduct \(P^I\) is defined as \(P^I = \{ A \leftarrow B : r \text { of the form (2) in } P, C \cap I=\emptyset , D \subseteq I\}\).

An HT-interpretation is a pair \(\langle X,Y\rangle \) s.t. \(X\subseteq Y \subseteq \mathcal {A}\). Given a program P, an HT-interpretation \(\langle X,Y\rangle \) is an HT-model of P if \(Y\,\models \,P\) and \(X\,\models \,P^{Y}\), where \(\models \) denotes the standard consequence relation for classical logic. We admit that the set of HT-models of a program P are restricted to \(\mathcal {A}(P)\) even if \(\mathcal {A}(P)\subset \mathcal {A}\). We denote by \(\mathcal {HT}(P)\) the set of all HT-models of P. A set of atoms Y is an answer set of P if \(\langle Y,Y\rangle \in \mathcal {HT}(P)\), but there is no \(X\subset Y\) such that \(\langle X,Y\rangle \in \mathcal {HT}(P)\). The set of all answer sets of P is denoted by \(\mathcal {AS}(P)\). We say that two programs \(P_1, P_2\) are equivalent if \(\mathcal {AS}(P_1)=\mathcal {AS}(P_2)\) and strongly equivalent, denoted by \(P_1\equiv P_2\), if \(\mathcal {AS}(P_1\cup R)=\mathcal {AS}(P_2\cup R)\) for any \(R\in \mathcal {C}_{e}\). It is well-known that \(P_1\equiv P_2\) exactly when \(\mathcal {HT}(P_1)=\mathcal {HT}(P_2)\) [45]. We say that \(P'\) is an HT-consequence of P, denoted by \(P\,\models _\mathsf{HT}P'\), whenever \(\mathcal {HT}(P)\subseteq \mathcal {HT}(P')\). The V -exclusion of a set of answer sets (a set of HT-interpretations) \(\mathcal {M}\), denoted \(\mathcal {M}_{\parallel V}\), is \({\{X\backslash V\mid X\in \mathcal {M}\}}\) (\({\{\langle X\backslash V,Y\setminus V\rangle \mid \langle X,Y\rangle \in \mathcal {M}\}}\)). Finally, given two sets of atoms \(X,X'\subseteq \mathcal {A}\), we write \(X\sim _V X'\) whenever \(X \backslash V=X' \backslash V\).

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Cite this paper

Leite, J. (2017). A Bird’s-Eye View of Forgetting in Answer-Set Programming. In: Balduccini, M., Janhunen, T. (eds) Logic Programming and Nonmonotonic Reasoning. LPNMR 2017. Lecture Notes in Computer Science(), vol 10377. Springer, Cham. https://doi.org/10.1007/978-3-319-61660-5_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-61660-5_2

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-61659-9

  • Online ISBN: 978-3-319-61660-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation