Abstract
Practical scalability of Description Logic (DL) reasoning is an important premise for the adoption of OWL in a real-world setting. Many highly efficient optimizations for the DL tableau calculus have been invented over the last decades. None of them aimed at parallelizing the tableau algorithm itself. This paper describes our approach for concurrent computation of the nondeterministic choices inherent to the standard tableau procedure. We discuss how this interrelates with the well-known optimization techniques and present first promising performance results when benchmarking our prototypical reasoner UUPR (Ulm University Parallel Reasoner) with a selection of established DL systems.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F.: The description logic handbook: theory, implementation, and applications. Cambridge University Press, New York (2003)
Berger, E.D., McKinley, K.S., Blumofe, R.D., Wilson, P.R.: Hoard: A scalable memory allocator for multithreaded applications. In: International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-IX), Cambridge, MA, pp. 117–128 (November 2000)
Bergmann, F.W., Quantz, J.J.: Parallelizing Description Logics. In: Wachsmuth, I., Brauer, W., Rollinger, C.-R. (eds.) KI-95: Advances in Artificial Intelligence. LNCS, vol. 981, pp. 137–148. Springer, Heidelberg (1995)
Haarslev, V., Möller, R.: Expressive ABox Reasoning with Number Restrictions, Role Hierarchies, and Transitively Closed Roles. In: Int. Conf. on Principles of Knowledge Representation and Reasoning (KR2000), pp. 273–284 (2000)
Haarslev, V., Möller, R., Turhan, A.Y.: Exploiting Pseudo Models for TBox and ABox Reasoning in Expressive Description Logics. In: Goré, R.P., Leitsch, A., Nipkow, T. (eds.) IJCAR 2001. LNCS (LNAI), vol. 2083, pp. 29–44. Springer, Heidelberg (2001)
Horrocks, I.: Applications of description logics: State of the art and research challenges. In: Dau, F., Mugnier, M.-L., Stumme, G. (eds.) ICCS 2005. LNCS (LNAI), vol. 3596, pp. 78–90. Springer, Heidelberg (2005)
Liebig, T.: Reasoning with OWL – system support and insights –. Technical Report TR-2006-04, Ulm University, Ulm, Germany (September 2006)
Schumann, J.: Tableau-Based Theorem Provers: Systems and Implementations. Journal of Automated Reasoning 13, 409–421 (1994)
Tsarkov, D., Horrocks, I., Patel-Schneider, P.F.: Optimising Terminological Reasoning for Expressive Description Logics. Journal of Automated Reasoning 39(3), 277–316 (2007)
Voronkov, A.: Automated Reasoning: Past Story and New Trends. In: Proc. of the Int. Joint Conf. on AI (IJCAI-2003, pp. 1607–1612 (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Liebig, T., Müller, F. (2007). Parallelizing Tableaux-Based Description Logic Reasoning. In: Meersman, R., Tari, Z., Herrero, P. (eds) On the Move to Meaningful Internet Systems 2007: OTM 2007 Workshops. OTM 2007. Lecture Notes in Computer Science, vol 4806. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-76890-6_41
Download citation
DOI: https://doi.org/10.1007/978-3-540-76890-6_41
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-76889-0
Online ISBN: 978-3-540-76890-6
eBook Packages: Computer ScienceComputer Science (R0)