Интервальная алгебра Аллена

Интервальная алгебра Аллена — это исчисление временных рассуждений , которое было введено Джеймсом Ф. Алленом в 1983 году.

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

Формальное описание

Отношения

Следующие 13 базовых отношений отражают возможные отношения между двумя интервалами.

Связь	Иллюстрация	Интерпретация
$X\,{\mathrel {\mathbf {<} }}\,Y$ $Y\,{\mathrel {\mathbf {>} }}\,X$		X предшествует Y Y предшествует X
$X\,{\mathrel {\mathbf {m} }}\,Y$ $Y\,{\mathrel {\mathbf {mi} }}\,X$		X встречается с Y Y встречается с X ( i означает i inverse )
$X\,{\mathrel {\mathbf {o} }}\,Y$ $Y\,{\mathrel {\mathbf {oi} }}\,X$		X пересекается с Y Y перекрывается X
$X\,{\mathrel {\mathbf {s} }}\,Y$ $Y\,{\mathrel {\mathbf {si} }}\,X$		Х начинается Y Y начинается с X
$X\,{\mathrel {\mathbf {d} }}\,Y$ $Y\,{\mathrel {\mathbf {di} }}\,X$		X во время Y Y содержит X
$X\,{\mathrel {\mathbf {f} }}\,Y$ $Y\,{\mathrel {\mathbf {fi} }}\,X$		X завершает Y Y закончен X
$X\,{\mathrel {\mathbf {=} }}\,Y$		Х равен Y

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

Предложения

Во время ужина Питер читает газету. После этого он ложится спать.

формализуются в алгебре интервалов Аллена следующим образом:

${\mbox{newspaper }}\mathbf {\{\operatorname {d} \}} {\mbox{ dinner}}$

${\mbox{dinner }}\mathbf {\{\operatorname {<} \}} {\mbox{ bed}}$

В общем случае количество различных отношений между n интервалами, начиная с n = 0, равно 1, 1, 13, 409, 23917, 2244361... OEIS A055203 . Особый случай, показанный выше, относится к n = 2.

Состав отношений между интервалами

Для рассуждений об отношениях между временными интервалами алгебра интервалов Аллена предоставляет таблицу композиции . Учитывая соотношение между $X$ и $Y$ и отношения между $Y$ и $Z$ , таблица состава позволяет сделать вывод о связи между $X$ и $Z$ . Вместе с обратной операцией это превращает алгебру интервалов Аллена в алгебру отношений .

Например, можно сделать вывод ${\mbox{newspaper }}\mathbf {\{\operatorname {<} ,\operatorname {m} \}} {\mbox{ bed}}$ .

Расширения

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

При изучении перекрывающейся разметки используется аналогичная алгебра (см. ^{[ 1 ]}). Его модели имеют больше вариаций в зависимости от того, разрешено ли конечным точкам структур документа быть действительно совмещенными или просто [касательными].

Реализации

Простая Java-библиотека, реализующая концепцию временных отношений Аллена и алгоритм согласованности путей.
Библиотека Java, реализующая алгебру интервалов Аллена (включая структуры данных и индексов, например, дерево интервалов )
OWL-Time Time Ontology в OWL — онтология темпоральных концепций OWL-2 DL для описания временных свойств ресурсов в мире или описанных на веб-страницах.
GQR является обоснованием интервальной алгебры Аллена (и многих других).
qualreas — это среда Python для качественных рассуждений над сетями алгебр отношений, таких как RCC-8, интервальная алгебра Аллена и алгебра Аллена, интегрированная с точками времени и расположенная во времени с левым или правым ветвлением.
SparQ является обоснованием интервальной алгебры Аллена (и многих других).
EveXL — это небольшой предметно-ориентированный язык для обнаружения событий, который реализует операторы интервальной алгебры с помощью художественных шаблонов ASCII.

См. также

Ссылки

^ Стивен ДеРоуз. Перекрытие разметки: обзор и лошадь. В Proceedings of Extreme Markup Languages 2004, Монреаль, Квебек, 2–6 августа 2004 г. http://xml.coverpages.org/DeRoseEML2004.pdf

Источники

Аллен, Джеймс Ф. (26 ноября 1983 г.). «Сохранение знаний о временных интервалах» (PDF) . Коммуникации АКМ . 26 (11): 832–843. CiteSeerX 10.1.1.472.5244 . дои : 10.1145/182.358434 . hdl : 1802/10574 . ISSN 0001-0782 . S2CID 16729000 .
Небель, Бернхард ; Бюркерт, Ханс-Юрген (1995). «Рассуждения о временных отношениях: максимально управляемый подкласс алгебры интервалов Аллена» (PDF) . Журнал АКМ . 42 : 43–66. дои : 10.1145/200836.200848 . S2CID 6586759 .
ван Бик, Питер; Манчак, Деннис В. (1996). «Разработка и экспериментальный анализ алгоритмов временного рассуждения» (PDF) . Журнал исследований искусственного интеллекта . 4 (1996): 1–18. arXiv : cs/9601101 . Бибкод : 1996cs........1101V . дои : 10.1613/jair.232 . S2CID 3204600 . Архивировано из оригинала (PDF) 6 июля 2017 года . Проверено 6 мая 2017 г.

[1] Стивен ДеРоуз. Перекрытие разметки: обзор и лошадь. В Proceedings of Extreme Markup Languages 2004, Монреаль, Квебек, 2–6 августа 2004 г. http://xml.coverpages.org/DeRoseEML2004.pdf

[ 1 ]