Abstract
The Semantic Web makes an extensive use of the OWL DL ontology language, underlied by the \(\mathcal{SHOIQ}\) description logic, to formalize its resources. In this paper, we propose a decision procedure for this logic extended with the transitive closure of roles in concept axioms, a feature needed in several application domains. The most challenging issue we have to deal with when designing such a decision procedure is to represent infinitely non-tree-shaped models, which are different from those of \(\mathcal{SHOIQ}\) ontologies. To address this issue, we introduce a new blocking condition for characterizing models which may have an infinite non-tree-shaped part.
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
Patel-Schneider, P., Hayes, P., Horrocks, I.: Owl web ontology language semantics and abstract syntax. In: W3C Recommendation (2004)
Tobies, S.: The complexity of reasoning with cardinality restrictions and nominals in expressive description logics. Journal of Artificial Intelligence Research 12, 199–217 (2000)
Aho, A.V., Ullman, J.D.: Universality of data retrieval languages. In: Proceedings of the 6th of ACM Symposium on Principles of Programming Language (1979)
Baader, F.: Augmenting concept languages by transitive closure of roles: An alternative to terminological cycles. In: Proceedings of the Twelfth International Joint Conference on Artificial Intelligence (1991)
Ortiz, M.: An automata-based algorithm for description logics around \(\mathcal{SRIQ}\). In: Proceedings of the fourth Latin American Workshop on Non-Monotonic Reasoning 2008, CEUR-WS.org (2008)
Calvanese, D., Eiter, T., Ortiz, M.: Regular path queries in expressive description logics with nominals. In: IJCAI, pp. 714–720 (2009)
Horrocks, I., Sattler, U.: A tableau decision procedure for \(\mathcal{SHOIQ}\). Journal of Automated Reasoning 39(3), 249–276 (2007)
Motik, B., Shearer, R., Horrocks, I.: Hypertableau reasoning for description logics. J. of Artificial Intelligence Research 36, 165–228 (2009)
Pratt-Hartmann, I.: Complexity of the two-variable fragment with counting quantifiers. Journal of Logic, Language and Information 14(3), 369–395 (2005)
Le Duc, C., Lamolle, M.: Decidability of description logics with transitive closure of roles. In: Proceedings of the 23rd International Workshop on Description Logics (DL 2010). CEUR-WS.org (2010)
Horrocks, I., Sattler, U., Tobies, S.: Practical reasoning for expressive description logics. In: Ganzinger, H., McAllester, D., Voronkov, A. (eds.) LPAR 1999. LNCS, vol. 1705, pp. 161–180. Springer, Heidelberg (1999)
Baader, F., Nutt, W.: Basic description logics. In: The Description Logic Handbook: Theory, Implementation and Applications, 2nd edn., pp. 47–104. Cambridge University Press (2007)
Fischer, M.J., Ladner, R.I.: Propositional dynamic logic of regular programs. Journal of Computer and System Sciences 18(18), 174–211 (1979)
Le Duc, C., Lamolle, M., Curé, O.: A decision procedure for \(\mathcal{SHOIQ}\) with transitive closure of roles in concept axioms. In: Technical Report (2013), http://www.iut.univ-paris8.fr/~leduc/papers/TR-SHOIQTr.pdf
Le Duc, C., Lamolle, M., Curé, O.: An expspace tableau-based algorithm for \(\mathcal{SHOIQ}\). In: Description Logics (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Le Duc, C., Lamolle, M., Curé, O. (2013). A Decision Procedure for \(\mathcal{SHOIQ}\) with Transitive Closure of Roles. In: Alani, H., et al. The Semantic Web – ISWC 2013. ISWC 2013. Lecture Notes in Computer Science, vol 8218. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41335-3_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-41335-3_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-41334-6
Online ISBN: 978-3-642-41335-3
eBook Packages: Computer ScienceComputer Science (R0)