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

Интервальная алгебра Аллена — это исчисление для пространственно-временных рассуждений^[англ.], которое было введено Джеймсом Ф. Алленом^[англ.] в 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 (i означает inverse (инверсию))
${\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{газета }}\mathbf {\{\operatorname {d} \}} {\mbox{ ужин}}}$

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

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

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

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

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

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

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

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

• Темпоральная логика
• Расчёт связей между регионами^[англ.]
• Пространственные соотношения^[англ.]
• Повседневное мышление

• Allen, James F. (1983-11-26). Maintaining knowledge about temporal intervals (PDF). Communications of the 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ürckert, Hans-Jürgen (1995). Reasoning about Temporal Relations: A Maximal Tractable Subclass of Allen's Interval Algebra (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) 2017-07-06. Дата обращения: 2017-05-06. {{cite journal}}: |archive-date= / |archive-url= несоответствие временной метки; предлагается 6 июля 2017 (справка)