Математические методы и алгоритмы определения согласованности баз знаний тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Григорьев, Андрей Викторович

• Григорьев, Андрей Викторович
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Григорьев, Андрей Викторович

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

ГЛАВА 1 МЕТОДЫ ОПРЕДЕЛЕНИЯ СОГЛАСОВАННОСТИ БАЗ ЗНАНИЙ

1.1 Математические инструменты представления знаний

1.1.1 Подходы основанные на теории графов

1.1.2 Подходы основанные на формальной логике

1.2 Алгоритмы анализа баз знаний

1.2.1 Методы основанные на автоматах

1.2.2 Методы основанные на правилах вывода

1.2.3 Метод резолюций

1.2.4 Табличные методы

1.3 Выводы

ГЛАВА 2 МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ

2.1 Сетевая модель классов предметной области

2.2 Разработка метода решения задачи о максимальном потоке минимальной стоимости для разработанной сетевой модели

2.3 Использование изоморфизма концептов для проверки согласованности баз знаний

2.4 Выводы

ГЛАВА 3 ПРОГРАММНЫЙ КОМПЛЕКС ПОДДЕРЖКИ ДЕЯТЕЛЬНОСТИ ИНЖЕНЕРА ПО ЗНАНИЯМ

3.1 Описание архитектуры программного комплекса

3.2 Описание уровня приложений программного комплекса

3.3 Описание уровня представлений

3.4 Выводы

ГЛАВА 4 ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ

4.1 Вычислительный эксперимент для базы знаний GALEN

4.2Вычислительный эксперимент на данных DL 98

4.3Вычислительный эксперимент на данных ORE 2013

4.4 Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕА

Введение диссертации (часть автореферата) на тему «Математические методы и алгоритмы определения согласованности баз знаний»

Введение

Актуальность темы исследования. Исследования в области разработки методов определения согласованности баз знаний обусловлены необходимостью решения таких практически значимых задач как семантический поиск, классификация понятий предметной области или поддержка принятия решений в экспертных системах. Для решения задач такого рода успешно применяются методы, основанные на автоматах (D. Calvanese, KRDB Research Center в Университете г. Бозен-Больцано; T. Either, Институт информационных систем университета г. Вена), методы, основанные на правилах вывода (Е. Kazakov, Вычислительная лаборатория Оксфордского университета), метод резолюций (В. Motik, университет г. Манчестер) и табличные методы (I. Horrocks, университет г. Манчестер). Основная проблема таких методов заключается в том, что все они имеют экспоненциальную вычислительную сложность, поэтому их применение в задачах реального времени весьма затруднительно для больших баз знаний (более 5000 аксиом).

Для того, чтобы снизить время работы представленных методов на практике, учеными предпринимается огромное количество попыток разработки новых алгоритмов. Такие разработки ежегодно представляются на международных конференциях по применению логических формализмов в искусственном интеллекте «Description Logic Workshop» и «International Joint Conférence On Automated Reasoning». Наиболее значимыми разработками, представленными на данных форумах, являются: алгоритм кэширования (Y. Ding, V. Haarslev), backJumpïng-алгоритм (I. Horrocks), алгоритм глобального кэширования (L. A. Nguyen), которые, зачастую, основываются на методах теории множеств и методах логики первого порядка, кроме того ни одна из этих разработок не направлена на снижение теоретической оценки вычислительной сложности.

Целью исследования является разработка алгоритмов проверки

согласованности баз знаний, сокращающих вычислительную сложность

табличных методов на определенных классах баз знаний.

Для достижения поставленной цели необходимо решить задачи:

1. Построение сетевой модели базы знаний, описанной выражениями дескрипционной логики.

2. Разработка метода нахождения максимального потока минимальной стоимости в разработанной сетевой модели базы знаний.

3. Реализация программного комплекса для поддержки деятельности инженера по знаниям, реализующего разработанные методы и алгоритмы.

4. Проведение вычислительного эксперимента для проверки адекватности разработанных моделей и методов.

Научная новизна исследования. Научная новизна исследования

заключается в следующем:

1. Разработана и обоснована сетевая модель базы знаний, представленной аксиомами предметной области, что дает возможность использовать математические методы и алгоритмы, применяемые в теории графов;

2. Для сетевой модели базы знаний разработан новый численный метод нахождения максимального потока минимальной стоимости с вычислительной сложностью О (К2). Доказано, что если максимальный поток минимальной стоимости графа, ассоциированного с конъюнкцией двух концептов, имеет положительный вес, то эта конъюнкция не согласована.

3. Модифицирован табличный метод проверки согласованности базы знаний, в котором обосновано, что для изоморфных концептов допускается не проводить повторную проверку;

4. Модифицирован алгоритм нахождения автоморфизмов в деревьях (J. Edmonds) для поиска изоморфных концептов базы знаний.

Практическая значимость работы. Для применения разработанных методов и алгоритмов был реализован кроссплатформенный программный комплекс поддержки деятельности инженера по знаниям. Программный комплекс позволяет создавать, импортировать и интегрировать базы знаний на языке OWL 2, выполнять проверку согласованности базы знаний, классификацию понятий и проверку их выполнимости.

Методология и методы исследования. При исследовании применялись методы теории множеств, теории графов, теории методов оптимизации.

На защиту выносятся следующие результаты соответствующие трем пунктам паспорта специальности 05.13.18 - Математическое моделирование, численные методы и комплексы программ по физико-математическим наукам:

Пункт 1. Разработка новых математических методов моделирования объектов и явлений.

1. Разработана новая математическая модель баз знаний, в которой для моделирования понятий баз знаний впервые были использованы сетевые модели, что позволяет применять алгоритмы поиска максимального потока минимальной стоимости для задач проверки согласованности баз знаний.

2. Разработан новый метод проверки согласованности базы знаний для классов изоморфных концептов, позволяющий сократить количество переборов в табличном методе.

Пункт 3. Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий.

3. Предложен новый численный метод нахождения максимального потока минимальной стоимости в разработанных сетевых моделях баз знаний. Вычислительная сложность разработанного алгоритма составила 0(V2).

Пункт 4. Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента.

