Интервальная алгебра Аллена (Numyjfgl,ugx gliyQjg Gllyug)

Интервальная алгебра Аллена — это исчисление для пространственно-временных рассуждений^[англ.], которое было введено Джеймсом Ф. Алленом^[англ.] в 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 означает 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$		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$		X равен Y

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

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

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

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

${\mbox{газета }}\mathbf {\{\operatorname {d} \}} {\mbox{ ужин}}$

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

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

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

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

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

Расширения

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

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

Реализации

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

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

Примечания

↑ Steven DeRose. Markup Overlap: A Review and a Horse. In Proceedings of Extreme Markup Languages 2004, Montréal, Québec, August 2-6, 2004. http://xml.coverpages.org/DeRoseEML2004.pdf

См. также

Источники

Allen, James F. (26 November 1983). "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) 6 июля 2017. Дата обращения: 6 мая 2017.

[1] Steven DeRose. Markup Overlap: A Review and a Horse. In Proceedings of Extreme Markup Languages 2004, Montréal, Québec, August 2-6, 2004. http://xml.coverpages.org/DeRoseEML2004.pdf

[1]