Алгебра интервалов Алленса - Википедия - Allens interval algebra

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

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

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

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

связи

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

СвязьИллюстрацияИнтерпретация

X предшествует YX предшествует Y

Y предшествует X

X встречает YX встречает Y

Y встречает X (я означает яnverse)

X перекрывается с YX перекрывается с Y

Y перекрывается X

X начинается с YX начинает Y

Y начинается с X

X во время YX во время Y

Y содержит X

X заканчивается на YX заканчивает Y

Y заканчивается X

X равно YX равно Y

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

Приговор

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

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

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

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

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

Например, можно сделать вывод .

Расширения

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

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

Реализации

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

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

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

Источники