4. Разработан программный комплекс для поддержки деятельности инженера по знаниям, позволяющий проводить классификацию, проверку согласованности и выполнимости концептов. Описание базы знаний реализовано с помощью языка OWL2.

5. Проведен вычислительный эксперимент. Для этого использовались 200 опубликованных базах знаний, для которых выполнялись задачи классификации и проверки согласованности. Результаты компьютерных экспериментов показали адекватность разработанных в диссертации математических моделей и методов.

Таким образом, в соответствии с формулой специальности 05.13.18 в диссертации представлены оригинальные результаты одновременно из трех областей: математического моделирования, численных методов и комплексов программ.

Достоверность изложенных в работе результатов подтверждается корректным использованием математического аппарата дескрипционной логики, теории графов, языка OWL 2 и сравнением полученных результатов с результатами авторов исследований в этой области.

Апробация результатов. Основные результаты исследования докладывались на:

• II международной конференции «OWL Reasoner Evaluation Workshop (ORE 2013)» (Германия, Ульм, 22 июля 2013);

• Международной научно-практической конференции «Современные проблемы и пути их решения в науке, транспорте, производстве и образовании'2012» (Украина, Одесса, 18-27 декабря 2012);

• XIV международной научно-практической конференции «Современные проблемы гуманитарных и естественных наук» (Москва, 26-27 марта 2013

г.);

• Научно-технической конференции «Современные проблемы математического и информационного моделирования. Перспективы разработки и внедрения инновационных 1Т-решений» (Тюмень, 13-15 апреля 2012 г.)

Глава 1 Методы определения согласованности баз знаний

1.1 Математические инструменты представления знаний

Для представления знаний в интеллектуальных информационных системах используется большое количество формализмов, некоторые из которых были разработаны специально для этой цели, другие же были заимствованы из других областей науки. Все многообразие моделей представления знаний можно условно поделить на 2 больших группы. Это математические модели представления знаний, основанные на различных логических формализмах и математические модели представления знаний, основанные на теории графов.

1.1.1 Подходы, основанные на теории графов

В группе формализмов, не основанных на логике, существуют два наиболее широко применяемых на сегодняшний момент метода: семантические сети и фреймы.

Семантические сети являются наиболее популярным формализмом представления знаний, в связи с тем, что они хорошо понимаются и просты в применении. Семантические сети получили широкое распространение в проблемах представления и обработки текстов на естественных языках [1]. Кроме того, семантические сети являются математической основой языка RDF [2], разработанного консорциумом W3C, специально для решения задач семантической паутины. Однако, данный подход обладает рядом недостатков, среди которых стоит выделить тот, что в семантических сетях не существует различий между классами и конкретными объектами классов, это влечет за собой возникновение неоднозначности при описании знаний, например, отношение "является" может означать как принадлежность конкретного индивида некоторому классу, так и то, что некоторый класс является подмножеством другого класса.

Среди алгоритмов вывода знаний в семантических сетях наиболее популярными являются два подхода: структурные методы [3] (методы

определения сходства подграфов), и методы вероятностно-алгебраического моделирования [4].

Наиболее известным примером использования семантических сетей является база знаний А^огс^е! [5], которая была разработана в лаборатории когнитивной науки университета города Принстон. '^гсШе! содержит существительные, прилагательные и глаголы, объединенные в классы синонимии и связанные отношениями между собой. Д\^огс1Ме1 не предоставляет каких-либо инструментов логического вывода или логического анализа и используется лишь как тезаурус, однако, успешно применяется в обработке естественного языка [6].

Ещё одной современной и успешной разработкой основанной на семантических сетях является система МиШ№1;, предоставляющая инструменты, включающие:

• семантический интерпретатор, который автоматически переводит тексты на

естественном немецком языке в сети МиШ№1:;

• браузер;

• синтаксический анализатор для управления структурами [5].

Недостатками подхода семантических сетей является то, что они не всегда способны определить неявно заданные знания из-за применения вероятностного подхода, кроме того, алгоритмы, реализующие структурные методы, являются КЕХРТ1МЕ (то есть имеют экспоненциальную вычислительную сложность), что не позволяет применять их для исследования моделей больших размеров.

Идея формализма фреймов заключается в использовании некоторого алгоритма (фреймворка), называемого фреймом [7], при появлении стереотипных ситуаций, при этом некоторые атрибуты фрейма меняются исходя из поставленной проблемы. Во фреймовой структуре, так же как и в семантической сети, используются понятия-вершины и отношения-ребра; отличие заключаются в том, что вместо вершин, понятия представляются особыми структурами -

фреймами, для которых в свою очередь введена система наследования, то есть один фрейм может наследовать атрибуты другого фрейма.

Практическое применение язык фреймов получил в системе KL-ONE [7], которая является системой представления знаний в искусственном интеллекте и успешно применялась в двух направлениях: как система для интеллектуального представления информации и в качестве модуля понимания естественных языков.

Ещё одной системой, основанной на языке фреймов, является Knowledge Machine [8]. Рассматриваемая система, наряду с системой KL-ONE, является реализацией собственного языка описания знаний, являющегося одним из потомков языка фреймов, при этом Knowledge Machine не привязана к какой-либо конкретной прикладной задаче, но способна осуществлять выполнение задач классификации и вывода новых знаний, на основе алгоритма проверки выполнимости концептов.

Хотя фреймовая система и представлена как независимый формализм описания знаний, при детальном изучении было установлено, что она является всего лишь вариантом синтаксиса фрагмента логики первого порядка, который представлен лишь операциями конъюнкции и квантором существования без предоставления таких операций как дизъюнкция и квантор всеобщности [5]. Тот факт, что системы, основанные на фреймах, не разрабатываются с начала 2000х годов, говорит о том, что рассматриваемый формализм представления знаний не имеет перспектив для продолжения исследований.

1.1.2 Подходы, основанные на формальной логике

Среди формализмов, основанных на логике, прежде всего, стоит отметить такие методы как логика первого порядка, модальная логика, темпоральная логика, логические программы, хорновские логики (язык пролог) и дескрипционная логика, которая является математической основой языка OWL [911], являющегося стандартом для описания онтологий семантической паутины.

