Optimized absorption method to reduce the time of tableaux algorithm

Journal «Language & Science» UTMN.



Optimized absorption method to reduce the time of tableaux algorithm

About the authors:

Grigoriev A V. ,
Tyumen State University, Information system department, assistant

Ovsyannikova, E O. , Tyumen State University, Information system department, System administrator


Nowadays OWL language and description logic as a consequence of its logical basis are the most widely used tools for knowledge representation. Reasoning is performed by the tableaux method which has exponential computational complexity. This article provides an improvement in the absorption method, which won’t allow the reduction of the computational complexity of the algorithm, but it will reduce the operating time of the tableaux algorithm.


1. Ivashko A., Ivanova E., Ovsyannikova E., Kolomiets S.. The
description logic application to describing the information system architecture. //
Bulletin of the Tyumen State University. 2012. vol. 4. - pp.137-142.
2. Baader F., Calvanese D., McGuinness D., Nardi D., Patel-Schneider
P. F. The Description Logic Handbook: Theory, Implementation and Applications.
– CUP, 2003.
3. Horrocks I. Optimizing tableaux decision procedures for description
logics. PhD thesis, University of Manchester, 1999.
4. Rudolph S., Polleres A., d'Amato C., Patel-Schneider P. F.
Foundations of Description Logics // Reasoning Web. Semantic Technologies for
the Web of Data. 2011. pp. 76-136. Springer, 2011.
5. Schmidt-Schauss M., Smolka G.. Attributive concept descriptions
with complements. // Artificial Intelligence, № 48, pp. 1-26. Springer, 1991.
6. W3C OWL Working Group. Standard at OWL 2. // [Electronic
resource]. URL: http://www.w3.org/TR/owl2-overview/ (date accessed
7. Wagih H. M., El Zanfaly D. S., Kouta M. M. Mapping Object Role
Modeling 2 Schemes into SROIQ (D) Description Logic. // International Journal of
Computer Theory and Engineering vol. 5, no. 2, pp. 232-237, Springer, 2013.
8. Horrocks I., Kutz O., Sattler U. The Even More Irresistible SROIQ //
Proceedings of the 10th International Conference on Principles of Knowledge
Representation and Reasoning (KR 2006), pp. 57-67. AAAI Press, 2006.
9. Motik B., Horrocks I. // Proceedings of the 7th International Semantic
Web Conference ISWC 2008, vol. 5318 of LNCS, pp. 307-322. Springer, 2008.
10. Lange K., Rossmanith P. The Emptiness Problem for Intersections of
Regular Languages // 17th Conference on Mathematical Foundations of Computer
Science. - 1992.