Алгебра интервалов Аллена - Allens interval algebra

Для типа булевой алгебры, называемой интервальной алгеброй, см. Булева алгебра (структура)

Алгебра интервалов Аллена это исчисление за временное рассуждение это было введено Джеймс Ф. Аллен в 1983 г.

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

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

связи

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

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

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

Приговор

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

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

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

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

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

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

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

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

Расширения

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

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

Реализации

• Простая библиотека Java, реализующая концепцию временных отношений Аллена и алгоритм согласованности путей.
• Библиотека Java, реализующая алгебру интервалов Аллена (включая структуры данных и индексов, например, interval_tree )
• OWL-Time Онтология времени в OWL онтология темпоральных понятий OWL-2 DL для описания временных свойств ресурсов в мире или описанных на веб-страницах.
• GQR является аргументом в пользу алгебры интервалов Аллена (и многих других)
• Qualreas представляет собой платформу Python для качественных рассуждений над сетями алгебр отношений, такими как RCC-8, алгебра интервалов Аллена и алгебра Аллена, интегрированная с точками времени и расположенная во времени с левой или правой ветвью.

Смотрите также

• Временная логика
• Логика
• Расчет соединения регионов.
• Пространственное отношение (аналог)
• Здравый смысл

Рекомендации

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

Источники

• Аллен, Джеймс Ф. (26 ноября 1983 г.). «Сохранение знаний о временных интервалах» (PDF). Коммуникации ACM. 26 (11): 832–843. CiteSeerX  10.1.1.472.5244. Дои:10.1145/182.358434. ISSN  0001-0782.
• Небель, Бернхард; Bürckert, Ханс-Юрген (1995). «Рассуждения о временных отношениях: максимальный послушный подкласс интервальной алгебры Аллена». Журнал ACM. 42: 43–66. Дои:10.1145/200836.200848.^{[постоянная мертвая ссылка ]}
• ван Бик, Питер; Манчак, Деннис В. (1996). «Разработка и экспериментальный анализ алгоритмов временных рассуждений» (PDF). Журнал исследований искусственного интеллекта. 4 (1996): 1–18. arXiv:cs / 9601101. Bibcode:1996cs ........ 1101V. Дои:10.1613 / jair.232.