Описание баз знаний любыми логическими формализмами включает в себя задание аксиом и фактов о предметной области. При этом аксиомы определяют соотношения классов объектов, а факты задают утверждения о конкретных объектах предметной области. Алгоритмы вывода знаний, в формальных системах заключаются в проверке выполнимости совокупности множества аксиом и множества фактов. Новые знания определяются в виде аксиом, зачастую они выводятся в виде аксиом включения понятий определенных в предметной области. Для определения отношения включаемости, в базу знаний добавляется аксиома включения, и если новая база знаний является выполнимой, то вся совокупность фактов влечет эту аксиому.

Рассматриваемые в этом параграфе формализмы представления знаний отличаются между собой выразительностью, то есть возможностями детального описания предметных областей, и алгоритмами осуществляющими логический анализ баз знаний, из чего прослеживается обратная зависимость выразительности логики языка и эффективности (с точки зрения времени выполнения) разрешающего алгоритма для неё.

1.1.2.1 Логика первого порядка

Логика первого порядка (или логика предикатов) позволяет описывать любые знания с помощью переменных, предикатов, функций и констант, позволяя задавать взаимосвязи между любым количеством объектов или классов [12-15]. Данная формальная система является мощнейшим инструментом определения любых логических выражений, все остальные, рассматриваемые в данном параграфе формализмы, являются фрагментами логики первого порядка (за исключением модальной и темпоральной логики). Однако максимальные выразительные возможности логики предикатов редко используются на практике [16]. Прежде всего, это связано с тем, что не существует алгоритма, который способен проверить выполнимость произвольной формулы, описанной в данной формальной системе, соответственно такой алгоритм отсутствует и для проверки базы знаний. Не смотря на это, для некоторого подмножества формул логики

первого порядка существует эффективный алгоритм логического анализа, называемый методом резолюций [12-16]. Кроме того, мощность выразительных возможностей языка не всегда является положительным аспектом используемого формализма. Выразительность логики первого порядка зачастую оказывается избыточной для задач, решаемых в рамках поставленной цели.

Однако, не смотря на все указанные проблемы при использовании, все же существуют варианты практического применения данного подхода. Knowledge interchange format - формат обмена знаниями [5], язык обмена знаниями между не интегрируемыми системами впервые был представлен в 1992 году. На сегодняшний момент KIF является основой фреймворка для так называемых языков общей логики, которые являются ISO стандартом обмена знаниями.

1.1.2.2 Модальная логика

Модальные логики были разработаны для того, чтобы оперировать различными формами истины. Например, можно специфицировать то, что обязательно является истиной, то, что известно как истина, и то, что принято на веру как истина. Такие формы принято называть модальностями [5], среди которых особо стоит выделить "должно быть" (необходимость) и "может быть" (возможность).

На сегодняшний момент модальные логики имеют применение в таких разработках как распределенные вычисления [17], логический вывод о программах [18], спецификация и верификация мультиагентных систем [19] верификация темпоральных свойств систем и логический вывод в теории игр [20].

1.1.2.3 Темпоральная логика

Темпоральная логика - расширение классической логики первого порядка, которая широко используется в спецификации и верификации комплексных систем. В эту логику добавлено время как дополнительное измерение, и таким образом логические свойства могут рассматриваться относительно времени, это

значит, что данный логический формализм подходит для описания таких знаний, в которых важным является изменение во времени.

Темпоральная логика используется во многих областях, включая информатику (как компьютерные науки) и искусственный интеллект, включая спецификацию распределенных систем [21], синтез программ из темпоральной спецификации [22], алгоритмическую верификацию посредством проверки модели [23], представление знаний и логический вывод [24], и темпоральные базы данных [25].

Однако, не смотря на разнообразные варианты использования темпоральных логик, все же область их применения остается весьма ограниченной, так как они применяются только в случаях, где необходимо использовать категорию времени.

1.1.2.4 Логические программы

Ещё одним инструментом описания знаний являются логические программы [26]. Формализм логических программ, а в последствии и первый язык логического программирования Prolog, были разработаны в конце 80х годов, несмотря на это данный подход продолжает широко использоваться по сей день. Важным отличием его от других формальных систем является то, что рассуждения в логических программах являются не монотонными, то есть добавление какого-либо факта к множеству фактов, может не увеличивать, а уменьшать количество знаний. Такой класс формализмов называется немонотонным [27]. Наряду с немонотонными логическими программами существуют хорновские логические программы, которые появились благодаря работам Хорна, в рамках изучения так называемых хорновских дизъюнкций: таких дизъюнкций в которых все одночлены являются литералами, и содержат не более одного дизъюнкта с отрицанием перед ним. Хорновские логические программы определяются только хорновскими дизъюнкциями и являются

подмножеством пересечения логических программ и фрагмента логики первого порядка.

Логические программы имеют большое количество приложений, в частности стоит отметить их применимость для создания семантической паутины [28]. Во многом это обязано тому, что для логических программ существует эффективный алгоритм вывода знаний [26]. Однако, не смотря на все преимущества логических программ в сравнении с другими методами описания знаний, выразительность не позволяет применять их в задачах, в которых необходимо выражать знания, которые предоставляют альтернативные варианты (в связи с отсутствием операции дизъюнкции), и в задачах, в которых необходимо обрабатывать объекты с большим количеством атрибутов (в связи с отсутствием кванторов существования).

1.1.2.5 Дескрипционная логика и профили OWL

На сегодняшний день наиболее широко используемым логическим инструментом представления знаний являются онтологии [29]. Язык OWL (Web Ontology Language), является стандартом описания онтологий, рекомендованным консорциумом W3C. OWL предоставляет 4 варианта описания онтологий, называемых профилями OWL, все они имеют своей математической основой различные фрагменты дескрипционной логики SROIQ [30-32], расширенной типами данных [33,34]. Все 4 профиля языка OWL имеют различную выразительность, то есть позволяют описывать знания с той или иной степенью детальности. Кроме того, наряду с профилями OWL существуют другие логические формализмы, выраженные пересечением дескрипционных логик и рассмотренных ранее систем. Важной разработкой, с точки зрения рассмотрения категории времени, являются темпоральные дескрипционные логики [35-37].

Для каждого из представленных профилей были разработаны алгоритмы, осуществляющие логический анализ онтологий, в частности позволяющие

выполнять классификацию концептов и определять противоречивость описанных знаний. Рассмотрим каждый из профилей OWL 2.

Самым выразительным языком среди всех своих профилей является язык OWL 2. OWL 2 основывается на дескрипционной логике SROIQ, которая была разработана на основе логики SHOIN [38], являющейся основой языка OWL DL, первого стандарта языка OWL. Логика SROIQ и стандарт OWL 2 появились в результате эволюции языка KL-ONE [7], который перерос в концептуальный язык ALC [39,40] - формализм являющийся основой всех, когда-либо разработанных дескрипционных логик. ALC получил широкое распространение благодаря строго определенной формальной семантике, позволяющей однозначно понимать любые описания, а также благодаря эффективному алгоритму проверки выполнимости концептов [39,41], который в дальнейшем был использован для осуществления вывода новых знаний.

Логика SROIQ оперирует понятиями концептов, описывающими классы объектов, ролями, являющимися бинарными предикативными отношениями и индивидами, которые отражают константы. Классы задаются с помощью операций конъюнкции, дизъюнкции, кванторов существования и всеобщности, а также операций кардинальности, что позволяет определять объединение и пересечение классов, задавать связи с другими классами и константами, а также определять классы объектов, находящихся в отношении с некоторым определенным количеством других объектов. Высокая выразительность данной логики достигается использованием аксиом, определяющих отношения не только между классами объектов, но и между предикатами. Например, аксиоматикой можно определить не только иерархию классов, но и иерархию самих отношений [42] и даже иерархию композиции ролей [43].

Совокупная выразительность логики SROIQ, соответственно языка OWL, интегрированная с процедурой осуществления логического вывода определила широкое применение онтологий на практике. Не смотря на то, что онтологии

были разработаны для создания семантической паутины, в настоящее время они получили очень широкое распространение как инструменты представления и хранения знаний. В первую очередь это касается знаний в биологии и медицине [44]. Учеными из медицинского университета города Вена, была разработана база знаний Genomic CDS Ontology [45], которая помогает поддерживать принятие медицинских решений, в частности назначение препаратов лечения, в зависимости от генетики пациента. Хотя данная онтология и не пользуется всеми выразительными возможностями языка OWL, все же не существует другого инструмента, позволяющего осуществлять вывод знаний с заданной выразительностью.

Другим не менее практическим значимым применением онтологий является онтология LUCADA [46], которая содержит информацию об онкологических заболеваниях органов дыхания, большая часть которой посвящена онкологии легких. Онтология LUCADA является семантическим уровнем в программном продукте Lung Cancer Assistant, которая является системой поддержки принятия решений по назначению лечения пациентам, что позволяет успешно бороться с наиболее опасным видом онкологических заболеваний. Среди медицинских онтологий также стоит отдельно отметить онтологию GALEN, которая была разработана для обмена информации между медицинскими учреждениями и её однозначного понимания.

Инструмент онтологий получил распространение не только в медицине и биологии, но и в компьютерных науках. Итальянскими учеными был предложен подход для использования семантики онтологий в проверке моделей бизнес-процессов [47]. Разработав онтологию нотации и инструмент автоматической генерации онтологий из моделей бизнес-процессов, успешно удается решать задачи:

• верификации семантической разметки отдельных элементов модели, в соответствии с определенными ограничениями;

• подсказывания для корректной разметки процессов;

• ответов на запросы, включающих информацию о процессах, например:

"выдать информацию о всех действиях с кредитной картой";

Онтологии выразительности OWL 2 DL, имеют ещё большее количество применений и реализаций, однотипных с уже описанными вариантами применения.

Профиль OWL 2 EL имеет своей математической основой дескрипционную логику EL [48], которая обязана своим появлением предметным областям, в которых необходимо описывать знания, состоящие из большого количества классов и их свойств [49]. Данная логика является фрагментом логики SROIQ, в которой для описания классов разрешены только операция конъюнкции и квантор существования, что делает этот профиль менее выразительным, чем профиль OWL 2, однако в отличие от логики SROIQ разрешающая процедура логики EL, имеет полиномиальную вычислительную сложность [50], это позволяет применять OWL 2 EL на практике в более широком диапазоне случаев чем OWL 2, в частности профиль OWL 2 EL широко используется в биомедицинских онтологиях. Эффективность алгоритма классификации понятий продемонстрирована разработкой системы ELK [51], которая классифицирует базы знаний колоссальных объемов (около 300000 понятий) менее чем за 1 секунду времени.

Ярким примером использования OWL 2 EL онтологий является онтология SNOMEDCT: систематическая номенклатура медицины - клинические термины. Данная онтология представляет собой терминологию медицинских терминов, которая используется в системах электронного здравоохранения в США и Великобритании [52].

OWL 2 RL нацелен на использование в приложениях, в которых необходимо осуществление расширяемых задач логического анализа, без сокрытия слишком большой части выразительности OWL 2. Алгоритмы

Список литературы диссертационного исследования кандидат наук Григорьев, Андрей Викторович, 2013 год

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

1. Губин М.Ю., Разин В.В., Тузовский А.Ф. Применение семантических сетей и частотных характеристик текстов на естественных языках для создания семантических метаописаний // Проблемы информатики. 2011.N. 5. С. 53-58. Новосибирск: Институт вычислительной математики и математической геофизики Сибирского отделения РАН.

2. Hayes P. RDF Semantics [Электронный ресурс] // W3C Official Site. 2004. URL: http://www.w3.org/TR/2004/REC-rdf-mt-20040210/ (дата обращения 28.06.2013)

3. М. Е. J. Newman. The structure and function of complex networks. // SIAM Review. 2003. Vol. 45(2). P. 167-256. doi:10.1137/S003614450342480.

4. Сукач Е.И., Ратобыльская Д. В., Мережа В. Л. Реализация вывода в семантической сети с использованием вероятностно-алгебраического моделирования // Материалы международной научно-технической конференции OSTIS-2011, С. 241-246. Минск: БГУИР.

5. Trentelman К. Survey of Knowledge Representation and Reasoning Systems. 2009. Edinburgh: DSTO.

