Top

Published in:

2017 | OriginalPaper | Chapter

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

Author : João Leite

Published in: Logic Programming and Nonmonotonic Reasoning

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter The Design of the Seventh Answer Set Programming Competition

next chapter Answer Set Programming and Its Applications in Planning and Multi-agent Systems

Available only for authorised users

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

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}\).

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

(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\).

Often, the term propositional variable is used synonymously.

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

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)

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)

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

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

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)

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)

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

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

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

10.

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

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)MathSciNetCrossRefMATH

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)MathSciNetCrossRefMATH

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

14.

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

15.

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

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

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 CrossRef

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

19.

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

20.

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

21.

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

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)MathSciNetCrossRefMATH

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)MathSciNetMATH

24.

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

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)

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 CrossRef

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)MathSciNetCrossRefMATH

28.

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

29.

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

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)

31.

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

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

33.

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

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)

35.

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

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 CrossRef

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)

38.

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

39.

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

40.

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

41.

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

42.

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

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 CrossRef

44.

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

45.

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

Title: A Bird’s-Eye View of Forgetting in Answer-Set Programming
Author: João Leite
Publisher: Springer International Publishing
Book: Logic Programming and Nonmonotonic Reasoning
Print ISBN: 978-3-319-61659-9

Electronic ISBN: 978-3-319-61660-5

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-61660-5_2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner