Reason about relations between intervals, and between points and intervals, in JavaScript and TypeScript.
In 1983, James Allen proposed reasoning about the relationships between intervals with an interval algebra (IA): Allen, James F. “Maintaining knowledge about temporal intervals”, Communications of the ACM 26(11) pages 832-843; November 1983.
Good synopses of this theory are
Allen noticed that reasoning about time often has to deal with incomplete or imprecise data, and that this is difficult when this is done with points on a time axis (“state space approaches”). He found that reasoning instead about the relationships between intervals as first class objects, without mapping them to a time axis, is often easier and leads to better results. This is not limited to reasoning about time, but applies to all domains where intervals are used on a set with strict total order.
This library realizes Allen’s Interval Algebra, and offers his implementation for inference.
The main reason for the existence of this library however is the fact that in modern business software we are confronted with incomplete and imprecise data about time with points on a time axis nevertheless. It is used as a dependency in @toryt/intervals, which attempts to bridge the gap. ppwcode dotnet-util-allen offers a C# version of the functionality of this library.
Allen’s Interval Algebra is an algebra over a set with 13 relations as elements. The approach is general and can also be applied to sets with a different number of relations (e.g., 3 for the strict total order (<, =, >), or 5 for the relationships between points and intervals). Allen’s Interval Algebra is realized in this library as a specialization of a more general class, that allows other extensions for algebras with a different number of elements.
We find that there are 13 basic relations possible between definite intervals. In this library, we use the notation as found in Thomas A. Alspaugh “Allen's interval algebra”.
| Basic relation | AR(i1, i2) | Illustration |
|---|---|---|
| i1 precedes i2 | (p) |  |
| i1 meets i2 | (m) |  |
| i1 overlaps i2 | (o) |  |
| i1 is finished by i2 | (F) |  |
| i1 contains i2 | (D) |  |
| i1 starts i2 | (s) |  |
| i1 equals i2 | (e) |  |
| i1 is started by i2 | (S) |  |
| i1 during i2 | (d) |  |
| i1 finishes i2 | (f) |  |
| i1 is overlapped by i2 | (O) |  |
| i1 is met by i2 | (M) |  |
| i1 is preceded by i2 | (P) |  |
These 13 basic relations are an orthogonal basis for all possible general relation-conditions between two intervals.
i1 (pm) i2 says that an interval i1 precedes or meets an interval i2. i3 (FDseSdf) i4 says that an interval i3 is finished by or contains or starts or equals or is started by or is during or finishes an interval i4. This implies ¬ (i3 (pmoOMP) i4): i3 does not precede and does not meet and does not overlap and is not overlapped by and is not met by and is not preceded by i4.
Each general relation expresses a certain amount of uncertainty, where a basic relation expresses certainty, and the full relation (pmoFDseSdfOMP) expresses complete uncertainty.
These 8192 (213), general relations form an algebra, with the operations:
- ∁
complement - ~
converse - \
min - ∨ (disjunction, union,
or) - ∧ (conjunction, intersection,
and) - ⨾ (
compose)
A relation implies another relation, or not. E.g., if we have determined that a relation between i1 and
i2 is (oO), and we need it to be (pmoOMP), this is ok because (oO) ⊢ (pmoOMP). If the relation is
(oeO) however, it is not ok ((oO) ⊬ (pmoOMP)), because (pmoOMP) does not allow the intervals to be equal
((e)).
When the relation between 2 intervals i1 and i2 is, e.g., (oFD), we write i1 (oFD) i2 or AR(i1, i2) = (oFD).
- Allen Relations
- Interval Constraints
- Points as intervals
- Comparing points with intervals
- Code documentation
Repo, CI, issues, pull requests This project is maintained in Bitbucket (repo, CI, issues, pull requests, …).
TODO Branches are copied automatically to [GitHub] by CI. This is done as backup, and because open source projects are more easily found there. Issues and pull requests there will not be reviewed.
This code uses the application to TypeScript of the Standard coding style.
All functions and methods are protected with explicit asserts, that throw when a precondition is violated. Although
written in TypeScript, types are verified dynamically too, so that type safety is ensured dynamically when the library
is used with plain JavaScript too.
Tests require complete code coverage.
eslint is used for linting, and prettier for code formatting. But it is hell to get them to work together nicely,
for years. At this time,
Setting up ESlint with Standard and Prettier
seems to be a viable approach.
- van Beek, Peter; Cohen, Robin “Exact and Approximate Reasoning about Temporal Relations”, Computational Intelligence 6:132-144, 1990
- Hogge, J. C. “TPLAN: A Temporal Interval-Based Planner with Novel Extensions”, University of Illinois Department of Computer Science Technical Report UIUCDCS-R-87-1367, September 1987 (no version found on the internet)
- Freuder, E. C. “Synthesizing Constraint Expressions”, Communications of the ACM 21 pages 958-966; November 1978
- Eriksson, Leif; Lagerkvist, Victor “Improved Algorithms for Allen’s Interval Algebra: a Dynamic Programming Approach”, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)
- Allen, J.; Fikes, R.; Sandewall, E. ”Principles of Knowledge Representation and Reasoning; Proceedings of the Second International Conference (KR91)”
Released under the Apache License, Version 2.0.
Copyright © 2022 – 2023 by Jan Dockx
Licensed under the Apache License, Version 2.0 (the “License”); you may not use this file except in compliance with the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an “AS IS” BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
This code was based on a Java implementation last updated in December 2008.