6. Fellbaum C. WordNet and wordnets. // Encyclopedia of Language and Linguistics, Second Edition. 2005. Oxford: Elsevier, P. 665-670.

7. R.J. Brachman and J.G. Schmolze, An overview of the KL-ONE knowledge representation system. // Cognitive Science. 1985. Vol. 9(2) P. 171-216.

8. Clark P., Porter B. Using Access Paths to Guide Inference with Conceptual Graphs // Proceedings of the International Conference on Conceptual Structures -ICCS'97. Seattle, Washington, USA, 3-8 August, 1997. P. 521-535. Berlin: Springer. 1997.

9. Motik В., Patel-Schneider P.F., Grau B.C. OWL 2 Web Ontology Language Direct Semantics (Second Edition). [Электронный ресурс]. // W3C Official Site. 2012. URL: http http://www.w3.org/TR/2012/REC-owl2-direct-semantics-20121211/ (дата обращения 29.06.2013)

10. Schneider M. OWL 2 Web Ontology Language RDF-Based Semantics (Second Edition). // W3C Official Site. 2012. URL: http://www.w3.org/TR/2012/REC-owl2-rdf-based-semantics-20121211/ (дата обращения 29.06.2013)

11. Motik В., Patel-Schneider P.F., Parsia B. OWL 2 Web Ontology Language Structural Specification and Functional-Style Syntax (Second Edition). [Электронный ресурс]. // W3C Official Site. 2012. URL: http://www.w3.org/TR/2012/REC-owl2-syntax-20121211/ (дата обращения 29.06.2013)

12. Судоплатов C.B., Овчинникова Б.В. Математическая логика и теория алгоритмов. М.: ИНФРА-М, 2004.

13. Клини С. К. Математическая логика. М.: МИР, 1973.

14. Игошин В.И. Математическая логика и теория алгоритмов: учебное пособие для студ. высш. учеб. заведений. М.: Академия, 2008.

15. Гуц А.К. Математическая логика и теория алгоритмов: учебное пособие. Омск: Наследие, 2003.

16. Brachman RJ, Levesque Н. Knowledge representation and reasoning. Elsevier. 2004.

17. Halpern J., Moses Y. Knowledge and common knowledge in a distributed environment//JACM. 1990. Vol. 37(3). P. 549-587.

18. Harel D. Dynamic logic // Handbook of Philosophical Logic. Vol. II. 1984. P. 497-604.

19. M. Wooldridge. An Introduction to Multi-agent Systems. John Wiley & Sons.

2002.

20. Hoek W.,Pauly M. Modal logic for games and information // Modal Logic Handbook. P. 1077-1148. URL: http://www.csc.liv.ac.uk/%CB%9Cfrank/MLHandbook

21. Manna Z., Pnueli A. The Temporal Logic of Reactive and Concurrent Systems: Specification. New York: Springer. 1992.

22. Kupferman O., Vardi M. Synthesis with Incomplete Information // Advances in Temporal Logic. 2000. Dordrecht: Kluwer Academic Publishers. P. 109-127.

23. Clarke E., Grumberg O., Peled D.A. Model Checking. 2000. New York: MIT

Press.

24. Artale A., Franconi E. Temporal Description Logics // Handbook of Temporal Reasoning in Artificial Intelligence. Elsevier. 2005. P. 375-388.

25. Chomicki J., Toman D. Temporal Logic in Information Systems // Logics for Databases and Information Systems. Elsevier. 1998. P. 31-70.

26. Baral C., Gelfond M. Logic Programming and Knowledge Representation. // Journal of Logic Programming. 1994. N. 20. P. 73-148.

27. Grosof B.N., Volz R., Horrocks I., Decker S. Description Logic Programs: Combining Logic Programs with Description Logic. // Proceeding of WWW '03 Proceedings of the 12th international conference on World Wide Web, Budapest, Hungary. May 20-24, 2003. P. 48-57. NY, ACM Publishing, 2003.

28. Boley. H. Knowledge Bases in the World Wide Web: A Challange for Logic Programming // Proceedings of the JICSLP'96 Post-Conference Workshop on Logic Programming Tools for Internet Applications. Bonn. 5-6 September, 2006. P. 139-147. URL: http://clement.info.umoncton.ca/~lpnet

29. Калиниченко JI. А. Экспансия онтологий: «онтологически базированные» информационные системы // Труды Второго симпозиума «Онтологическое моделирование: состояние, направления исследований и применения», Казань, 11-12 октября 2010. М.: ИПИРАН, 2011. С. 29-44.

30. Horrocks I., Kutz О., Sattler U. The Irresistible SRIQ // Proceedings of the OWLED'05 Workshop on OWL: Experiences and Directions. Galway, Ireland. November 11-12, 2005. P. 87-99. URL: http://ceur-ws.org/Vol-188/

31. Kazakov Y. An Extension of Complex Role Inclusion Axioms in the Description Logic SROIQ. // Proceeding IJCAR'10 Proceedings of the 5th international conference on Automated Reasoning. Edinburgh, UK, July 16-19, 2010. P. 472-486. doi:10.1007/978-3-642-14203-l_40

32. Horrocks I., Kutz O., Sattler U. The Even More Irresistible SROIQ. // Proceedings of the 10th International Conference on the Principles of Knowledge Representation and Reasoning. Lake District, UK, 2-6 June, 2006. P. 57-67. Menlo Park: AAAI Press.

33. Peterson D., Gao S., Malhotra A., Sperberg-McQueen C.M., Thompson H.S. W3C XML Schema Definition Language (XSD) 1.1 Part 2: Datatypes [Электронный ресурс] // W3C Official Site. 2012. URL: http://www.w3.org/TR/2012/REC-xmlschemal 1-2-20120405/ (дата обращения 2.07.2013)

34. Boris Motik, Ian Horrocks. OWL Datatypes: Design and Implementation. // Proceedings of the 7th International Semantic Web Conference. Karlsruhe, Germany, 26-30 October, 2008. P. 307-322. New York: Springer.

35. Artale A., Franconi E. Introducing Temporal Description Logics // Proceedings of the International Conference on Temporal Representation and Reasoning (TIME-99), Orlando, USA, 1-2 May, 1999. P. 2-5. URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=777962

