Для типа булевой алгебры, называемой интервальной алгеброй, см. Булева алгебра (структура)
Интервал алгебра Аллена является исчислением для временного рассуждения , которое было введено Джеймсом Ф. Алленом в 1983 году.
Исчисление определяет возможные отношения между временными интервалами и предоставляет композиционную таблицу, которую можно использовать в качестве основы для рассуждений о временных описаниях событий.
Формальное описание
связи
Следующие 13 базовых отношений отражают возможные отношения между двумя интервалами.
Связь | Иллюстрация | Интерпретация |
---|---|---|
| X предшествует Y Y предшествует X | |
| X встречает Y Y встречается с X ( i означает i nverse ) | |
| X перекрывается с Y Y перекрывается X | |
| X начинает Y Y начинается с X | |
| X во время Y Y содержит X | |
| X заканчивает Y Y заканчивается X | |
X равно Y |
Используя это исчисление, данные факты можно формализовать, а затем использовать для автоматических рассуждений. Отношения между интервалами формализованы как наборы базовых отношений.
Предложение
- Во время обеда Питер читает газету. После этого он ложится спать.
формализована в алгебре интервалов Аллена следующим образом:
В общем, количество различных отношений между n интервалами, начиная с n = 0, равно 1, 1, 13, 409, 23917, 2244361 ... OEIS A055203 . Показанный выше частный случай предназначен для n = 2.
Составление отношений между интервалами
Для рассуждений о соотношениях между временными интервалами интервальная алгебра Аллена предоставляет композиционную таблицу. Учитывая связь между а также и связь между а также , таблица состава позволяет сделать вывод о связи между а также . Вместе с обратной операцией это превращает интервальную алгебру Аллена в алгебру отношений .
Например, можно сделать вывод .
Расширения
Алгебра интервалов Аллена может использоваться для описания как временных интервалов, так и пространственных конфигураций. Для последнего использования отношения интерпретируются как описание относительного положения пространственных объектов. Это также работает для трехмерных объектов, если перечислить отношения для каждой координаты отдельно.
При изучении перекрывающейся разметки используется аналогичная алгебра (см. [1] ). Его модели имеют больше вариаций в зависимости от того, разрешено ли конечным точкам структур документа быть действительно совмещенными или просто [касательными].
Реализации
- Простая библиотека Java, реализующая концепцию временных отношений Аллена и алгоритм согласованности путей.
- Библиотека Java, реализующая алгебру интервалов Аллена (включая структуры данных и индексов, например, interval_tree )
- OWL-Time Time Ontology в OWL - онтология OWL -2 DL временных концепций для описания временных свойств ресурсов в мире или описанных на веб-страницах.
- GQR является аргументом в пользу алгебры интервалов Аллена (и многих других).
- qualreas - это среда Python для качественных рассуждений над сетями алгебр отношений, такими как RCC-8, алгебра интервалов Аллена и алгебра Аллена, интегрированная с точками времени и расположенная во времени с левым или правым ветвлением.
- SparQ - аргумент в пользу алгебры интервалов Аллена (и многих других).
- EveXL - это небольшой предметно-ориентированный язык для обнаружения событий, который реализует операторы интервальной алгебры с помощью художественных шаблонов ASCII.
Смотрите также
Рекомендации
- ^ Стивен ДеРоуз. Перекрытие разметки: обзор и лошадь. In 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 . ISSN 0001-0782 .
- Небель, Бернхард ; Bürckert, Ханс-Юрген (1995). «Рассуждения о временных отношениях: Максимально управляемый подкласс интервальной алгебры Аллена» . Журнал ACM . 42 : 43–66. DOI : 10.1145 / 200836.200848 .[ постоянная мертвая ссылка ]
- ван Бик, Питер; Манчак, Деннис В. (1996). «Дизайн и экспериментальный анализ алгоритмов временных рассуждений» (PDF) . Журнал исследований искусственного интеллекта . 4 (1996): 1–18. arXiv : cs / 9601101 . Bibcode : 1996cs ........ 1101V . DOI : 10.1613 / jair.232 .