Сокращение пространства поиска интерпретаций за счет обнаружения изоморфных концептов

Об авторах:

Ивашко Александр Григорьевич, доктор технических наук, профессор кафедры программной и системной инженерии, Тюменский государственный университет; a.g.ivashko@utmn.ru

Григорьев Андрей Викторович, аспирант кафедры информационных систем Института математики, естественных наук и информационных технологий Тюменского государственного университета

Аннотация:

В статье рассматривается алгоритм осуществления логического вывода в базах знаний, описанных на языке OWL, который основан на формализме дескрипционных логик. Рассматриваемый алгоритм имеет экспоненциальную вычислительную сложность, что делает его не применимым на практике. К настоящему моменту были разработаны оптимизации, существенно сокращающие время работы алгоритма, но некоторые реальные базы знаний не могут быть классифицированы за приемлемое время. Основная часть статьи посвящена разработке метода сокращения количества рассматриваемых интерпретаций табличным алгоритмом за счет исключения из поиска изоморфных интерпретаций. Для данного метода представлено доказательство корректности работы и дана оценка количеству не рассматриваемых интерпретаций.В статье приводится краткое описание структур, используемых для представления концептов, и приведена модификация метода Эдмондсона для поиска идентичных подструктур в описании концептов. Разработанный метод был реализован в системе TReasoner. В заключение представлены результаты тестирования на данных международного симпозиума по дескрипционным логикам DL'98 в сравнении с наиболее популярными системами логического анализа онтологий JFact и HermiT.

Список литературы:

1. Ивашко А.Г., Иванова Е.И., Овсянникова Е.О., Коломиец С.И. Применение дескрипционной логики для описания архитектуры информационной системы // Вестник Тюменского государственного университета. 2012. №4. Серия «Физико-математические науки. Информатика». С. 137-142.

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

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

4. Schmidt-Schaus, M. and Smolka, 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 Intelligence. 93(1):273-288. 2009.

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

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

11. Григорьев А.В. Алгоритм упрощения концептов ALC //Современные проблемы математического и информационного моделирования. Перспективы разработки и внедрения инновационных IT-решений. 2012.

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.