Разработка методов темпоральной спецификации и дедукции для онтологий тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Нгуен Тхи Минь Ву

• Нгуен Тхи Минь Ву
• кандидат наук
• 2017

Оглавление диссертации кандидат наук Нгуен Тхи Минь Ву

ВВЕДЕНИЕ

ГЛАВА 1 ТЕМПОРАЛЬНЫЕ ФОРМАЛИЗМЫ

1.1 Общие сведения об онтологиях

1.2 Неявное моделирование времени

1.2.1 Ситуационное исчисление

1.2.2 Исчисление событий

1.2.3 Системы типа STRIPS

1.2.4 Сети Петри

1.3 Явное моделирование времени

1.3.1 Модальные темпоральные логики

1.3.2 Темпоральные интервальные логики

1.3.3 Метрическая точечная модель времени

1.3.4 Комбинация качественных и метрических моделей времени

1.4 Дескриптивные логики

1.4.1 Синтаксис дескриптивной логики

1.4.2 Семантика дескриптивной логики

1.4.3 Темпоральные дескриптивные логики

1.5 Вывод по главе

ГЛАВА 2 ЯЗЫКИ ТЕМПОРАЛЬНОЙ СПЕЦИФИКАЦИИ ОНТОЛОГИЙ ДЛЯ СИСТЕМЫ «БИНАРНАЯ МОДЕЛЬ ЗНАНИЙ»

2.1 О системе «Бинарная Модель Знаний»

2.1.1 Язык структурной спецификации ЯСС

2.1.2 Язык логической спецификации ЯЛС

2.2 Представление времени в системе БМЗ

2.2.1 Язык темпоральной спецификации ЯТС

2.2.2 Дедукция в языке ЯТС

2.2.3 Язык спецификации переходов ЯСП

2.3 Вывод по главе

ГЛАВА 3 ДЕДУКЦИЯ ДЛЯ ИНТЕРВАЛЬНЫХ ОНТОЛОГИЙ

3.1 Интервальная логика Аллена

3.1.1 Полиномиальный метод дедукции в логике ЬЛ

3.1.2 Метод дедукции в логике ЬЛ с преобразованием интервальных отношений

3.2 Булево расширение интервальной логики Аллена

3.2.1 Алгоритм вывода в логике ЬЛ+

3.2.2 Алгоритм распознавания противоречивости онтологий в

логике ЬЛ+

3.3 Булево расширение интервальной логики Аллена с включением метрической информации

3.3.1 Дедукция в логике ^ЬЛ

3.3.2 Алгоритм распознавания противоречивости онтологий в

логике ^ЬЛ

3.3.3 Дедукция в логике ^ЬЛ+

3.3.4 Алгоритм дедукции в логике ^ЬЛ+

3.3.5 Нахождение ответов на запросы к интервальным онтологиям в логике ^ЬЛ+

3.4 Выводы по главе

ГЛАВА 4 ПРИМЕРЫ ПРИМЕНЕНИЯ РАЗРАБОТАННЫХ МЕТОДОВ И АЛГОРИТМОВ

4.1 Спецификация темпоральных отношений в базах знаний для потоков работ

4.1.1 Поток работ

4.1.2 Пример потока работ и спецификации онтологии для этого потока работ

4.2 Спецификация онтологии для системы моделирования движения поездов

4.2.1 Спецификация онтологии в языках ЯСС и ЯТС

4.2.2 Запросы к онтологии

4.3 Выводы по главе

ГЛАВА 5 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ

5.1 Структура программы

5.2 Графический интерфейс программы

5.3 Внутреннее представление онтологии

5.4 Работа с синтаксическим анализатором

5.5 Работа с деревом вывода

5.6 Внедрение разработанной программы

5.7 Выводы по главе

СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ 1 Таблица композиции темпоральных отношений для

интервальной алгебры Аллена

ПРИЛОЖЕНИЕ 2 Графы, ассоциированные с системами простых неравенств

для онтологии О в примере

ПРИЛОЖЕНИЕ 3 Акты о внедрении

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

ВВЕДЕНИЕ

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

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

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

Многие предметные области для реальных приложений, содержат объекты, зависящие от времени. Зависящее от времени понятие - это событие. События связываются между собой темпоральными (временными) отношениями (например, такими, как «раньше», «позже», «одновременно», «в течение», «всегда в будущем» и т.п.). Для спецификации темпорального знания в онтологиях нужны соответствующие формальные языки. К настоящему времени разработано и исследовано достаточно много языков онтологий для статических предметных областей, и некоторые из этих языков рекомендованы консорциумом W3C в качестве стандартов. ^3С - организация, разрабатывающая и внедряющая технологические стандарты для Веба.) Но, в отличие от этого, пока мало предложено языков онтологий для динамических

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

Замечание. Работы в области, к которой относится диссертация, в настоящее время ведутся почти исключительно за рубежом. Наиболее близкие работы были выполнены C. Welty, Z. Zhang, A. Artale, E. Franconi, C. Lutz, F. Wolter, C. Gutierrez, М. Захарьящевым, Р. Кончаков и др.

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

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

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

Для достижения указанных целей необходимо решить следующие задачи:

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

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

• разработка языков для описания интервальных онтологий;

• разработка методов и алгоритмов дедукции для интервальных онто-логий;

• программная реализация разработанных методов и алгоритмов.

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

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

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

Научные результаты и их новизна.

1) Разработан язык темпоральной спецификации ЯТС для системы онтологического моделирования «Бинарная Модель Знаний» (БМЗ). Язык ЯТС позволяет представлять информацию о событиях и темпоральное отношение между ними.

2) Введено понятие интервальной онтологии, ассоциированной с онтологией, представленной в языке ЯТС. Определен язык ЬЛ+, предназначенный для спецификации интервальных онтологий. Он является булевым расширением языка интервальной логики Аллена.

3) Определены языки цЬЛ и цЬЛ+, являющиеся метрическим расширением и булевым метрическим расширением языка интервальной логики Аллена. Предложенные языки позволяют описывать не только качественные, но и количественные зависимости между темпоральными интервалами.

4) Разработан полный метод дедукции для интервальных онтологий, представленных в языках ЬЛ+, цЬЛ и цЬЛ+. На основе предложенного метода также разработаны алгоритмы дедукции и алгоритм вычисления запросов.

Эти научные результаты являются новыми.

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

Практическая значимость работы подтверждена использованием полученных результатов в ООО «Империя соусов» для онтологического моделирования бизнес-процесса перевозки готовой продукции, и в учебном процессе ФГБОУ ВО «НИУ «МЭИ» при изучении дисциплины «Прикладная семиотика», о чём имеются акты о внедрении.

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

1. Международной науч.-техн. конференции «Открытые семантические технологии проектирования интеллектуальных систем». - (Минск, февраль 2015 г.);

2. Международной науч.-техн. конференции «Открытые семантические технологии проектирования интеллектуальных систем». - (Минск, февраль 2016 г.);

3. 9th International Conference on Application of Information and Communication Technologies. - (Rostov-on-Don, July 2015).

4. Международной научной конференции, посвященной 25-летию Института информационных и вычислительных технологий «Информатика и прикладная математика». - (Алматы, сентябрь 2016). Публикации. Основные результаты, полученные при выполнении диссертационной работы, опубликованы в 1 1 печатных работах, включая 2 статьи в журналах из перечня ВАК.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка использованной литературы (79 наименований) и 3 приложений. Диссертация содержит 154 страниц машинописного текста (без приложений), 39 рисунков и 10 таблиц. Краткое содержание работы

В первой главе «Темпоральные формализмы» дан обзор формальных языков для спецификации темпоральных свойств и отношений в онтологиях, применяемых в информационных системах. В частности, описаны: интервальная логика Халперна-Шоэма (HS), интервальная логика Аллена (LA) и две темпоральные дескриптивные логики. В дальнейшем эти логики используются для сравнения с разработанными в диссертации логиками.

Во второй главе «Языки темпоральной спецификации онтологий для системы «Бинарная Модель Знаний» описан разработанный нами язык темпоральной спецификации свойств и отношений в онтологиях (ЯТС) для си-

стемы «Бинарная Модель Знаний» (БМЗ). Также кратко описан язык ЯСП спецификации переходов, который тоже разработан для системы БМЗ. Он используется для спецификации динамических предметных областей, в частности, для описания реактивных систем.

Замечание. БМЗ - это инструментальная система, предназначенная для решения задач онтологического моделирования, таких, как построение, анализ и интерпретация формальных онтологий [4, 5, 58].

Язык ЯТС характеризуется следующими чертами:

• ЯТС - концептуальный язык с семантикой, основанной на формальной модели понятия;

• Язык ЯТС объектно-ориентирован;

• ЯТС расширяет языки структурной и логической спецификации (ЯСС и ЯЛС соответственно), входящие в систему «Бинарная Модель Знаний»;

• В ЯТС включены связки Аллена, выражающие фундаментальные бинарные отношения между темпоральными (временными) интервалами («раньше», «встречает», «в течение», «начинает», «перекрывает», «заканчивает», «равен»);

