(Last modified Fri Apr 11 15:39 2008)

allen: A tool for doing calculations involving Allen's interval algebra

Allen's interval algebra has operations on relations, notably composition, that are complicated enough that a tool can provide welcome assistance. allen does these significant calculations, as well as some other simpler ones:

Compose arbitrary Allen relations, such as (o).(D)=(pmoFD) or (pmoFD).(dfO)=(pmoFDseSdfO).
Complement a relation.
Calculate the converse of a relation.
Calculate the intersection of two relations.
Calculate the union of two relations.
Any expression involving the above operations.

There are also a number of tedious or lengthy calculations on subclasses of the interval algebra that allen will do:

Enumerate the relations of the full interval algebra.
Read an arbitrary list of relations.
Close a set of relations under any of the operations listed above.
Determine if a set of relations is closed, and list counterexamples if it is not.
Determine whether a set of relations is a subclass of any of the eighteen maximal tractable subalgebras, and list counterexamples if it is not.
Exclude relations that are not part of a specific maximal tractable subalgebra.

java -jar allen.jar -help shows allen's options and usage for performing calculations with Allen relations.
java -cp allen.jar allen.subclass.Command -help shows allenSubclass's options and usage for working with subclasses of the full interval algebra.
An ISR technical report describes its function and gives a brief introduction to Allen's interval algebra.
Some examples and discussion of its use.

References on Allen's interval algebra

James F. Allen. "Maintaining knowledge about temporal intervals". Communications of the ACM 26[11] pp.832-843, Nov. 1983.

Thomas A. Alspaugh. "Software support for calculations in Allen's interval algebra". Technical Report UCI-ISR-05-02, Institute for Software Research, University of California, Irvine, Feb. 2005. .

Andrei Krokhin, Peter Jeavons, and Peter Jonsson, "Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra". Journal of the ACM 50(5), pp. 591-640, 2003.