Top

Published in:

2017 | OriginalPaper | Chapter

Iterative Variable Elimination in ASP

Authors : Ricardo Gonçalves, Matthias Knorr, João Leite

Published in: Progress in Artificial Intelligence

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

In recent years, a large variety of approaches for forgetting in Answer Set Programming (ASP) have been proposed, in the form of specific operators, or classes of operators, following different principles and obeying different properties. A recent comprehensive overview of existing operators and properties provides a uniform picture of the landscape, including many novel results on relations between properties and operators. In this paper, we introduce four new properties not considered previously and show that these are indeed succinct and relevant additions providing novel results and insights, further strengthening established relations between existing operators. Most notably among these, the invariance to permutations of the order of forgetting a set of atoms iteratively raises interesting questions with surprising results.

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 haspie - A Musical Harmonisation Tool Based on ASP

next chapter Logic-Based Encodings for Ricochet Robots

\(\models \) is the standard consequence relation from classical logic.

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

Actually, classical negation can occur in scope of \(not\,\), but due to the restriction to consistent programs, this difference is of no effect [39], so we ignore it here.

Here, \(^+\) denotes the restriction to consistent programs.

It has been shown in [34] that SE-Forgetting [32] coincides with Semantic Strong Forgetting.

Without loss of generality, we consider HT-models instead of SE-models [41] as in [27].

We use the term postulate to follow [27] and ease readability. Technically, they are treated as every other property.

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

Liu, Y., Wen, X.: On the progression of knowledge in the situation calculus. In: Walsh, T. (ed.) Proceedings of IJCAI, pp. 976–982. IJCAI/AAAI (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)MathSciNetCrossRef

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

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

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

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

10.

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

11.

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

12.

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

13.

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_7CrossRef

14.

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_22CrossRef

15.

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

16.

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

17.

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

18.

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

19.

Leite, J.: A bird’s-eye view of forgetting in answer-set programming. In: Balduccini, M., Janhunen, T. (eds.) LPNMR 2017. LNCS, vol. 10377, pp. 10–22. Springer, Cham (2017). doi:10.1007/978-3-319-61660-5_2CrossRef

20.

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

21.

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

22.

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

23.

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

24.

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_29CrossRef

25.

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

26.

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

27.

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

28.

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)

29.

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

30.

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_29CrossRef

31.

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

32.

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)

33.

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

34.

Gonçalves, 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)

35.

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)

36.

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

37.

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

38.

Cabalar, P., Ferraris, P.: Propositional theories are strongly equivalent to logic programs. TPLP 7(6), 745–759 (2007)MathSciNetMATH

39.

Gelfond, M., Lifschitz, V.: Classical negation in logic programs and disjunctive databases. New Gener. Comput. 9(3–4), 365–385 (1991)CrossRef

40.

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

41.

Turner, H.: Strong equivalence made easy: nested expressions and weight constraints. TPLP 3(4–5), 609–622 (2003)MathSciNetMATH

42.

Truszczynski, M.: Reducts of propositional theories, satisfiability relations, and generalizations of semantics of logic programs. Artif. Intell. 174(16–17), 1285–1306 (2010)MathSciNetCrossRef

43.

Alferes, J.J., Knorr, M., Wang, K.: Forgetting under the well-founded semantics. In: Cabalar, P., Son, T.C. (eds.) LPNMR 2013. LNCS, vol. 8148, pp. 36–41. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40564-8_4CrossRef

44.

Knorr, M., Alferes, J.J., Hitzler, P.: Local closed world reasoning with description logics under the well-founded semantics. Artif. Intell. 175(9–10), 1528–1554 (2011)MathSciNetCrossRef

45.

Gonçalves, R., Alferes, J.J.: Parametrized logic programming. In: Janhunen, T., Niemelä, I. (eds.) JELIA 2010. LNCS, vol. 6341, pp. 182–194. Springer, Heidelberg (2010). doi:10.1007/978-3-642-15675-5_17CrossRef

46.

Slota, M., Leite, J., Swift, T.: On updates of hybrid knowledge bases composed of ontologies and rules. Artif. Intell. 229, 33–104 (2015)MathSciNetCrossRef

47.

Gonçalves, R., Knorr, M., Leite, J.: Evolving multi-context systems. In: Schaub, T., Friedrich, G., O’Sullivan, B. (eds.) Proceedings of ECAI, pp. 375–380. IOS Press (2014)

48.

Brewka, G., Ellmauthaler, S., Pührer, J.: Multi-context systems for reactive reasoning in dynamic environments. In: Schaub, T., Friedrich, G., O’Sullivan, B. (eds.) Proceedings of ECAI, pp. 159–164. IOS Press (2014)

49.

Gebser, M., Kaufmann, B., Kaminski, R., Ostrowski, M., Schaub, T., Schneider, M.T.: Potassco: the Potsdam answer set solving collection. AI Commun. 24(2), 107–124 (2011)MathSciNetMATH

50.

Ivanov, V., Knorr, M., Leite, J.: A query tool for \(\cal{EL}\) with non-monotonic rules. In: Alani, H., et al. (eds.) ISWC 2013. LNCS, vol. 8218, pp. 216–231. Springer, Heidelberg (2013). doi:10.1007/978-3-642-41335-3_14CrossRef

51.

Costa, N., Knorr, M., Leite, J.: Next step for NoHR: OWL 2 QL. In: Arenas, M., et al. (eds.) ISWC 2015. LNCS, vol. 9366, pp. 569–586. Springer, Cham (2015). doi:10.1007/978-3-319-25007-6_33CrossRef

52.

Lopes, C., Knorr, M., Leite, J.: NoHR: integrating XSB Prolog with the OWL 2 profiles and beyond. In: Balduccini, M., Janhunen, T. (eds.) LPNMR 2017. LNCS, vol. 10377, pp. 236–249. Springer, Cham (2017). doi:10.1007/978-3-319-61660-5_22CrossRefMATH

Title: Iterative Variable Elimination in ASP
Authors: Ricardo Gonçalves
Matthias Knorr
João Leite
Publisher: Springer International Publishing
Book: Progress in Artificial Intelligence
Print ISBN: 978-3-319-65339-6

Electronic ISBN: 978-3-319-65340-2

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-65340-2_53

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