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

Исчисление для временного обоснования (относящегося к моментам времени) событий

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

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

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

Отношения

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

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

Предложения

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

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

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

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

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

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

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

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

Расширения

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

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

Реализации

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

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

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

Ссылки

1. Стивен ДеРоуз. Markup Overlap: A Review and a Horse. В 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 . doi :10.1145/182.358434. hdl :1802/10574. ISSN  0001-0782. S2CID  16729000.
• Nebel, Bernhard ; Bürcckert, Hans-Jürgen (1995). "Рассуждения о временных отношениях: максимальный подкласс интервальной алгебры Аллена" (PDF) . Journal of the ACM . 42 : 43–66. doi : 10.1145/200836.200848 . S2CID  6586759.
• van Beek, Peter; Manchak, Dennis W. (1996). "The design and experimental analysis of algorithms for temporal reasoning" (PDF) . Journal of Artificial Intelligence Research . 4 (1996): 1–18. arXiv : cs/9601101 . Bibcode :1996cs........1101V. doi :10.1613/jair.232. S2CID  3204600. Архивировано из оригинала (PDF) 6 июля 2017 г. . Получено 6 мая 2017 г. .