36. Artale A., Franconi E. A Temporal Description Logic for Reasoning about Actions and Plans. // Journal of Artificial Intelligence Research. 1998. N. 9. P. 463-506.

37. Sturm H., Wolter F. A tableau calculus for temporal description logic: the expanding domain case. // Journal of Logic and Computation. 2000. Vol. 2001. P. 809838.

38. Horrocks I. R. Optimizing tableaux decision procedures for description logics. PhD thesis. University of Manchester. 1999;

39. Schmidt-Schauss M., Smolka G. Attributive concept descriptions with complements. // Artificial Intelligence. 1991. Vol. 48(1). P. 1-26.

40. Hollunder B., Nutt W., Schmidt-Schauss M. Subsumption algorithms for concept description languages. In Proceedings of the 9th Europe Conference on Artificial Intelligence, Stockholm, Sweden, 6 August, 1990. P. 348-353. London: Pitman. 1990.

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

42. Ian Horrocks, Ulrike Sattler. A Description Logic with Transitive and Inverse Roles and Role Hierarchies. // Journal of Logic Computation. 1999. Vol. 9(3). P. 385410. doi: 10.1093/logcom/9.3.385.

43. Simancik F. Elimination of Complex RIAs without Automata // Proceedings of the 2012 International Workshop on Description Logics, Rome, Italy, 7-10 June 2012. P. 119-126. URL: http://www.ceur-ws.org/Vol-846/

44. Jovic A., Prcela M., Gamberger D. Ontologies in Medical Knowledge Representation // Proceedings of the 29th International Conference on Information Technology Interfaces, Dubrovnik, Croatia, 25-28 June, 2007. P. 535-540. URL: http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=4283719

45. Samwald M. Genomic CDS: an example of a complex ontology for pharmacogenetics and clinical decision support. // Proceeding of the 2nd OWL Reasoner Evaluation Workshop (ORE 2013), Ulm, 22 July 2013. P. 128-133. URL: http://ceur-ws.org/Vol-1015/

46. Sesen В., Jimenez-Ruiz E., Banares-Alcantara R., Brady M. Evaluating OWL 2 Reasoners in the context of Clinical Decision Support in Lung Cancer Treatment Selection. // Proceeding of the 2nd OWL Reasoner Evaluation Workshop (ORE 2013), Ulm, 22 July 2013. P. 128-133. URL: http://ceur-ws.org/Vol-1015/

47. Chiare Di Francescomarino, Chiara Chidini. Reasoning on semantically annotated processes. // Lecture Notes in Computer Science. Vol. 5364. 2008. P. 132146.

48. Baader. F., Brandt S., Lutz. C. Pushing the EL Envelope. Proceedings of the 19th Joint International Conference on Artificial Intelligence, Edindurgh, Scotland, 30 July - 5 August, 2005. P. 364-369. URL: www.cse.lehigh.edu/~munoz/Publications/IJCAI05W-proceedings.pdf

49. Motik В., Grau B.C., Horrocks I., Wu Z., Fokoue A., Lutz C. OWL 2 Web Ontology Language Profiles (Second Edition) [Электронный ресурс] // W3C Official Site. 2012. URL: http://www.w3.org/TR/2012/REC-owl2-profiles-201212U/ (дата обращения 2.07.2013)

50. Baader. F., Brandt S., Lutz. C. Pushing the EL Envelope Further // Proceedings of the OWLED 2008 DC Workshop on OWL: Experiences and Directions, Washington, 1-2 April, 2008. P. 6-12.

51. Kazakov Y., Krotzsch M., Simancik F. ELK Reasoner: Architecture and Evaluation. // Proceeding of the 1st OWL Reasoner Evaluation Workshop (ORE 2012), Manchester, 1 July 2012. P. 101-110. URL: http://ceur-ws.org/Vol-858/

52. Ryan A. Towards semantic interoperability in healthcare: ontology mapping from SNOMED-CT to HL7 version 3 // Proceedings of the 2nd Australasian workshop

on Advances in ontologies. Hobart, Australia,5 December 2006. P. 69-74. Darlinghurst: Australian Computer Society.

53. BioPortal [Электронный ресурс]. 2011. //URL: http://bioportal.bioontology.org (дата обращения 30 мая 2013).

54. С. Maria Keet, Ronnel Alberts, Aurona Gerber. Enhancing web portals with Ontology-Based Data Access: the case study of South Africa's Accessibility Portal for people with disabilities // Proceedings of the 5th OWLED Workshop on OWL: Experiences and Directions. Karlsruhe, Germany, October 26-27, 2008. P. 14-19 URL: http://ceur-ws.org/Vol-432/

55. Поршнев Я.И., Силич Н.Г. Возможности использования онтологий и семантических средств в процессе обучения // Школьные технологии. 2010. № 4. С. 108-112.

56. Glavinic V., Rosic М., Zelic М. Leveraging the Semantic Web for Adaptive Education. // Proceedings of the 6th Symposium of the Workgroup Human-Computer Interaction and Usability Engineering, 2010. Klagenfurt, Austria, November 4-5, 2010. P. 497-500. New York: Springer. 2010.

57. Афонин С., Козицын А. Использование онтологий в поисковых системах // Материалы Всероссийской конференции с международным участием "Знания-Онтологии-Теории" 2009, 22-24 ноября, г. Новосибирск. — Т. 2. — 2009. — С. 47-52.

58. Haarslev V., Moller R. Applying an ALC ABox Consistency Tester to Modal Logic SAT Problems // Proceedings of the International Conference TABLEAUX'99. New York, USA, June 7-11 1999. P. 24-29. New York: Springer. 1999.

59. Hefflin J. OWL Web Ontology Language Use Cases and Requirements. [Электронный ресурс]. 2009. URL: http://www.w3.org/TR/2004/REC-webont-req-20040210/ (дата обращения 29.06.2013).

60. Garcia R., Tsinaraki C., Celma O., Christodoulakis S. Multimedia Content Description Using Semantic Web Languages // Semantic Multimedia and Ontologies, 2008. P. 16-54.

61. Ghosh H., Chaudhury S., Kashyap K., Maiti B. Ontology specification and integration for multimedia applications // Ontologies. 2007. P. 265-296.

62. Harit G., Chaudhury S., Ghosh H. Managing document images in a digital library: An ontology guided approach // Proceedings of the 1st International Workshop on Document Image Analysis for Libraries, Palo Alto, USA. 23-24 January, 2004. P. 64-92. Washington: IEEE.

63. Rudolph S. Foundations of Description Logics. // Reasoning Web. Semantic Technologies for the Web of Data - 7th International Summer School 2011, Galway, Ireland, August 23-27, 2011. P. 76-136. doi: 10.1007/978-3-642-23032-5

64. Calvanese D., Eiter T., Ortiz M. Regular path queries in expressive description logics with nominals. // Proceedings of the 21 st International Conference on Artificial Intelligence, Pasadena, California, USA, 11-17 July, 2009.P. 714-720.URL:

65. Kazakov Y. Consequence-driven reasoning for horn SHIQ ontologies. // Proceedings of the 21st International Conference on Artificial Intelligence, Pasadena, California, USA, 11-17 July, 2009. P. 2040-2045. URL:

66. Buchheit M., Donini F.M., Schaerf A. Decidable Reasoning in Terminological Knowledge Representation Systems. // Journal of Artificial Intelligence Research. 1993. Vol. 1. P. 109-138.

67. Donini F.M., Massacci F. EXPTIME tableaux for ALC // Artificial Intelligence. 2000. Vol. 124(1). P. 87-138.

68. Horrocks I., Sattler U., Tobies S. Practical Reasoning for Very Expressive Description Logics. // Logic Journal of the IGPL. 2000. Vol. 8(3). P. 239-264.

69. I. Horrocks, U. Sattler. S. Tobies. Reasoning with Individuals for the Description Logic SHIQ. // 17th International Conference on Automated Deduction, Pittsburgh, Pennsylvania, USA, June 17-20, 2000. P. 482-496. New York: Springer. 2000.

70. Horrocks I., Sattler U. A Tableau Decision Procedure for SHOIQ. // Journal of Automated Reasoning. 2007. Vol. 39(3). P. 249-276.

71. Baader F., Sattler U. An Overview of Tableau Algorithms for Description Logics. // Studia Logica. 2001. N. 69. P. 5-40.

72. Schaerf A. Reasoning with individuals in concept languages // Data and Knowledge Engineering. 1994. Vol. 13(2). P. 141-176.

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

74. Boris Motik, Rob Shearer, Ian Horrocks. A Hypertableau Calculus for SHIQ. // Proceedings of the 2007 International Workshop on Description Logics, Brixen, Italy, 8-10 June 2007. P. 419-426. URL: http://www.ceur-ws.org/Vol-250/

75. Khodadadi M., Schmidt R.A., Tishkovsky D. An abstract tableau calculus for the Description Logic SHOI Using Unrestricted Blocking and Rewriting // Proceedings of the 2012 International Workshop on Description Logics, Rome, Italy, 7-10 June, 2012. P. 144-149. URL: http://www.ceur-ws.org/Vol-846/

76. Kolovski V., Parsia B., Sirin E. Extending the SHOIQ(D) Tableaux with DL-safe Rules: First Results // Proceedings of the 2006 International Workshop on Description Logics, Lake District, UK, 30 May - 1 June, 2006. URL: http://www.ceur-ws.org/Vol-189/

77. Horrocks I., Sattler U. Ontology Reasoning in the SHOQ(D) Description Logic. // Proceedings of the International Joint Conference on Artificial Intelligence, Seattle, 4-10 August, 2001. P. 199-204. URL:

http://ijcai.Org/Past%20Prcceedings/I JCAI-200 l/PDF/IJCAI-2001 -b.pdffl JCAI-2001 -b.pdf

78. Colbourn C.J., Booth K.S. Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs // SIAM Journal of Computing. 1981. Vol. (10). 203-225. doi:10.1137/0210015

79. M. Horridge, S. Bechhofer. The OWL API: A Java API for OWL Ontologies //Journal Semantic Web. 2011. Vol. 2(1). P. 11-21.

80. Tarjan R. Depth-First Search and Linear Graphs Algorithms. // SIAM Journal of Computing. Vol. 1(2). 1972. P. 146-160.

81. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы. Построение и анализ, 2-е издание. М.: Вильяме, 2007.

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

83. Ding Y., Haarslev V. Tableau Caching for Description Logics with Inverse and Transitive Roles // Proceedings of the 2006 International Workshop on Description Logics (DL'2006), Lake District, May 30 - June 1, 2006. P. 143-149. URL: http://www.ceur-ws.Org/V ol-189/

84. Steigmiller A., Liebig Т., Glimm B. Extended Caching, Backjumping, and Merging for Expressive Description Logics // Proceedings of the 6th international joint conference on Automated Reasoning, Manchester, UK, 26-29 June, 2012. P. 514-529. Berlin: Springer-Verlag. 2012.

85. Nguyen L.A., Szalas A. Tableaux with global caching for checking satisability of a knowledge base in the description logic SH // Computational Collective Intelligence. 2010. Vol. (1). P. 21-38.

86. Rajeev G., Nguyen L.A. EXPTIME Tableaux for ALC Using Sound Global Caching // Journal of Automated Reasoning. 2013. Vol. 50(4). P. 355-381.

87. Linh Anh Nguyen. A cut-free ExpTime tableau decision procedure for the description logic SHI // Proceedings of 3rd International Conference on Computational Collective Intelligence - Technologies and Applications. Gdynia, Poland.21-23 September, 2011. P. 572-581. New York: Springer. 2011.

88. Moses Charikar, P. Indyk, R. Panigrahy. New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching and Related Problems. // Proceedings of the 29th International Colloquium. Malaga, Spain. 8-13 July, 2002. P. 451-462. New York: Springer. 2002.

89. Ouyang M. How good are branching rules in DPLL? // Discrete Applied Mathematics. 1998. N. 89. P. 281-286.

90. Loveland D.W. Automated Theorem Proving: A Logical Basis. Amsterdam. North-Holland. 1978.

