Reducing of interpretation search space through isomorphic concepts discovering

About the authors:

Alexander G. Ivashko, Dr. Sci. (Tech.), Professor, Department of Program and System Engineering, University of Tyumen; a.g.ivashko@utmn.ru

Andrey V. Grigoryev, postgraduate student, Institute of Mathematics, Humanities and Information Technologies, Tyumen State University

Abstract:

The article considers an algorithm for logic inference on knowledge bases described in OWL language which is based on description logic formalism. The considered algorithm has an NEXPTIME complexity which makes it inapplicable in practice. By now certain optimizations, reducing worktime of the algorithm, have been developed, but nevertheless some real knowledge bases can’t be classified in satisfactory time. The main part of the article is devoted to developing of a new method on reducing the number of interpretations under consideration by tableau algorithm. The article demonstrates the proof of correctness for the given method and offers estimation of the number of nonconsidered interpretations. The authors briefly describe the structures, used for concepts representation, and determine the modification of Edmonds’ method for the search of identical substructures in concept descriptions. The developed method is implemented in TReasoner system. At the end of the article testing results are presented. Testing was performed with the help of data of the Description Logic International Workshop DL’98 in comparison with such popular systems as JFact and HermiT.

References:

1. Ivashko, A.G., Ivanova, E.I., Ovsjannikova, E.O., Kolomiec, S.I. Application of Description Logic for the Description of Information System Architecture. Vestnik Tjumenskogo gosudarstvennogo universiteta — Tyumen State University Herald. №4. 2012. Pp. 137-142. (in Russian).

2. Jie Bao, Elisa F. Kendall, Deborah L. McGuinness, Peter F. Patel-Schneider. OWL 2 Web Ontology Language Quick Reference Guide (Second Edition) // http://www.w3.org/TR/2012/REC-owl2-quick-reference-20121211/

3. F. Baader, D. Calvanese, D. McGuinness, D. Nardi, and P. F. Patel-Schneider, editors. The Description Logic Handbook: Theory, Implementation and Applications. CUP, 2003, p. 601.

4. Schmidt-Schaus, M. andSmolka, G. Attributive concept descriptions with complements. Artificial Intelligence. 48(1):1-26, 1991.

5. Motik, B., Shearer, R., Horrocks, I. Hypertableau Reasoning for Description Logics. Journal of Artificial Intelligence Research 36(1):165-228, 2009.

6. Donini, F.M., Massacci, F. EXPTIME tableaux for ALC. Artificial Intelligence.124(1): 87-138, 2000.

7. Ding, Y. and Haarslev, V. Tableau caching for description logics with inverse and transitive roles. In Proc. DL-2006: International Workshop on Description Logics. 2006. Pp. 143-149.

8. Linh Anh Nguyen. An Efficient Tableau Prover using Global Caching for the Description Logic ALC. Artificial Intelligenc. 93(1):273-288, 2009.

9. Prosser, P. Hybrid Algorithms for the Constraint Satisfaction Problem. Computational Intelligence. 9(3). 1993. Pp. 268-299.

10. Horrocks, I., Boris Motik, and Zhe Wang. The HermiT OWL Reasoner // OWL Reasoner Evaluation Workshop. 2012.

11. Grigor'ev, A.V. Algorithm of ALC concepts simplification. Sovremennye problem matematicheskogo i informacionnogo modelirovanija. Perspektivy razrabotki i vnedrenija innovacionnyh IT-reshenij — Topical Problems of Mathematics of Information Modeling. Prospects of Innovative IT-Methods Development and Implementation. 2012. (in Russian).

12. Busacker, G., Saaty, T.L. Finite Graphs and Networks. McGraw Hill, 1965.

13. Franconi, E. DL'98 Systems Comparison: official test data. //http://dl.kr.org/dl98/comparison/data.html

14. Tsarkov, D. and Horrocks, I. FaCT++ Description Logic Reasoner: System Description. In Proc. IJCAR 2006. Pp. 292-297.