Allensova intervalová algebra - Allens interval algebra - Wikipedia
Typ booleovské algebry zvaný intervalová algebra viz Booleova algebra (struktura)
Allenova intervalová algebra je počet pro časové uvažování který představil James F. Allen v roce 1983.
Kalkul definuje možné vztahy mezi časovými intervaly a poskytuje tabulku složení, kterou lze použít jako základ pro uvažování o časových popisech událostí.
Formální popis
Vztahy
Následující 13 základních vztahů zachycuje možné vztahy mezi dvěma intervaly.
Vztah | Ilustrace | Výklad |
---|---|---|
![]() | X předchází Y Y předchází X | |
![]() | X splňuje Y Y je splněno X (i znamená inverse) | |
![]() | X se překrývá s Y. Y se překrývá s X | |
![]() | X začíná Y Y začíná X | |
![]() | X během Y Y obsahuje X | |
![]() | X končí Y Y končí X | |
![]() | X se rovná Y |
Pomocí tohoto počtu lze daná fakta formalizovat a poté použít pro automatické uvažování. Vztahy mezi intervaly jsou formalizovány jako sady základních vztahů.
Věta
- Během večeře Peter čte noviny. Poté jde spát.
je formován v Allenově intervalové algebře takto:
Obecně platí, že počet různých vztahů mezi n intervaly, počínaje n = 0, je 1, 1, 13, 409, 23917, 2244361 ... OEIS A055203. Výše uvedený speciální případ platí pro n = 2.
Složení vztahů mezi intervaly
Pro úvahy o vztazích mezi časovými intervaly poskytuje Allenova intervalová algebra a složení stůl. Vzhledem ke vztahu mezi a a vztah mezi a , tabulka složení umožňuje učinit závěr o vztahu mezi a . Společně s a konverzovat operace, to změní Allenovu intervalovou algebru na a relační algebra.
Například lze odvodit .
Rozšíření
Allenovu intervalovou algebru lze použít k popisu časových intervalů i prostorových konfigurací. Pro druhé použití jsou vztahy interpretovány jako popis relativní polohy prostorových objektů. Funguje to také pro trojrozměrné objekty tak, že vypisujete relaci pro každou souřadnici zvlášť.
Studium překrývající se označení používá podobnou algebru (viz [1]). Jeho modely mají více variant v závislosti na tom, zda je povoleno, aby byly koncové body struktur dokumentů skutečně umístěny společně, nebo pouze [tečna].
Implementace
- Jednoduchá java knihovna implementující koncept časových vztahů Allena a algoritmus konzistence cesty
- Java knihovna implementující Allenovu intervalovou algebru (vč. datových a indexových struktur, např. interval_tree )
- Časová ontologie OWL v OWL ontologie časových konceptů OWL-2 DL pro popis časových vlastností zdrojů ve světě nebo popsaných na webových stránkách.
- GQR je důvodem pro Allenovu intervalovou algebru (a mnoho dalších)
- Kvalitní je rámec Pythonu pro kvalitativní uvažování nad sítěmi relačních algeber, jako je RCC-8, Allenova intervalová algebra a Allenova algebra integrovaná s časovými body a umístěná v levém nebo pravém větvícím čase.
Viz také
Reference
- ^ Steven DeRose. Překrývání značek: Recenze a kůň. In Proceedings of Extreme Markup Languages 2004, Montréal, Québec, 2. - 6. srpna 2004.http://xml.coverpages.org/DeRoseEML2004.pdf
Zdroje
- Allen, James F. (26. listopadu 1983). „Udržování znalostí o časových intervalech“ (PDF). Komunikace 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). „Úvaha o časových vztazích: maximální vlečná podtřída Allenovy intervalové algebry“. Deník ACM. 42: 43–66. doi:10.1145/200836.200848.[trvalý mrtvý odkaz ]
- van Beek, Peter; Manchak, Dennis W. (1996). „Návrh a experimentální analýza algoritmů pro časové uvažování“ (PDF). Journal of Artificial Intelligence Research. 4 (1996): 1–18. arXiv:cs / 9601101. Bibcode:1996cs ........ 1101V. doi:10.1613 / jair.232.