álgebra de intervalos de Allen

Cálculo para el razonamiento temporal (relativo a instancias de tiempo) de eventos.

El álgebra de intervalos de Allen es un cálculo para el razonamiento temporal introducido por James F. Allen en 1983.

El cálculo define posibles relaciones entre 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 base capturan las posibles relaciones entre dos intervalos.

Usando este cálculo, los hechos dados pueden formalizarse y luego usarse para el razonamiento automático. Las relaciones entre intervalos se formalizan como conjuntos de relaciones base.

Las oraciones

Durante la cena, Peter lee el periódico. Después se va a la cama.

se formalizan en el álgebra de intervalos de Allen de la siguiente manera:

${\displaystyle {\mbox{newspaper }}\mathbf {\{\operatorname {d} \}} {\mbox{ dinner}}}$

${\displaystyle {\mbox{dinner }}\mathbf {\{\operatorname {<} \}} {\mbox{ bed}}}$

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 . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Y}$ ${\displaystyle Z}$ ${\displaystyle X}$ ${\displaystyle Z}$

Por ejemplo, se puede inferir . ${\displaystyle {\mbox{newspaper }}\mathbf {\{\operatorname {<} ,\operatorname {m} \}} {\mbox{ bed}}}$

Extensiones

El álgebra de intervalos de Allen se puede utilizar para la descripción tanto de intervalos temporales como de configuraciones espaciales. Para este último uso, se interpreta que las relaciones describen la posición relativa de los objetos espaciales. Esto también funciona para objetos tridimensionales al enumerar la relación de 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 de documentos estén realmente ubicados conjuntamente 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 Java que implementa el álgebra de intervalos de Allen (incluidas estructuras de datos e índices, por ejemplo, árbol de intervalos )
• OWL-Time Time Ontology en OWL, una ontología OWL-2 DL de conceptos temporales, para describir las propiedades temporales de los recursos en el mundo o descritos en páginas web.
• GQR es un razonador del á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, álgebra de intervalos de Allen y álgebra de Allen integrada con puntos de tiempo y situada en 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 del álgebra de intervalos a través de patrones artísticos ASCII.

Ver también

• Lógica temporal
• Lógica
• Cálculo de conexión de región
• Relación espacial (analógica)
• Razonamiento de sentido común

Referencias

1. Steven DeRose. Superposición de marcado: una revisión y un caballo. En Proceedings of Extreme Markup Languages ​​2004, Montreal, Québec, 2 al 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. hdl :1802/10574. ISSN  0001-0782. S2CID  16729000.
• Nebel, Bernhard ; Bürckert, Hans-Jürgen (1995). "Razonamiento sobre relaciones temporales: una subclase manejable máxima del álgebra de intervalos de Allen" (PDF) . Revista de la ACM . 42 : 43–66. doi : 10.1145/200836.200848 . S2CID  6586759.
• van Beek, Peter; Manchak, Dennis W. (1996). "El diseño y análisis experimental de algoritmos de razonamiento temporal" (PDF) . Revista de investigación en inteligencia artificial . 4 (1996): 1–18. arXiv : cs/9601101 . Código Bib : 1996cs.......1101V. doi :10.1613/jair.232. S2CID  3204600. Archivado desde el original (PDF) el 6 de julio de 2017 . Consultado el 6 de mayo de 2017 .