Abstract
Unification in description logics (DLs) has been introduced as a novel inference service that can be used to detect redundancies in ontologies, by finding different concepts that may potentially stand for the same intuitive notion. It was first investigated in detail for the DL \(\mathcal {FL}_0\), where unification can be reduced to solving certain language equations. In order to increase the recall of this method for finding redundancies, we introduce and investigate the notion of approximate unification, which basically finds pairs of concepts that “almost” unify. The meaning of “almost” is formalized using distance measures between concepts. We show that approximate unification in \(\mathcal {FL}_0\) can be reduced to approximately solving language equations, and devise algorithms for solving the latter problem for two particular distance measures.
F. Baader—Supported by the Cluster of Excellence ‘Center for Advancing Electronics Dresden’.
P. Marantidis—Supported by DFG Graduiertenkolleg 1763 (QuantLA).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
In the first line below we assume, as usual, that \(\min \emptyset = \infty \) and \(2^{-\infty } = 0\).
- 2.
An ILTA \((\varSigma , Q, Q_0, \delta )\) is trim if every state is reachable from an initial state and \(\delta (q,a) \ne \emptyset \) for all \(q\in Q, a\in \varSigma \).
References
Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P.F. (eds.): The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press (2003)
Baader, F., Marantidis, P., Okhotin, A.: Approximate unification in the description logic \(\cal{FL}_{0}\). LTCS-Report 16–04, Chair for Automata Theory, Institute for Theoretical Computer Science, Technische Universität Dresden, Dresden (2016). http://lat.inf.tu-dresden.de/research/reports.html
Baader, F., Marantidis, P., Okhotin, A.: Approximately solving set equations. In: Ghilardi, S., Schmidt-Schauß, M. (eds.) Proceedings of the 30th International Workshop on Unification (UNIF 2016), Porto (2016)
Baader, F., Morawska, B.: Unification in the description logic \(\cal{EL}\). Log. Methods Comput. Sci. 6(3), 350–364 (2010)
Baader, F., Narendran, P.: Unification of concept terms in description logics. J. Symb. Comput. 31(3), 277–305 (2001)
Baader, F., Okhotin, A.: On language equations with one-sided concatenation. Fundamenta Informaticae 126(1), 1–35 (2013)
Baader, F., Tobies, S.: The inverse method implements the automata approach for modal satisfiability. In: Goré, R., Leitsch, A., Nipkow, T. (eds.) IJCAR 2001. LNCS, vol. 2083, pp. 92–106. Springer, Heidelberg (2001). doi:10.1007/3-540-45744-5_8
Banach, S.: Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales. Fundamenta Mathematicae 3(1), 133–181 (1922)
Ecke, A., Peñaloza, R., Turhan, A.-Y.: Computing role-depth bounded generalizations in the description logic \(\cal {ELOR}\). In: Timm, I.J., Thimm, M. (eds.) KI 2013. LNCS (LNAI), vol. 8077, pp. 49–60. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40942-4_5
Iranzo, P.J., Rubio-Manzano, C.: Proximity-based unification theory. Fuzzy Sets Syst. 262, 21–43 (2015)
Kapur, D., Narendran, P.: Complexity of unification problems with associative-commutative operators. J. Autom. Reason. 9, 261–288 (1992)
Kreyszig, E.: Introductory Functional Analysis With Applications. Wiley, New York (1978). Wiley Classics Library
Kunc, M.: What do we know about language equations? In: Harju, T., Karhumäki, J., Lepistö, A. (eds.) DLT 2007. LNCS, vol. 4588, pp. 23–27. Springer, Heidelberg (2007). doi:10.1007/978-3-540-73208-2_3
Lehmann, K., Turhan, A.-Y.: A framework for semantic-based similarity measures for \(\cal {ELH}\)-concepts. In: Cerro, L.F., Herzig, A., Mengin, J. (eds.) JELIA 2012. LNCS (LNAI), vol. 7519, pp. 307–319. Springer, Heidelberg (2012). doi:10.1007/978-3-642-33353-8_24
Munkres, J.: Topology. Featured Titles for Topology Series. Prentice Hall, Upper Saddle River (2000)
Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1999)
Tongphu, S., Suntisrivaraporn, B.: On desirable properties of the structural subsumption-based similarity measure. In: Supnithi, T., Yamaguchi, T., Pan, J.Z., Wuwongse, V., Buranarach, M. (eds.) JIST 2014. LNCS, vol. 8943, pp. 19–32. Springer, Heidelberg (2015). doi:10.1007/978-3-319-15615-6_2
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Baader, F., Marantidis, P., Okhotin, A. (2016). Approximate Unification in the Description Logic \(\mathcal {FL}_0\) . In: Michael, L., Kakas, A. (eds) Logics in Artificial Intelligence. JELIA 2016. Lecture Notes in Computer Science(), vol 10021. Springer, Cham. https://doi.org/10.1007/978-3-319-48758-8_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-48758-8_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-48757-1
Online ISBN: 978-3-319-48758-8
eBook Packages: Computer ScienceComputer Science (R0)