Abstract
We present a method for forgetting concept symbols in ontologies specified in the description logic \(\mathcal {ALCOI}\). The method is an adaptation and improvement of a second-order quantifier elimination method developed for modal logics and used for computing correspondence properties for modal axioms. It follows an approach exploiting a result of Ackermann adapted to description logics. An important feature inherited from the modal approach is that the inference rules are guided by an ordering compatible with the elimination order of the concept symbols. This provides more control over the inference process and reduces non-determinism, resulting in a smaller search space. The method is extended with a new case splitting inference rule, and several simplification rules. Compared to related forgetting and uniform interpolation methods for description logics, the method can handle inverse roles, nominals and ABoxes. Compared to the modal approach on which it is based, it is more efficient in time and improves the success rates. The method has been implemented in Java using the OWL API. Experimental results show that the order in which the concept symbols are eliminated significantly affects the success rate and efficiency.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ackermann, W.: Untersuchungen \(\ddot{u}\)ber das Eliminationsproblem der mathematischen Logik. Mathematische Annalen 110(1), 390–413 (1935)
Bachmair, L., Ganzinger, H., Waldmann, U.: Refutational theorem proving for hierarchic first-order theories. Applicable Algebra in Engineering, Communication and Computing 5(3–4), 193–212 (1994)
Conradie, W., Goranko, V., Vakarelov, D.: Algorithmic correspondence and completeness in modal logic. I. The core algorithm SQEMA. Logical Methods in Computer Science 2(1) (2006)
Grau, B.C., Motik, B.: Reasoning over ontologies with hidden content: The importby-query approach. Journal of Artificial Intelligence Research 45, 197–255 (2012)
Doherty, P., Łukaszewicz, W., Szałas, A.: Computing circumscription revisited: A reduction algorithm. Journal of Automated Reasoning 18(3), 297–336 (1997)
Doherty, P., Łukaszewicz, W., Szałas, A.: General domain circumscription and its effective reductions. Fundamenta Informaticae 36(1), 23–55 (1998)
Gabbay, D.M., Ohlbach, H.J.: Quantifier elimination in second-order predicate logic. In: Principles of Knowledge Representation and Reasoning (KR92), pp. 425–435. Morgan Kaufmann (1992)
Gabbay, D.M., Schmidt, R.A., Szałas, A.: Second Order Quantifier Elimination: Foundations, Computational Aspects and Applications. College Publications (2008)
Goranko, V., Hustadt, U., Schmidt, R.A., Vakarelov, D.: SCAN is complete for all Sahlqvist formulae. In: Berghammer, R., Möller, B., Struth, G. (eds.) RelMiCS 2003. LNCS, vol. 3051, pp. 149–162. Springer, Heidelberg (2004)
Konev, B., Lutz, C., Walther, D., Wolter, F.: Model-theoretic inseparability and modularity of description logic ontologies. Artificial Intelligence 203, 66–103 (2013)
Konev, B., Walther, D., Wolter, F.: Forgetting and uniform interpolation in extensions of the description logic \(\cal EL\). In: Proceedings of the 22nd International Workshop on Description Logics (DL 2009). CEUR Workshop Proceedings, vol. 477. CEUR-WS.org (2009)
Koopmann, P., Schmidt, R.A.: Forgetting concept and role symbols in \(\cal ALCH\)-ontologies. In: McMillan, K., Middeldorp, A., Voronkov, A. (eds.) LPAR 2013. LNCS, vol. 8312, pp. 552–567. Springer, Heidelberg (2013)
Koopmann, P., Schmidt, R.A.: Implementation and evaluation of forgetting in ALC-ontologies. In: Proceedings of the 7th International Workshop on Modular Ontologies (WoMo 2013). CEUR Workshop Proceedings, vol. 1081, pp. 1–12. CEUR-WS.org (2013)
Koopmann, P., Schmidt, R.A.: Uniform interpolation of \(\cal ALC\)-ontologies using fixpoints. In: Fontaine, P., Ringeissen, C., Schmidt, R.A. (eds.) FroCoS 2013. LNCS, vol. 8152, pp. 87–102. Springer, Heidelberg (2013)
Koopmann, P., Schmidt, R.A.: Count and forget: uniform interpolation of \(\cal SHQ\)-ontologies. In: Demri, S., Kapur, D., Weidenbach, C. (eds.) IJCAR 2014. LNCS, vol. 8562, pp. 434–448. Springer, Heidelberg (2014)
Koopmann, P., Schmidt, R.A.: LETHE: A saturation-based tool for non-classical reasoning (2015). Manuscript, submitted
Koopmann, P., Schmidt, R.A.: Saturated-based forgetting in the description logic SIF. In: Proceedings of the 28th International Workshop on Description Logics (DL 2015). CEUR Workshop Proceedings, vol. 1350. CEUR-WS.org (2015)
Koopmann, P., Schmidt, R.A.: Uniform interpolation and forgetting for \(\cal ALC\)-ontologies with ABoxes. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, pp. 175–181. AAAI Press (2015)
Ludwig, M., Konev, B.: Towards practical uniform interpolation and forgetting for \(\cal ALC\) TBoxes. In: Proceedings of the 26th International Workshop on Description Logics (DL 2013). CEUR Workshop Proceedings, vol. 1014, pp. 377–389. CEUR-WS.org (2013)
Lutz, C., Seylan, I., Wolter, F.: An automata-theoretic approach to uniform interpolation and approximation in the description logic \(\cal EL\). In: Principles of Knowledge Representation and Reasoning: KR 2012, pp. 286–297. AAAI Press (2012)
Lutz, C., Wolter, F.: Foundations for uniform interpolation and forgetting in expressive description logics. In: Proceedings of IJCAI 2011, pp. 989–995. IJCAI/AAAI (2011)
Nikitina, N.: Forgetting in general \(\cal EL\) terminologies. In: Proceedings of the 24th International Workshop on Description Logics (DL 2011). CEUR Workshop Proceedings, vol. 745. CEUR-WS.org (2011)
Nonnengart, A., Szałas, A.: A fixpoint approach to second-order quantifier elimination with applications to correspondence theory. In: Orlowska, E. (ed.) Logic at Work: Essays Dedicated to the Memory of Helena Rasiowa, pp. 307–328. Springer (1999)
Ohlbach, H.J.: SCAN–elimination of predicate quantifiers. In: McRobbie, M.A., Slaney, J.K. (eds.) CADE 1996. LNCS, vol. 1104, pp. 161–165. Springer, Heidelberg (1996)
Schild, K.: A correspondence theory for terminological logics: preliminary report. In: Proceedings of IJCAI 1991, pp. 466–471. Morgan Kaufmann (1991)
Schmidt, R.A.: The Ackermann approach for modal logic, correspondence theory and second-order reduction. Journal of Applied Logic 10(1), 52–74 (2012)
Szałas, A.: On the correspondence between modal and classical logic: An automated approach. Journal of Logic and Computation 3, 605–620 (1993)
Szałas, A.: Second-order reasoning in description logics. Journal of Applied Non-Classical Logics 16(3–4), 517–530 (2006)
Wang, K., Wang, Z., Topor, R., Pan, J.Z., Antoniou, G.: Concept and role forgetting in \(\cal ALC\) ontologies. In: Bernstein, A., Karger, D.R., Heath, T., Feigenbaum, L., Maynard, D., Motta, E., Thirunarayan, K. (eds.) ISWC 2009. LNCS, vol. 5823, pp. 666–681. Springer, Heidelberg (2009)
Wang, K., Wang, Z., Topor, R., Pan, J.Z., Antoniou, G.: Eliminating concepts and roles from ontologies in expressive description logics. Computational Intelligence 30(2), 205–232 (2014)
Wang, Z., Wang, K., Topor, R., Pan, J.Z.: Forgetting concepts in DL-Lite. In: Bechhofer, S., Hauswirth, M., Hoffmann, J., Koubarakis, M. (eds.) ESWC 2008. LNCS, vol. 5021, pp. 245–257. Springer, Heidelberg (2008)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Zhao, Y., Schmidt, R.A. (2015). Concept Forgetting in \(\mathcal {ALCOI}\)-Ontologies Using an Ackermann Approach. In: Arenas, M., et al. The Semantic Web - ISWC 2015. ISWC 2015. Lecture Notes in Computer Science(), vol 9366. Springer, Cham. https://doi.org/10.1007/978-3-319-25007-6_34
Download citation
DOI: https://doi.org/10.1007/978-3-319-25007-6_34
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-25006-9
Online ISBN: 978-3-319-25007-6
eBook Packages: Computer ScienceComputer Science (R0)