Please use this identifier to cite or link to this item: https://elib.utmn.ru/jspui/handle/ru-tsu/14515
Title: Сокращение пространства поиска интерпретаций за счет обнаружения изоморфных концептов
Other Titles: Reducing of interpretation search space through isomorphic concepts discovering
Authors: Alexander, G. Ivashko
Andrey, V. Grigoryev
Григорьев, Андрей Викторович
Ивашко, Александр Григорьевич
Keywords: description logic;Isomorphism;tableau algorithm;concept;Изоморфизм;дескрипционная логика;концепт;табличный алгоритм
Issue Date: 2013
Citation: Ивашко, А. Г. Сокращение пространства поиска интерпретаций за счет обнаружения изоморфных концептов / А. Г. Ивашко, А. В. Григорьев // Вестник Тюменского государственного университета. - 2013. - № 7. - С. 187-193.
metadata.dc.relation.ispartof: Вестник ТюмГУ: Физико-математическое моделирование. Нефть, газ, энергетика. Физико-математические науки. Информатика (№7, 2013)
Abstract: В статье рассматривается алгоритм осуществления логического вывода в базах знаний, описанных на языке OWL, который основан на формализме дескрипционных логик. Рассматриваемый алгоритм имеет экспоненциальную вычислительную сложность, что делает его не применимым на практике. К настоящему моменту были разработаны оптимизации, существенно сокращающие время работы алгоритма, но некоторые реальные базы знаний не могут быть классифицированы за приемлемое время. Основная часть статьи посвящена разработке метода сокращения количества рассматриваемых интерпретаций табличным алгоритмом за счет исключения из поиска изоморфных интерпретаций. Для данного метода представлено доказательство корректности работы и дана оценка количеству не рассматриваемых интерпретаций.В статье приводится краткое описание структур, используемых для представления концептов, и приведена модификация метода Эдмондсона для поиска идентичных подструктур в описании концептов. Разработанный метод был реализован в системе TReasoner. В заключение представлены результаты тестирования на данных международного симпозиума по дескрипционным логикам DL'98 в сравнении с наиболее популярными системами логического анализа онтологий JFact и . 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.
URI: https://elib.utmn.ru/jspui/handle/ru-tsu/14515
Appears in Collections:Вестник ТюмГУ: Физико-математическое моделирование. Нефть, газ, энергетика

Files in This Item:
File SizeFormat 
3_А.Г. Ивашко, А.В. Григорьев.pdf432,51 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.