• ЯТС содержит темпоральные кванторы SOMETIME («когда-нибудь») и ALLTIME («все время»), а также темпоральное отношение AT («в данное время».

С записанной в языке ЯТС онтологией ассоциируются базы фактов, выражающие информацию о текущих состояниях моделируемой предметной области. База фактов представляется в реляционной базе данных, благодаря чему имеется возможность использовать СУБД для выполнения транзакций (в частности, для вычисления ответов на запросы к базе фактов).

Приведем примеры выражений языка ЯТС, которые дадут некоторое представление о выразительных возможностях этого языка.

Автомобиль[Марка:String,Габариты:(Длина-мм:Integer, Ширина-мм:Integer, BbicoTa-MM:Integer) ,

Двигатель:Двигатель]. Это предложение утверждает, что каждый пример (экземпляр) понятия (класса) Автомобиль имеет два атрибута Марка и Габариты, а также компоненту Двигатель:

Двигатель[Тип:Integer/. Мощность ^c:Integer,

КоробкаПередач^^1пд]. (Персона Владеет Автомобиль)[ДатаРегистр:Date]. Это предложение определяет бинарную связь (отношение) Владеет между примерами понятия Персона и понятия Автомобиль. Связь эта имеет атрибут ДатаРегистр с доменом Date. EVENT Владеет.

Это предложение утверждает, что бинарная связь Владеет является событием, т.е. его примеры существуют в некоторых интервалах времени. Таким образом, понятие Владеет имеет (неявно представленный) атрибут Int (интервал), значениями которого служат пары [х, у], где х и у - элементы типа данных Time и х раньше у.

ЛА.П. Иванов' Владеет (SOMETIME X) SOME

Автомобиль(Марка=лAudi 200'); X BEFORE NOW. Это предложение утверждает, что Иванов владел раньше (в течение некоторого интервала времени X) одним из автомобилей марки Ауди 200. ^Бывший владелец автомобиля'== Персона THAT Владеет (SOMETIME Х) SOME Автомобиль; Х BEFORE NOW. Это предложение определяет понятие „Бывший владелец автомобиля' как персону, которая владела раньше (в течение некоторого интервала времени Х) автомобилем.

(Робот МожетПереносить Объект). IF (X МожетПереносить Y); X-Тип^а' THEN Y. Вес=< л200 kg'. Робот типа «а» может переносить только объекты веса не более 200 кг. EACH Робот(Тип= ла') Х МожетПереносить EACH

Объект(Тип=лб') OR МожетПереносить EACH Агент THAT Меньше Х AND МожетПереносить EACH Объект(Тип=лв'). Это предложение утверждает, что всякий робот типа «а» может переносить каждый объект типа «б» или переносить любого агента, который меньше этого робота и может переносить каждого объекта типа «в».

В третьей главе «Дедукция для интервальных онтологий» представлены методы и алгоритмы дедукции для онтологий, записанных в некоторых расширениях интервальной логики Аллена.

Пусть О - онтология в языке темпоральной спецификации ЯТС, содержащая события. Событие - это понятие (класс или бинарная связь), имеющая неявный атрибут Int, значениями которого служат темпоральные интервалы. Мы будем предполагать, что в предложениях онтологии О нет вхождений темпоральных кванторов SOMETIME и ALLTIME. Тогда, если игнорировать структуру понятий онтологии О, то мы получаем интервальную онтологию О1, объектами которой являются темпоральные интервалы, а ее предложения выражают отношения между интервалами. Фактически такие предложения соответствуют булевым комбинациям предложений интервальной логики Аллена.

Интервальную логику Аллена обозначим LA и через LA+ обозначим булево расширение логики LA. Предложениями логики LA+ являются булевы комбинации предложений логики LA. Другими словами, множество предложений LA+ является замыканием множества предложений LA с помощью связок ~ , Л , V и ( Формула ф ^ у является сокращением для формулы ~ ф V у.)

В логике Аллена LA используются (в качестве примитивов) семь бинарных отношений между темпоральными интервалами: b (before - раньше), m (meets - встречает), o (overlaps - перекрывает), d (during - в течение), s (starts - начинает), f (finishes - заканчивает), e (equal - равен). Семантика связок Аллена определяется неравенствами между концами интервалов: А b В О А+ < В- О В- - А+ > 1,

А т В О А+ = В- О В- - А+ > 0, А+ - В- > 0,

А о В О А- < В-, В- < А+, А+ < В+ О В- - А- > 1, А+ - В- >1, В+ - А+ > 1, А й В О В- < А", А+ < В+ О А~ - В- > 1, В+ - А+ > 1, А s В О А- = В-, А+ < В+ О А- - В- > 0, В- - А- > 0, В+ - А+ >1, А /В О В- < А", А+ = В+ О А" - В- > 1, А+ - В+ > 0, В+ - А+ > 0, А е В О А- = В", А+ = В+ О А" - В- > 0, В- - А" > 0, А+ - В+ > 0,

В+ - А+ > 0. (1)

(Заметим, что X < У О У - X >1, так как предполагается, что моменты времени - целые неотрицательные числа.)

Пусть О ={Ь, т, о, й, s,/, е, Ь*, т*, о*, й*, s*,/*}, где 0* - отношение, обратное к бинарному отношению 0: А 0* В О В 0 А.

Замечание. Дедукция для интервальных онтологий, записанных в языке интервальной логики Аллена ЬЛ, может выполняться с помощью извест-

-5

ного алгоритма Аллена, имеющего временную оценку сложности О(п /о^п). По данной онтологии О алгоритм Аллена находит, как правило, но не всегда, все логические следствия из О. Однако, этот алгоритм не полон.

Рассмотрим проблему дедукции для онтологий, записанных в языке булева расширения интервальной логики Аллена ЬЛ+. Пусть О - интервальная онтология, записанная в языке ЬЛ+. Чтобы выяснить, является ли онтология О невыполнимой, можно применить метод аналитических таблиц.

В табл. 1 приведены известные правила вывода для предложений (формул) с пропозициональными связками. Здесь стоящие перед формулой знаки «+» и «-» означают соответственно истинность и ложность этой формулы (в некоторой интерпретации). Поэтому, например, правило Т1(2, 2) из табл.1, указанное во второй строке и втором столбце, интерпретируется так: если на некотором шаге построения дерева вывода это правило применяется к формуле вида - (ф V у), приписанной к вершине V текущего дерева, то, найдя концы v1, v2,..., Vp проходящих через V ветвей, мы присоединяем подряд новые вершины, приписав к ним соответственно формулы - ф и - у. Аналогичную интерпретацию имеет правило Т1(2, 3) с тем отличием, что к

каждой из вершин V присоединяется вилка с вершинами, которым приписаны соответственно формулы - ф и + у.

Таблица 1 - Правила вывода для пропозициональных связок

+ (~ ф) ^ - ф - (~ ф) ^ + ф + (и л у) ^ + и, + у - (и л у) ^ - и 1 - у

+ (и V у) ^ + (и | +у) - (и V у) ^ -и -у + (ф ^ у) ^ - ф 1 + у - (и ^ у) ^ + Ф, - у

Возьмем, например, интервальную онтологию О = {р ^ А ЪЪ*В, q ^ В вй/Б С, ~ (р Л q ^ А й* С)}. Применяя к множеству означенных формул

Е = {+ (р ^ А ЪЪ* В), + ^ ^В вй/Б С), - (р Л q ^ А й* С)} правила из табл. 1 (с приоритетом правил для + (~ ф), - (~ ф), + (ф Л у), - (ф V у), - (ф ^ у)), получим завершенное дерево вывода с тремя ветвями (см. рис. 3.5 в главе 3, где ~ А х С следует заменить на А й* С). Первая ветвь про-позиционально замкнута, так как содержит контрарную пару (+ р, - р). Вторая ветвь также пропозиционально замкнута, так как содержит контрарную пару (+ q, - q). Третья ветвь содержит множество означенных формул {+ (А й* С), + (А ЪЪ* В), + (В вй/Б С)}. Если применить к этому множеству алгоритм Аллена (предварительно сняв с формул знаки «+»), то получим среди следствий из О противоречие А 0 С. Следовательно, третья ветвь также замкнута, и, значит, онтология О противоречива.

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

Полный алгоритм вывода можно получить, присоединив к правилам из табл. 1 новые правила, представленные в табл. 2. Правила вывода в табл. 2 получены из семантики связок Аллена. Рассмотрим, например, стоящее в четвертой строке и первом столбце правило Т2(4, 1). Если имеет место + (А / В), т.е. истинно предложение А /В, то справедливы неравенства А--В- > 1,

В+-А+ > 0, А+-В+ > 0 (см. (1)). Таким образом, правило вывода Т3(4, 1) состоятельно.

Таблица 2 - Правила вывода для связок Аллена

+А Ь В ^ В--А+ > 1 - А Ь В ^ А+-В- > 0

+А т В ^ В--А+ > 0, А+-В- > 0 - А т В ^ В--А+ > 1, А+-В- > 1

+А о В ^ В-А- > 1, А+-В- > 1, В+-А+ >1 - А о В ^ А--В- > 0 | В--А+ > 0 | А+-В+ > 0

+А/В ^ А--В- > 1, В+-А+ > 0, А+-В+ > 0 - А /В ^ В--А- > 0 | А+-В+ > 1 | В+-А+ >1

+А ^ В ^ В--А- > 0, А--В- > 0, В+-А+ >1 - А ^ В ^ А--В- > 1 | В-А- > 1 | А+-В+ > 0

+А й В ^ А--В- > 1, В+-А+ > 1 - А й В ^ В--А- > 0 А+-В+ > 0

+А е В ^ В-А- > 0, А--В > 0, В+-А+ > 0, А+-В+> 0 - А е В ^ А--В- > 1 | В-А- > 1 | А+-В+ > 1 | В+-А+ > 1

Для многих задач онтологического моделирования требуется специфицировать также метрическую информацию о темпоральных интервалах. Возьмем, например, предложение А о В. Если это предложение истинно, то для концов интервалов А и В имеет место А~ < ВТ < А+ < В+, и мы имеем следующие интервалы

[А", В"], [А", А+], [А", В+], [В", А+], [В", В+], [А+, В+], (2)

имеющие длину > 1. Включенная в отношение А о В метрическая информация заключается в конкретных оценках для длин этих интервалов, т.е. для разностей

В" - А", А+ - А", В+ - А", А+ - В", В+ - В", В+ - А+. (3)

Например, мы можем указать, что А+ -А - = 2 (т.е. длина интервала [А", А+] равна 2) и 2 < А+ - ВТ < 5 (т.е. длина перекрытия интервалов А и В не меньше 2 и не больше 5). В языке метрического расширения логики Аллена цЬЛ мы можем эту информацию представить предложением

А о(А+ - А" = 2; 2 < А+ - В- < 5) В. (4)

Метрическое ограничение А+ - А~ = 2; 2 < А+ - В- < 5 можно переписать в эквивалентной форме, когда все неравенства имеют вид X-У > г , как А+ - А" > 2; А" - А+ > -2; А+ - В- > 2; В- - А > - 5.

Поэтому предложение (4) эквивалентно предложению

А о(А+ - А" > 2; А" - А+ > -2; А+ - В- > 2; В- - А > - 5) В (5)

Мы скажем, что предложение (5) является нормальной формой предложения (4). В дальнейшем перед дедукцией для онтологии мы будем приводить ее предложения к нормальной форме.

Произвольное предложение языка цЬЛ получается соединением атомарных предложений так же, как это делается в языке ЬЛ. Например, предложение

А Ъ*/б(Б+ - А+ = 2; А+ - А" < 3)о(Б+ - А" > 3) В (6)

получено соединением атомарных предложений

А Ъ*В, А/В, А б(Б+ - А+ = 2; А+ - А" < 3) В и А о(Б+ - А" > 3) В. Предложение (6) интерпретируется так же, как и следующее выражение, составленное из неравенств и булевых связок:

(А+ - А" > 1) Л (В+ - Б" > 1) Л ((А" - Б+ > 1) V

(А" - В" > 1) Л (В+ - А+ > 0) Л (А+ - В+ > 0) V

(А" - В" > 0) Л (В" - А" > 0) Л (В+-А+ = 2) Л (А+ - А" < 3) V

(В" - А" > 1) Л (А+ - Б" > 3) Л (В+ - А+ > 1)).

Замечание. Предложение А в(А+ - А~ = г) А мы записываем короче как |А| = г . Аналогично, вместо А в(А+ - А~ > г) А пишем |А| > г и т.п.

В табл. 3 представлены правила вывода для предложений со связками Аллена с ограничениями. В табл. 4 показаны правила вывода для ограниче-

ний.

Таблица 3 - Правила вывода для связок Аллена с ограничениями

+ (А 0(Х) В) ^ + (А 0 В), + X - (А 0(Х) В) ^ - (А 0 В) | - X

+ (А 50 В) ^ + (А 5 В) | + (А 0 В) - (А 50 В) ^ - (А 5 В), - (А 0 В)

0 £ О или 0 = а(Х), а £ О, X - ограничение, 5 - последовательность (слово) таких 0

Таблица 4 - Правила вывода для ограничений

+ (X - У) > г ^ X - У > г - (X-У) > г ^ У - X > 1 - г

+ (X - У) > г ^ X - У > г + 1 - (X-У) > г ^ У - X > - г

+ (X - У) < г ^ У - X > - г - (X-У) < г ^ У - X > г + 1

+ (X - У) < г ^ У - X > 1 - г - (X-У) < г ^ У - X > г

+ (0 ; X) ^ + 0, + X - (0 ; X) ^ - 0 | - X

0 - атомарное ограничение, X - произвольное ограничение

Обозначим через цЬЛ+ булево метрическое расширение интервальной логики Алена ЬЛ. Рассмотрим пример дедукции в логике цЬЛ+.

Пример 2. Возьмем интервальную онтологию О = {р ^ А Ь(В - А+ > 2) В, д ^ В Ь(С- - В+ > 3) С} и формулу р Л д ^ А Ь(С - А+ > 3) С. Чтобы доказать логическое следствие О |= р Л д ^А Ь(С - В+ >3) С, мы строим дерево вывода, применяя правила вывода из табл. 2 - табл. 4 к начальной ветви {+ (р ^ А Ь(В- - А+ > 2) В), + (д ^ В Ь(С- - В+ > 3) С), - (р Л д А Ь(С-А+>3)С)} (см. рис. 3.9, глава 3). Из двух незамкнутых ветвей выпишем неозначенные неравенства, добавив стандартные неравенства для интервалов А, В и С: Б1= {В"-А+ > 2, С-В+ > 3, А+-С > 0, А+-А" > 1, В+-В" > 1, С^-С > 1}, Б2= {В"-А+ > 2, С-В+ > 3, А+-С > - 2, А+-А" > 1, В+-В" > 1, С^-С > 1}. Легко выяснить противоречивость (невыполнимость) систем неравенств и Б2. В самом деле, содержит неравенства В" - А+ > 2, В+ - В" > 1, С - В+ > 3, А+ - С > 0, складывая которые получаем (В" - А+) + (В+ - В") + (С - В+) + (А - С") > 2 + 1 + 3, т.е. 0 > 6 (противоречие). Аналогично доказывается невыполнимость системы Б2.

Для нахождения противоречивой циклической подсистемы неравенств, можно применить алгоритм для отыскания цикла положительной длины в графе с взвешенными дугами. Для произвольной системы Б неравенств вида X - У > г определяем граф Г(Б), вершинами которого служат переменные, и

две вершины У и Х соединяются дугой веса r тогда и только тогда, когда неравенство X- Y > r содержится в S.

В четвертой главе «Примеры применения разработанных методов и алгоритмов» приведены два примера онтологического моделирования приложений с использованием языков ЯТС и цЬЛ+. Первое приложение относится к задаче спецификации потоков работ (workflows). Второе приложение относится к задаче о движении поездов.

В пятой главе описана программа, реализующая разработанные методы и алгоритмы для выяснения невыполнимости онтологий и для нахождения ответы на запросы к онтологиям, записанным в языке цЬЛ+. Программа написана в среде Microsoft Visual Studio 2013 на языке C#.

ГЛАВА 1 ТЕМПОРАЛЬНЫЕ ФОРМАЛИЗМЫ

1.1 Общие сведения об онтологиях

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

Понимание предметной области достигается с помощью понятий, которые классифицируют ее объекты и связи (отношения) между ними. Концептуализация предметной области - это результат описания знания в терминах этих понятий. Но для того чтобы это знание можно было бы представить в компьютере, причем так, чтобы была возможность его программной семантической обработки, необходимо записать это знание в подходящем формализме. Результатом такого описания служит онтология предметной области. Следуя Т. Груберу [34], онтология - это явная формальная спецификация концептуализации, понимание которой разделяется некоторым сообществом агентов.

Онтология представляет знание о предметной области, выраженное в общих ее связях и закономерностях. Конкретное знание выражается при помощи фактов, структурированных в соответствии с этой онтологией. Таким образом, если О - онтология и ГБ — база фактов (структурированных по онтологии О), то база знаний есть КВ = О и ГБ.

В базе знаний КВ онтология О является стабильной компонентой, а база фактов ГБ, как правило, переменной. Можно ввести параметр у, значение которого фиксирует базу фактов и, следовательно, базу знаний: КВТ = О и ГБу. Этим параметром может быть время, контекст, положение в пространстве, ситуация и т.п. Параметр у называется точкой соотнесения [4].

Время является одним из фундаментальных понятий при описании реального мира и является предметом длительных научных исследований.

Многие важные понятия для систем искусственного интеллекта (ИИ) и его приложений такие, как «изменение», «причина», «следствие» и отношения между ними, описываются в терминах времени. В темпоральной онтологии точками соотнесения служат значения, включающие моменты времени или временные (темпоральные) интервалы. Темпоральные онтологии строятся для динамических предметных областей, состояния которых изменяются во времени. Понятие, имеющее временную референцию, называется событием. Событие имеет атрибуты, значениями которых служат временные точки или временные интервалы. Событие также может иметь атрибут, значением которого являются ситуации - термы, специфицирующие состояния предметных областей. При спецификации темпоральных онтологий используются формализмы, предложения которых определяют изменения состояний предметных областей.

Время представляется в базах знаний либо в неявном виде с помощью изменений состояний моделируемой системы во времени, либо в явном - на основе той или иной иерархии временных единиц [2]. В классе подходов, использующих моделирование изменений, базовыми являются сущности, преобразующие одно состояние системы в другое. Эти состояния рассматриваются как мгновенные снимки мира, не обладающие длительностью. Явное моделирование времени дает возможность строить высказывания, истинностные значения которых приурочены к определенному моменту или интервалу времени и могут изменяться с течением времени. При явном представлении времени предложения формализма интерпретируются относительно временных единиц.

1.2 Неявное моделирование времени

Типичными представителями формализмов, в которых время представляется через изменения, являются ситуационное исчисление (situation calculus) [52], исчисление событий (event calculus) [46], планирующие системы типа STRIPS [31] и сети Петри [57].

1.2.1 Ситуационное исчисление

Ситуационное исчисление было предложено Дж. Мак-Карти и П. Хейе-сом [52]. Оно использовалось для представления и рассуждения о времени, действиях и изменениях. В дальнейшем это исчисление послужило базой для таких областей как:

• планирование действий (напр., [32, 38, 48]);

• нахождение объяснений (напр., [68]);

• обновления в базах данных (напр., [20, 64]);

• транзакции в базах данных (напр., [45]);

• агентное программирование и роботика (напр., [21, 25, 42, 47]).

Фактически, ситуационное исчисление является наиболее изученным

формализмом для представления изменений состояний.

Предложения ситуационного исчисления записываются в многосортной логике предикатов. Имеются три основных сорта: ситуация, действие и объект. Элемент сорта «ситуация» интерпретируется как мгновенный снимок состояния приложения. Элементы сорта «объект» используются для обозначения любых сущностей, кроме ситуаций и действий.

Список литературы диссертационного исследования кандидат наук Нгуен Тхи Минь Ву, 2017 год

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Бестужева, И.И. Временные сети Петри. Классификация и сравнительный анализ [Текст] / И.И. Бестужева, В.В. Руднев // Автоматика и телемеханика. - 1990. - № 10. - С.3-31.

2. Еремеев, А.П. Модели представления временных зависимостей в интеллектуальных системах поддержки принятия решений [Текст] / А.П. Еремеев, В.В. Троицкий // Известия РАН. Теория и системы управления. - 2003.

- № 5. - С. 75-88.

3. Кормен, Т. Алгоритмы: построение и анализ. Глава 22 - Элементарные алгоритмы для работы с графами [Текст] // Т. Кормен, Ч. Лейзерсон, Р. Ривест. - М.: «Вильямс», 2005. - 2-е изд. - С. 622-632.

4. Плесневич, Г.С. Бинарные модели знаний [Текст] // Материалы III межд. науч.-практич. семинар «Интегрированные модели и мягкие вычисления в искусственном интеллекте»: сб. науч. тр., Коломна, 15-17 мая 2005 г. -М.: Физматлит, 2005. - Т. 1. - С. 106-117.

5. Плесневич, Г.С. Формальные онтологии [Текст] // Материалы межд. науч.-техн. конф. 0STIS-2012 «Открытые семантические технологии проектирования интеллектуальных систем».- Минск: Изд-во БГУИР, 2012. - С. 163-169.

6. Плесневич, Г.С. Один язык для спецификации онтологий // Открытые семантические технологии проектирования интеллектуальных систем (OSTIS-2014): материалы IV межд. науч.-техн. конф. (Минск, 20-22 февраля 2014 года). - Минск: БГУИР, 2014. - С. 143-146.

7. Рассел, Дж. Консорциум Всемирной паутины. - М.: Изд-во VSD, 2012.

- 98 c.

8. Смирнов, В.А. Логические системы с модальными временными операторами // Материалы II Советско-финского коллоквиума по логике «Модальные и временные логики». - М.: Институт философии АН СССР, 1979. - С. 89-98.

9. Фейс, Р. Модальная логика. - М. Наука. - 1974. - 520 с.

10. Фон Вригт, Г.Н. Логико-философские исследования. Избранные труды [Текст] / Г.Н. Фон Вригт - М.: Прогресс, 1986. - 600 с.

11. Abiteboul, S. Foundation of databases [Text] / S. Abiteboul, R. Hull, V, Vi-anu. - Addisom-Wesley, 1995.

12. Allen, J.F. Maintaining Knowledge about Temporal Intervals [Text] / J.F. Allen // Communications of the ACM. - 1983. - Vol. 26, № 11. - P. 832-843.

13. Allen, J.F. Planning as temporal reasoning [Text] / J.F. Allen // Proc. of the 2nd Intern. Conf. on Principles of Knowledge Representation and Reasoning. -1991. - P. 3-14.

14. Allen, J.F. Actions and events in interval temporal logic [Tech. Rep.]: TR521 / J.F. Allen, G. Ferguson; Rochester University. - 1994.

15. Alonso, G.F. Web services: concepts, architectures and applications [Text] / G.F. Alonso, F. Casati, H. Kuno, V. Machiraju. - Springer-Verlag, 2004. - 340 p.

16. Artale A., Franconi E. A temporal description logic for reasoning about actions and plans // Journal of Artificial Intelligence Research. - 1998. - Vol. 9. - P. 463-506.

17. Artale, A. A survey of temporal extensions of description logics [Text] / A. Artale, E, Franconi // Annals of Mathematics in Artificial Intelligence. - 2000. -№ 1. - Р. 171-210.

18. Artale, A. Temporal description logics [Text] / A. Artale, E, Franconi // Handbook of Time and Temporal Reasoning in Artificial Intelligence / M. Fisher, D. Gabbay, L. Vila (eds.). - MIT Press, 2005. - P. 375-388.

19. Baader, F. The description logic handbook: theory, implementation, and applications [Text] / F. Baader, D.L. McGuinness, D. Nardi, P. Patel-Schneider (eds.). - Cambridge University Press, 2010 - 624 p.

20. Bertossi, L. SCDBR: An automated reasoner for specifications of database updates [Text] / L. Bertossi, M. Arenas, C. Ferretti // Journal of Intelligent Information Systems. - 1998. - Vol. 10, № 3. - P. 235-280.

21. Boutilier, C. Decision-theoretic, high-level agent programming in the situation calculus [Text] / C. Boutilier et al // Proc. of the 17th IAAI 2000, Austin, TX, USA. - 2000. - P. 355-362.

22. Bresolin, D. Propositional interval neighborhood logics: Expressiveness, decidability, and undecidable extensions [Text] / D. Bresolin, V. Goranko, A. Mon-tanari, G. Sciavicco // Annals of Pure and Applied Logic. - 2009. - Vol. 161, № 3.

- P. 289-304.

23. Bresolin, D. Optimal tableau systems for propositional neighborhood logic over all, dense, and discrete linear orders [Text] / D. Bresolin, A. Montanari, P. Sala, and G. Sciavicco // TABLEAUX 2011. LNCS. - Springer, 2011. - Vol. 6793. -P. 73-87.

24. Brunner, K. Automated reasoning with analytic tableaux and related methods [Text] / K. Brunner , G. Metcalf (eds.) // Proc. of 20th Intern. Conf. TABLEAUX 2011. - Bern, Switzerland. 2011. - LNAI 6793. - 279 p.

25. Burgard, W. The interactive museum tour-guide robot [Text] / W. Burgard et al. // Proc. of the 15th National Conf. on Artificial Intelligence AAAI-98. - 1998.

- P. 207-215.

26. Dechter, R. Temporal constraint networks [Text] / R. Dechter, I. Meiri, J. Pearl // Artificial Intelligence. - 1991. - Vol. 49. - P. 61-95.

27. Dumas, M. Process-aware information systems: Bridging People and Software Through Process Technology [Text] / M. Dumas, Will M.P. Van der Aalst, Ter Hofstede A.H.M. (eds.). - Wiley-Interscience, 2007. - 1 edition. - 432 p.

28. Emerson, E.A. Using branching time logic to synthesize synchronization skeletons [Text] / E.A. Emerson, E.M. Clarke // Sci. Comput. Programming. -1982. - Vol. 2. - P. 241-266.

29. Emerson, E. Decision procedures and expressiveness in the temporal logic of branching time [Text] / E. Emerson, J. Halpern // Journal of Computer and System Sciences. - 1985. Vol. 30, № 1. - P. 1-24.

30. Fernandes, A. A logic-based integration of active and deductive databases [Text] / A. Fernandes, M. Williams, N. Paton // New Generation Computing. -1997. - Vol. 15, № 2. - P. 205-244.

31. Fikes, R. STRIPS: a new approach to the application of theorem proving to problem solving [Text] / R. Fikes, N. Nilsson // Artificial Intelligence. - 1971. - № 2. - P. 189-208.

32. Fikes, R. Learning and executing generalized robot plans [Text] / R. Fikes, P.E. Hart, N.J. Nilsson // Artificial Intelligence. - 1972. - № 3. - P. 251-288.

33. Gabbay, D.M. Many-dimensional modal logics: theory and applications [Text] / D.M. Gabbay, A. Kurucz, F. Wolter, M. Zakharyaschev. - The Netherlands, 2003. - 745 p.

34. Gruber, T. A translation approach to portable ontology specifications [Text] / T. Gruber // Knowledge Acquisition. - 1993. - Vol. 5, № 2 - P. 199-220.

35. Gurari, E. Backtracking algorithms CIS 680: DATA STRUCTURES. Chapter 19: Backtracking Algorithms [Text] / E. Gurari. - 1999.

36. Gurevich, Yu. Reconsidering Turing's thesis: towards more realistic semantics of programs [Techn. Report] / Yu Gurevich // CRL-TR-36-84, EECS Department, University of Michigan, 1984.

37. Gurevich, Yu. A New Thesis [Text] / Yu Gurevich // American Mathematical Society Abstracts. - August 1985. - P.317-318.

38. Haddawy, P. A logic of time, chance, and action for representing plans [Text] / P. Haddawy // Artificial Intelligence. - 1996. - Vol. 80, № 1. - P. 243308.

39. Hailpern, B.T. Verifying concurrent processes using temporal logic [Lec. Notes]: Comp. Sci. 129. - Springer Verlag, Berlin. 1982.

40. Halpern, J. A propositional modal logic of time intervals [Text] / J. Halpern, Y. Shoham // Journal of the ACM. - 1991. - Vol. 38, № 4. - P. 935-962.

41. Huhns, M. Service-oriented computing: Key concepts and principles [Text] / M. Huhns, M. Singh // IEEE Internet Computing. 2005. - Vol. 9, № 1. - P. 75-81.

42. Jenkin, M. A logical approach to portable high-level robot programming [Text] / M. Jenkin // Proc. of the 10th Australian Joint Conf. on Artificial Intelligence, Perth, Australia. - 1997. - P. 12-26.

43. Kamp, J.A. Tense logic and the theory of linear order [Text]: Ph. D. thesis / J.A. Kamp; University of California, Los Angeles. - 1968.

44. Kautz, H. Integrating metric and qualitative temporal reasoning [Text] / H. Kuatz, P. Ladkin // Proc. of AAAI-91. - 1991. - P. 241-246.

45. Kiringa, I. Towards a general theory of advanced transaction models in the situation calculus [Text] / I. Kiringa // Proc. of the 8th Intern. Workshop on Knowledge Representation meets Databases KRDB'2001, Rome, Italy. - 2001.

46. Kowalski, R. A logic-based calculus of events [Text] / R. Kowalski, M. Ser-got" // New Generation Computing. - 1986. - Vol. 4, № 1. - P. 67-95.

47. Levesque, H. A situation calculus approach to modeling and programming agents [Text] / H. Levesque, Y. Lesperance, R. Reiter // Foundations of Rational Agency / A. Rao and M. Wooldridge (eds.). - Springer Netherlands, 1999. - P. 275-299.

48. Lifschitz, V. Towards a metatheory of action [Text] / V. Lifschitz // Proc. of the 2nd Intern. Conf. on Principles Knowledge Representation and Reasoning (KR-91), Los Altos, California / J.Allen, R.Fikes, E.Sandewall (eds.). - Morgan Kaufmann Publishers, 1991. - P. 376-386.

49. Mackworth, A.K. Consistency in network of relations [Text] / A.K. Mackworth // Artificial Intelligence. - 1977. - Vol. 8, № 1. - P. 99-118.

50. Mahbub, K. Run-time monitoring of requirements for systems composed of web-services: Initial implementation and evaluation experience [Text] / K.

r c\

Mahbub, G. Spanoudakis // Proc. of the 3 IEEE Intern. Conf. on Web Services ICWS. - 2005. - P. 257-265.

51. Mathias, W. Workflow management systems: formal foundation, conceptual design, implementation aspects [dissertation] / W. Mathias. - Munster, December 1999.

52. McCarthy, J. Some philosophical problems from the standpoint of artificial intelligence [Text] / J. McCarthy, P. Hayes // Machine Intelligence / B. Meltzer and D. Michie (eds.) . - Edinburgh University Press, 1969. - Vol. 4. - P. 463-502.

53. Meiri, I. Temporal reasoning: A constraint-based approach [Text]: Ph. D. diss. / I. Meiri: University of California. - 1992.

54. Meiri, I. Combining qualitative and quantitative constraints in temporal reasoning [Text] / I. Meiri // Artificial Intelligence. - 1996. - Vol. 87, № 1-2. - P. 343-385.

55. Montanari, A. Decidability of interval temporal logics over split-frames via granularity [Text] / A. Montanari, G. Sciavicco, N. Vitacolonna // Proc. of the 8th European Conf. on Logics in Artificial Intelligence (JELIA). LNCS. - Springer, 2002. - Vol. 2424. - P. 259-270.

56. Montanari, A. Maximal decidable fragments of Halpern and Shoham's modal logic of intervals [Text] / A. Montanari, G. Puppis, P. Sala // Proc. of the 37th Intern. Colloquium on Automata, Languages, and Programming - Part II (ICALP-2). LNCS. - 2010. - Vol. 6199. - P. 345-356.

57. Petri, C. Kommunikation mit Automaten [Text]: Ph. D. Thesis / C. Petri; Institut fur instrumentelle Mathematik, Bon, Germany. - 1962.

58. Plesniewicz, G.S. Ontology Specification in the System «Binary Model of Knowledge» [Text] / G.S. Plesniewicz // Proc. of 11th Intern. Conf. on Application of Fuzzy Systems and Soft Computing (ICAFS-2014, Paris, France, September 24, 2014). - Kaufering: b- Quadrat-Verlag, 2014. - P. 69-78.

59. Plesniewicz, G.S. Ontologies and fact bases specification by means of the system "Binary Model Of Knowledge" [Text] / G.S. Plesniewicz, B.S. Karabekov, T.M.V. Nguyen // Proc. of the VIIIth World Conf. on Intelligent Systems for Industrial Automation (Tashkent, Uzbekistan, November 25-27, 2014). - Kaufering: b-Quadrat-Verlag, 2014. - P. 474-478.

60. Pnuelli, A. The temporal logic of programs [Text] / A. Pnuelli // Proc. of the 18th Annual Symposium on Foundations of Computer Science (FOCS). - 1977. -P. 46-57.

61. Prior, A.N. Time and Modality [Text] / A.N. Prior. - Oxford: Oxford University Press, 1957. - 160 p.

62. Prior, A.N. Past, present and future [Text] / A.N. Prior. - Oxford: Clarendon Press, 1967. - 228 p.

63. Reiter, R. On closed world data bases [Text] / R. Reiter // Logic and databases [Text] / Callaire H, Minker J. (eds.). - Plenum Press, New York, 1978. - P. 55-76.

64. Reiter, R. On specifying database updates [Text] / R. Reiter // Journal of Logic Programming. - 1995. - Vol. 25, № 1. - P. 53-91.

65. Rouached, M. A semantical framework to engineering WSBPEL processes [Text] / M. Rouached, W. Fdhila, C. Godart // Information Systems and EBusiness Management. - 2008. - Vol. 7, № 2. - P. 223-250.

66. Schmiedel, A. A temporal terminological logic [Text] / A. Schmiedel // Proc. of AAAI-90, Doston, MA. - 1990. - P. 640-645.

67. Schmidt-Schauss, M. Attributive concept description with complements [Text] / M. Schmidt-Schauss , G. Smolka //Artificial Intelligence, 1991. - Vol. 48, № 1. - P. 1-26.

68. Shanahan, M. Explanation in the situation calculus [Text] / M. Shanahan // Proc. of Intern. Joint Conf. on Artificial Intelligence IJCAI-93. - 1993. - P. 16065.

69. Shanahan, M. Robotics and the common sense informatic situation [Text] / M. Shanahan // Proc. of the 12th European Conf. on Artificial Intelligence ECAI 1996 / Wahlster, W. (ed.). - 1996. - P. 684-688.

70. Shanahan, M. An abductive event calculus planner [Text] / M. Shanahan // Journal of Logic Programming. - 2009. - Vol. 44. - P. 207-239.

71. Shoham, Y. Representing time and action in AI. Revised version of: Problems in formal temporal reasoning [Text] / Y. Shoham, N. Goyal // Artificial Intelligence. - 1988. - Vol. 36, № 1. - P. 49-61.

72. Shostak, R. Deciding linear inequalities by computing loop residues [Text] / R. Shostak // Journal of the ACM. - 1981. - Vol. 28, № 4. - P. 769-779.

73. Thomason, R.H. Combinations of tense and modality [Text] / R.H. Thom-ason // Handbook of Philosophical Logic / D.M. Gabbay, F. Guenthner (eds). -Kluwer, Dordrecht, 1984. - Vol. 2. - P. 135-165.

74. Torsun, I.S. Foundations of intelligent knowledge-based systems [Text] / I.S. Torsun. - Academic press, London, 1998. - 507 p.

75. Van Der Aalst. Workflow management: models, methods and systems (Information systems) [Text] / Wil M.P. van der Aalst, Kees Van Hee. - MIT Press, Cambridge, USA, 2004. - 384 p.

76. Vilain, M. Constraint propagation algorithms for temporal reasoning [Text] / M. Vilain, H. Kautz // Proc. of the 5th National Conf. of Artificial Intelligence AAAI-86. - 1986. - P. 377-382.

77. Weiss, G: Multiagent systems: a modern approach to distributed artificial intelligence / G. Weiss (ed.). - MIT Press, New Ed edition, 2000. - 648 p.

78. Winter, K. Model checking for ASM [Text] / K. Winter // J. Universal Computer Science. - 1997. Vol. 3, № 5. - P. 689-701.

79. Zaidi, A.K. Combining qualitative and quantitative temporal reasoning for criminal forensics [Text] / A.K. Zaidi, M. Ishaque, A. Levis // Mathematical Methods in Counterterrorism, part 1. - Springer-Verlag, 2009. - P. 69-90.

ПРИЛОЖЕНИЕ 1 Таблица композиции темпоральных отношений для

интервальной алгебры Аллена

Т1А В ь* т * т о * о й й* * / / Е

ь В и Ь Ь о т й s Ь Ь о т й £ Ь о т й £ Ь Ь Ь Ь о т й £ Ь В

ь* и Ь* * Ь* й о* Ь* * Ь* й 1т1 о* Ь* * Ь* й о* Ь* * Ь* й о* Ь* Ь* Ь* Ь*

т В * * Ь* о* * т ** й s Ь * II е Ь о й £ о й £ Ь т т о й £ Ь т

* т Ь о т й I* Ь* * £ £ е Ь* Ч о* Ь* Ч о* Ь* ч о* Ь* * т * т * т

о В * * Ь* о* * т ** й s Ь ** о* й* * £ Ь о т Ь о й £ Ь от т й I* о о й* I* о й £ Ь о т о

* о Ь о т й I* Ь* о й* I* Ь* О й £ 1 е О* * * й S I* ** о* Ь* * т* Ч о* ** Ь* о* * т ** й £ о* й I ** о* Ь* * т* * о ** й* о* * £ * о

й В Ь* Ь Ь* Ь о т й £ * Ь* й ю; т* й и й * Ь* й н т* й Ь о т й £ й

а* Ь о т й I* ** Ь* о* * т ** й s о й* I* ** о* й* * £ о й* I* ** о* й* * £ 0 й £ 1 е о * * й £ I* й* о й* I* й* ** о* й* * £ й* й*

В Ь* Ь * т Ь о т ч о* й Ь от т й I* £ * s s е й Ь о т £

* Ь от т й I* Ь* о й* I* * т о й* I* * о о* й I й* * £ £ е * £ * о й* * £

/ В Ь* т Ь* о й £ ** Ь* о* * т* й * * Ь* о* * т ** й s й ** Ь* о* * т* I II* е I

/ В * * Ь* о* * т ** й s т ** S О й* о ** £ о й* о й £ й* о й* * II е I I

е В Ь* т * т о * о й й* £ * £ I I е

ПРИЛОЖЕНИЕ 2 Графы, ассоциированные с системами простых неравенств для онтологии О в примере 4.1

Дерево имеет 26 ветвей, пронумерованных с 1 до 26 по порядку слева

направо, среди них 14 незамкнутых, графы которых ниже показаны.

ОД)

-1

0(89)

-1

0(8П), 0(812)

-1

0(815)

1

G(S17),

G(S18)

ПРИЛОЖЕНИЕ 3 Акты о внедрении

1. Акт о внедрении в учебно-научном процессе в ФГБОУ ВО «НИУ «МЭИ» при изучении дисциплины «Прикладная семиотика».

об использовании в учебно-научном процессе НИУ «МЭИ» результатов диссертационной работы НГУЕН ТХИ МИНЬ ВУ «Разработка методов темпоральной спецификации и дедукции для онтологии», представленной на соискание ученой степени канд. техн. наук по специальности 05.13.17 - Теоретические основы информатики

Настоящим актом подтверждается использование результатов диссертационной работы Нгуен Т.М.В. в учебно-научном процессе кафедры прикладной математики по направлениям «Прикладная математика и информатика» (по программе «Математическое и программное обеспечение вычислительных машин и компьютерных сетей») при проведении учебных занятий по дисциплине «Прикладная семиотика», а также в НИР, выполняемых на кафедре прикладной математики по разработке методов, алгоритмов и инструментальных средств моделирования рассуждений в интеллектуальных системах поддержки принятия решений, в том числе: 1) вопросы разработки языка темпоральной спецификации онтологий; 2) программа дедукции для онтологий в языке расширенной логики Аллена.

Заведующий каф. ПМ

Зам. зав. каф. по учебной работе к.т.н., доц.

д.т.н., проф.

Еремеев А.11.

Маран М.М.

Зам. зав. каф. по научной работе к.т.н., доц.

Варшавский И.Р.

2. Акт о внедрении в систему управления доставкой готовой продукции ООО «Империя соусов».