Para el tipo de álgebra booleana llamada álgebra de intervalo, vea álgebra booleana (estructura)
El álgebra de intervalos de Allen es un cálculo para el razonamiento temporal que fue introducido por James F.Allen en 1983.
El cálculo define las posibles relaciones entre los intervalos de tiempo y proporciona una tabla de composición que puede usarse como base para razonar sobre descripciones temporales de eventos.
Descripción formal
Relaciones
Las siguientes 13 relaciones de base capturan las posibles relaciones entre dos intervalos.
Relación | Ilustración | Interpretación |
---|---|---|
| X precede a Y Y está precedido por X | |
| X se encuentra con Y Y se cumple por X ( i Soportes para i nverse ) | |
| X se superpone con Y Y está superpuesto por X | |
| X comienza Y Y comienza con X | |
| X durante Y Y contiene X | |
| X termina Y Y está terminado por X | |
X es igual a Y |
Usando este cálculo, los hechos dados se pueden formalizar y luego usar para el razonamiento automático. Las relaciones entre intervalos se formalizan como conjuntos de relaciones de base.
La frase
- Durante la cena, Peter lee el periódico. Luego, se va a la cama.
se formaliza en el Álgebra de intervalos de Allen de la siguiente manera:
En general, el número de relaciones diferentes entre n intervalos, comenzando con n = 0, es 1, 1, 13, 409, 23917, 2244361 ... OEIS A055203 . El caso especial que se muestra arriba es para n = 2.
Composición de relaciones entre intervalos
Para razonar sobre las relaciones entre intervalos temporales, el álgebra de intervalos de Allen proporciona una tabla de composición . Dada la relación entre y y la relación entre y , la tabla de composición permite concluir sobre la relación entre y . Junto con una operación inversa , esto convierte el álgebra de intervalos de Allen en un álgebra de relaciones .
Por ejemplo, se puede inferir .
Extensiones
El álgebra de intervalos de Allen se puede utilizar para la descripción de intervalos temporales y configuraciones espaciales. Para este último uso, las relaciones se interpretan como una descripción de la posición relativa de los objetos espaciales. Esto también funciona para objetos tridimensionales al enumerar la relación para cada coordenada por separado.
El estudio del marcado superpuesto utiliza un álgebra similar (ver [1] ). Sus modelos tienen más variaciones dependiendo de si se permite que los puntos finales de las estructuras del documento sean realmente coubicados o simplemente [tangentes].
Implementaciones
- Una biblioteca Java simple que implementa el concepto de relaciones temporales de Allen y el algoritmo de consistencia de ruta.
- Biblioteca de Java que implementa el álgebra de intervalos de Allen (incluidas estructuras de índice y datos, por ejemplo, interval_tree )
- OWL-Time Ontología de tiempo en OWL una ontología OWL-2 DL de conceptos temporales, para describir las propiedades temporales de recursos en el mundo o descritos en páginas web.
- GQR es un razonador para el álgebra de intervalos de Allen (y muchos otros)
- qualreas es un marco de Python para el razonamiento cualitativo sobre redes de álgebras de relaciones, como RCC-8, el álgebra de intervalo de Allen y el álgebra de Allen integrado con puntos de tiempo y situado en el tiempo de ramificación izquierda o derecha.
- SparQ es un razonador del álgebra de intervalos de Allen (y muchos otros)
- EveXL es un pequeño lenguaje de dominio específico para la detección de eventos que implementa los operadores de Interval Algebra a través de patrones de arte ASCII.
Ver también
Referencias
- ^ Steven DeRose. Superposición de marcas: una revisión y un caballo. En Proceedings of Extreme Markup Languages 2004, Montreal, Québec, 2-6 de agosto de 2004. http://xml.coverpages.org/DeRoseEML2004.pdf
Fuentes
- Allen, James F. (26 de noviembre de 1983). "Mantener el conocimiento sobre los intervalos temporales" (PDF) . Comunicaciones de la ACM . 26 (11): 832–843. CiteSeerX 10.1.1.472.5244 . doi : 10.1145 / 182.358434 . ISSN 0001-0782 .
- Nebel, Bernhard ; Bürckert, Hans-Jürgen (1995). "Razonamiento sobre las relaciones temporales: una subclase manejable máxima del álgebra de intervalo de Allen" . Revista de la ACM . 42 : 43–66. doi : 10.1145 / 200836.200848 .[ enlace muerto permanente ]
- van Beek, Peter; Manchak, Dennis W. (1996). "El diseño y análisis experimental de algoritmos para el razonamiento temporal" (PDF) . Revista de Investigación en Inteligencia Artificial . 4 (1996): 1–18. arXiv : cs / 9601101 . Bibcode : 1996cs ........ 1101V . doi : 10.1613 / jair.232 .