91. Davis M., Logemann G., Loveland D. A Machine Program For TheoremProving // Communications of the ACM. 1962. N. 5. P. 394-397.

92. Farsiniamarj N., Haarslev V. Practical reasoning with qualified number restrictions: A hybrid Abox calculus for the description logic SHQ // Journal AI Communications - Practical Aspects of Automated Reasoning. 2010. Vol. 23(2-3). P. 205-240.

93. Haarslev V., Moller R. Optimizing Reasoning in Description Logics with Qualified Number Restrictions // Proceedings of the International Workshop on Description Logics (DL'2001), Stanford 1-3 August, 2001. P. 142-151. URL: http://www.ceur-ws.orgA/- ol-49/

94. Mosurovic M., Krdzavac N. Some Optimizations R+IQ Tableau Algorithm // Proceedings of the 2nd International conference "Optimization and applications", Petrovac, Montenegro, 25 September - 2 October, 2011. P. 47. URL: http://www.ccas.ru/optima201 l/abstracts_e.html

95. Bron C., Kerbosch J. Finding All Cliques of an Undirect Graph // Communications of the ACM. 1973. N. 1. P. 575-576.

96. Baader F., Hollunder B., Nebel B., Profitlich H.-J. An Empirical Analysis of Optimization Techniques for Terminological Representation Systems. // Applied Intelligence. 1993. Vol. 4(2). P. 109-132.

97. Knublauch H., Fergeson R.W., Noy N.F., Musen M.A. The Protege OWL Plugin: An Open Development for Semantic Web Applications // Proceedings of the 3rd International Semantic Web Conference (ISWC2004), Hiroshima, 7-11 November, 2004. P. 229-243. New York: Springer-Vierlag. 2004.

98. Hollunder B., Laux A., Profitlich H.-J., Trenz T. KRIS-manual // Technical report. Deutsches Forschungszentrum fur Kunstliche Intelligenz (DFKI), 1991. URL: http://w5.cs.uni-saarland.de/teaching/ss02/materialien/kris-manual.pdf

99. Goncalves R., Bail S., Jimenez-Ruiz E., Matentzoglu N., Parsia B., Glimm B., Kazakov Y. (eds.) Proceeding of the 2nd OWL Reasoner Evaluation Workshop (ORE 2013). Ulm, 22 July 2013. URL: http://ceur-ws.org/Vol-858/

100. Horrocks I., Patel-Schneider P.F. Optimising Description Logic Subsumption. // Journal of Logic and Computation. 1999. Vol. 9(3). P. 267-293.

101. Nguyen L.A. An Efficient Tableau Prover using Global Caching for the Description Logic ALC. // Fundamenta Informaticae. 2009. Vol. 93(1-3). P. 273-288.

102. Tsarkov D., Palmisano I. Chainsaw: Metareasoner for Large Ontologies. // Proceeding of the 1st OWL Reasoner Evaluation Workshop (ORE 2012), Manchester, 1 July 2012. P. 29-37. URL: http://ceur-ws.org/Vol-858/

103. Tsarkov D., Horrocks I. FaCT++ Description Logic Reasoner: System Description // Proceedings of the 3rd International Joint Conference on Automated Reasoning. 16-21 August, 2006. Seattle: Springer, 2006. P. 292-297.

104. Horrocks I., Motik B., Wang Z. The HermiT OWL Reasoner. // Proceeding of the 1st OWL Reasoner Evaluation Workshop (ORE 2012), Manchester, 1 July 2012. P. 119-127. URL: http://ceur-ws.org/Vol-858/

105. Romero A.A, Grau B.C, Horrocks I. Modular Combination of Reasoners for Ontology Classification // Proceeding of the 25th Description Logic Workshop (DL

2012), Rome, Italy. June 7-10, 2012. P. 15-25. URL: http://ceur-ws.org/Vol-846/

106. Pan J.Z., Ren Y., Jekjantuk N., Garcia J. Reasoning the FMA Ontologies with TrOWL // Proceeding of the 2nd OWL Reasoner Evaluation Workshop (ORE

2013), Ulm, 22 July 2013. P. 87-93. URL: http://ceur-ws.org/Vol-1015/

107. Weihong S., Spencer B., Wiechang D. A Transformation Approach for Classifying ALCHI(D) Ontologies with a Consequence-based ALCH Reasoner.// Proceeding of the 2nd OWL Reasoner Evaluation Workshop (ORE 2013), Ulm, Germany. 22 July 2013. P. 39-45. URL: http://ceur-ws.org/Vol-1015/

108. Sertkaya B. The ELepHant Reasoner System Description// Proceeding of the 2nd OWL Reasoner Evaluation Workshop (ORE 2013), Ulm,Grmany.July22, 2013. P. 87-93. URL: http://ceur-ws.org/Vol-1015/

109. Mendez J. jcel: A Modular Rule-based Reasoner. // Proceeding of the 1st OWL Reasoner Evaluation Workshop (ORE 2012), Manchester, 1 July 2012. P. 112118. URL: http://ceur-ws.org/Vol-858/

110. Jimenez A.M., Lawley M. Snorocket 2.0: Concrete Domains and Concurrent Classification // Proceeding of the 2nd OWL Reasoner Evaluation Workshop (ORE 2013), Ulm, 22 July 2013. P. 32-38. URL: http://ceur-ws.org/Vol-1015/

111. Goncalves R., Bail S., Jimenez-Ruiz E., Matentzoglu N., Parsia B., Glimm B., Kazakov Y. OWL Reasoner Evaluation (ORE) Workshop 2013 Results: Short Report // Proceeding of the 2nd OWL Reasoner Evaluation Workshop (ORE 2013), Ulm, Germany. July 22, 2013. P. 87-93. URL: http://ceur-ws.org/Vol-1015/.

о

?

1! 1

1 -I

щ

} \

^ I

9

г 1

0^1 ?

о! о

0\1

Ф

0|1

6

-14

о

0'1 0|1 0]1

0:1 Л.

Л

ОМ

t

?

0(1

о

X X1

0/1

£

I

ф

0 0

Ой

у

0 1

0 1

9

0; 1 ?

0 1

о и ?

0|1 ?

0 0

Рисунок 26 - Сетевая модель концептов