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

Интервальная алгебра Аллена — это исчисление для Шаблон:Не переведено, которое было введено Шаблон:Не переведено в 1983 году.

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

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

Отношения

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

Отношение	Иллюстрация	Интерпретация
$X<Y$ $Y>X$		X предшествует Y Y предшествует X
$X𝐦Y$ $Y𝐦𝐢X$		X встречает Y Y встречен X (i означает inverse (инверсию))
$X𝐨Y$ $Y𝐨𝐢X$		X перекрывается с Y Y перекрывается X
$X𝐬Y$ $Y𝐬𝐢X$		X начинается с Y Y начинается с X
$X𝐝Y$ $Y𝐝𝐢X$		X во время Y Y содержит X
$X𝐟Y$ $Y𝐟𝐢X$		X заканчивает Y Y закончен X
$X\mathbf{=}Y$		X равен Y

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

Предложения:

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

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

$\text{газета }\mathbf{\{}\mathrm{d}\mathbf{\}}\text{ ужин}$

$\text{ужин }\mathbf{\{}<\mathbf{\}}\text{ кровать}$

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

Композиция отношений между интервалами

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

Например, можно сделать следующей вывод: $\text{газета }\mathbf{\{}<\mathbf{\}}\text{ кровать}$.

Расширения

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

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

Реализации

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

Семантические механизмы рассуждений для интервальной алгебры Аллена (и других): GQR и SparQ.

См. также

• Темпоральная логика
• Шаблон:Не переведено
• Шаблон:Не переведено
• Повседневное мышление

Источники

• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal