Temporal Reasoning: Allen’s Algebra and PyReason

📍 Where we are: Part VI · Annotated and Temporal Logic — Chapter 20. Annotated Logic taught us to hang a value on every fact — a provenance token, a confidence in a lattice, an interval of time. This chapter takes that last kind of label, the interval, and makes it the thing we reason about: not "when is this true," but "how do two true-over-time facts line up," and what that lets a reasoner conclude.

A fact in an ontology is usually timeless: Professor(alice) either holds or it does not. But most of what we know about the world holds over a stretch of time — alice was a PhD student, then a postdoc, then faculty — and, crucially, what we actually know is rarely the exact dates. We know that her PhD ended when her postdoc began, that her faculty years came after both. Temporal reasoning is the art of computing with those relationships when the numbers are missing, and it has an algebra all its own.

The simple version

Imagine you are told three things about a movie night: the trailers ran right up until the film started, the film ran right up until the credits, and you want to know how the trailers relate to the credits. You never learn a single clock time. Yet you can be certain the trailers finished before the credits began — because "right up until" chained twice can only mean "before." Allen's algebra is the bookkeeping that makes that chaining exact: name every way two time spans can line up, then tabulate what each pairing implies about a third.

What this chapter covers

• Why time needs its own algebra — a fact holds over an interval, and what we usually know is not endpoints but how intervals relate; the thirteen relations come in six inverse pairs plus equality.
• The thirteen relations, decoded — before/after, meets/met-by, overlaps/overlapped-by, during/contains, starts/started-by, finishes/finished-by, equals, each pinned to an exact endpoint test in the companion's relation function.
• Composition as transitive inference — given $I\,r_1\,J$ and $J\,r_2\,K$, which relations $I \to K$ are still possible; the full 13-by-13 table is computed by construction, not hand-typed.
• The academic world, dated — career intervals for alice and bob, and the real run showing PhD meets postdoc meets faculty.
• Two telling compositions — compose(meets, meets) and compose(before, before) each collapse to a single certain answer; compose(before, after) explodes to all thirteen, the entry that tells the reasoner nothing.
• PyReason in one paragraph — the open-world, annotated, temporal logic engine that scales this idea to whole graphs evolving over time.

Why time needs its own algebra

An interval is a stretch of time with a start and an end. Write it $I = (a, b)$ where $a$ is the start, $b$ the end, and $a \lt b$ always — an interval has positive duration [1]. A fact "holds over" an interval: phd(alice) is true across $(2005, 2010)$, not at a single instant.

Now the key move. We rarely know $a$ and $b$ as calendar dates. What we know is how one interval sits relative to another: did the PhD end exactly when the postdoc started, or was there a gap, or did they overlap? Allen's interval algebra answers this by proving a small, complete fact: every ordered pair of intervals stands in exactly one of thirteen basic relations [2]. Not "at least one" and not "sometimes several" — exactly one, always. That exhaustiveness is what makes the algebra a genuine classification and not just a vocabulary.

The thirteen come in a tidy shape: six inverse pairs and one self-inverse. If $I$ is before $J$, then $J$ is after $I$ — same configuration, read from the other side. The one relation that is its own inverse is equals: if $I$ equals $J$, then $J$ equals $I$. Six pairs give twelve, plus equals, makes thirteen. Notation: we write $I\,r\,J$ to mean "interval $I$ stands in relation $r$ to interval $J$," so $\text{phd}\ \text{m}\ \text{postdoc}$ reads "the PhD interval meets the postdoc interval."

The thirteen relations, decoded

The companion file names all thirteen by their standard two-letter codes and pairs each code with its English name (annotated.py lines 204–210):

ALLEN = ["b", "bi", "m", "mi", "o", "oi", "d", "di", "s", "si", "f", "fi", "eq"]
ALLEN_NAME = {
    "b": "before", "bi": "after", "m": "meets", "mi": "met-by",
    "o": "overlaps", "oi": "overlapped-by", "d": "during", "di": "contains",
    "s": "starts", "si": "started-by", "f": "finishes", "fi": "finished-by",
    "eq": "equals",
}

What makes each relation precise is not the English word but a test on the four endpoints. Given $I = (a, b)$ and $J = (c, d)$, the relation function decides the single relation by a cascade of comparisons (annotated.py lines 213–238):

def relation(I, J) -> str:
    """Allen relation of interval I=(a,b) to J=(c,d), with a<b and c<d."""
    (a, b), (c, d) = I, J
    if a == c and b == d:
        return "eq"
    if b < c:
        return "b"
    if d < a:
        return "bi"
    if b == c:
        return "m"
    if d == a:
        return "mi"
    if a == c:
        return "s" if b < d else "si"
    if b == d:
        return "f" if c < a else "fi"
    if a < c < b < d:
        return "o"
    if c < a < d < b:
        return "oi"
    if c < a and b < d:
        return "d"
    if a < c and d < b:
        return "di"
    raise ValueError(f"degenerate intervals {I}, {J}")  # pragma: no cover

Read the cascade as a decision list: first the equality of both endpoints (equals); then the two "no overlap at all" cases, $I$ ends before $J$ starts (before) or $J$ ends before $I$ starts (after); then the two "touch at a point" cases, $I$'s end equals $J$'s start (meets) or the reverse (met-by); then shared starts, shared ends, and finally the strict interleavings. Every ordered pair falls through to exactly one return, and the final raise is unreachable for proper intervals — the guarantee "exactly one relation" made executable. Here is the whole catalog, each relation with its inverse and the exact endpoint condition the code tests:

relation	code	inverse	endpoint condition on $I=(a,b)$, $J=(c,d)$
before	b	bi	$b \lt c$
after	bi	b	$d \lt a$
meets	m	mi	$b = c$
met-by	mi	m	$d = a$
overlaps	o	oi	$a \lt c \lt b \lt d$
overlapped-by	oi	o	$c \lt a \lt d \lt b$
during	d	di	$c \lt a$ and $b \lt d$
contains	di	d	$a \lt c$ and $d \lt b$
starts	s	si	$a = c$ and $b \lt d$
started-by	si	s	$a = c$ and $d \lt b$
finishes	f	fi	$b = d$ and $c \lt a$
finished-by	fi	f	$b = d$ and $a \lt c$
equals	eq	eq	$a = c$ and $b = d$

Composition is transitive inference

The catalog names relations; the power is inference. Suppose a knowledge base tells you $I\,r_1\,J$ and $J\,r_2\,K$ but says nothing directly about $I$ and $K$. What can you conclude? This is composition, and it is the temporal cousin of the transitive-closure step we saw drive forward chaining. Formally, the composition of two relations is the set of base relations that could hold between $I$ and $K$:

$$r_1 \circ r_2 \;=\; \big\{\, r \;:\; \exists\, I, J, K.\; (I\,r_1\,J) \,\wedge\, (J\,r_2\,K) \,\wedge\, (I\,r\,K) \,\big\}.$$

The ∘ reads "composed with," the ∃ reads "there exist," and ∧ reads "and." In words: $r$ belongs to the composition exactly when some concrete arrangement of three intervals realizes $I\,r_1\,J$, $J\,r_2\,K$, and $I\,r\,K$ all at once. The result is a set because two relations rarely pin down a third uniquely — sometimes one answer survives, sometimes all thirteen do.

Most treatments print this 13-by-13 table as a hand-typed grid. The companion instead computes it, turning the existential definition directly into a loop over concrete small integer intervals (annotated.py lines 241–252):

def composition_table(n: int = 6):
    """Compute the full 13×13 Allen composition table *by construction*: for every
    triple of small integer intervals I, J, K, record that the relation I→K is
    achievable given the relations I→J and J→K. The result is the exact table."""
    intervals = [(a, b) for a in range(n + 1) for b in range(a + 1, n + 1)]
    table = {(r1, r2): set() for r1 in ALLEN for r2 in ALLEN}
    for I in intervals:
        for J in intervals:
            r1 = relation(I, J)
            for K in intervals:
                table[(r1, relation(J, K))].add(relation(I, K))
    return table

This is the $\exists\,I,J,K$ of the definition made literal: intervals is a finite stock of every interval with endpoints in $0..6$, and the triple loop witnesses every arrangement. For each triple it reads off $r_1 = \text{relation}(I, J)$ and $r_2 = \text{relation}(J, K)$, then adds the observed $\text{relation}(I, K)$ into the cell table[(r1, r2)]. Six distinct endpoint values are enough to realize every relative arrangement of three intervals — no configuration of three spans ever needs more than six distinct boundary points — so the union of observations over all triples is exactly the composition table, computed rather than transcribed: no hand-entry, no chance of a typo. That the interval stock is already saturated is easy to check empirically — the table built from $n=6$ is identical, cell for cell, to the one built from $n=12$. The one-line compose wrapper just looks a cell up (annotated.py lines 255–259).

How hard is temporal reasoning once you have this table? With a definite relation between each pair, composition is a table lookup and chaining is cheap. But real knowledge is disjunctive — a constraint might say $I$ is before or meets $J$ — and then deciding whether a whole network of such constraints is jointly satisfiable becomes NP-complete. Allen's original method propagates constraints by repeatedly intersecting composed relations (a procedure called path consistency, cubic in the number of intervals), which is sound but incomplete: it can fail to detect some inconsistencies [2]. Certainty is cheap; the general question of consistency is not.

Allen's thirteen interval relations and their composition: alice's PhD meets her postdoc meets her faculty years, so composing meets with meets certifies the PhD lies strictly before the faculty appointment — while composing before with after collapses to all thirteen, telling the reasoner nothing. Original diagram by the authors, created with AI assistance.

The academic world, dated

Now ground it. The companion attaches career intervals to the individuals of the running example — a fact that holds over a span of years (annotated.py lines 264–269):

INTERVAL_FACTS = {
    ("phd", "alice"): (2005, 2010),
    ("postdoc", "alice"): (2010, 2012),
    ("faculty", "alice"): (2012, 2025),
    ("phd", "bob"): (2008, 2013),
}

alice's three stages abut perfectly: the PhD ends in 2010, the postdoc begins in 2010; the postdoc ends in 2012, the faculty years begin in 2012. By the endpoint test that is meets twice over ($b = c$ in each case). Running the module confirms it and then composes the two meetings into a conclusion about the pair we never stated directly:

Allen interval algebra (13 relations):
  phd(2005, 2010) vs postdoc(2010, 2012): meets
  postdoc(2010, 2012) vs faculty(2012, 2025): meets
  compose(m, m) = ['b']  ⟹  phd is 'before' faculty
  compose(b, b)   = ['b']   (transitivity of 'before')
  compose(b, bi)  = 13 relations (the total-uncertainty entry)

Read the third line as the whole point of the chapter: nobody wrote down how the PhD relates to the faculty years, yet compose(m, m) = {b} proves it can only be before. That is genuine inference from relations alone, no dates required — the temporal echo of deriving grandAdvisor from a chain of advises. (The dates are here only so the companion can check its own answer; strip them and the composition still holds.) Note too that alice's PhD $(2005, 2010)$ and bob's $(2008, 2013)$ overlaps rather than meets — the same machinery cleanly distinguishes careers that abut from careers that run partly in parallel.

Two compositions that say everything, and one that says nothing

Three cells from the table, printed above, tell the whole story of what composition buys and where it stops:

composition	result	reading
compose(meets, meets)	{before}	two back-to-back abutments force the first span strictly before the third
compose(before, before)	{before}	before is transitive — a lone, certain answer, like any ordering
compose(before, after)	all 13	total uncertainty: the composition constrains nothing at all

The first two cells are the good news: composition can shrink possibility to a single relation, and when it does, you have a proof. The third is the honest bad news. If $I$ is before $J$ and $J$ is after $K$ (that is, $K$ is also before $J$), then $I$ and $K$ are both somewhere left of $J$ — but nothing ties them to each other. Every one of the thirteen relations is realizable, so the composition returns the full set and the reasoner has learned nothing new. But this total shrug is rare: only three of Allen's 169 cells return all thirteen relations — before ∘ after, after ∘ before, and during ∘ contains — while more than half the table (97 of the 169 cells) pins the answer to a single, certain relation, and the average cell names just 2.42 possibilities. Composition is powerful precisely where the geometry pins things down, and mute only in those few cells where it does not. Knowing which cells are informative is half of using the algebra well.

PyReason: the practical descendant

Allen's algebra reasons about a handful of intervals in isolation. The modern engine that carries the idea to scale is PyReason: an open-world, annotated, temporal logic reasoner that runs rules over an entire graph whose facts each carry a bound — a confidence interval and a span of time-steps during which they hold — and propagates those annotated, timed facts across the graph until a fixpoint, one discrete time-step at a time [3]. It is the direct union of the three threads of this part: the lattice-valued confidences of the previous chapter, the interval-timed facts of this one, and the graph-shaped knowledge base of the whole volume. Where the companion computes one composition table over four toy intervals, PyReason answers "which nodes satisfy this rule, with what confidence, at which times" over millions of edges evolving through time — the same interval intuition, industrialized.

The unsolved part

Annotations — provenance, confidence, and time — make a knowledge base richer, but they also hand it two new ways to fail, and Allen's algebra shows the sharper one in miniature. First, richer facts can become inconsistent: attach intervals to enough facts and impose enough relations, and the constraints may have no joint solution at all — there is no way to place the intervals on a line. Detecting that is exactly the NP-complete satisfiability question above, and Allen's own polynomial propagation can miss it, certifying "consistent" a network that secretly is not. Second, and opposite, under the open-world assumption a temporal knowledge base can simply stay silent: compose(before, after) returning all thirteen relations is the reasoner honestly reporting that it cannot narrow things down, and no amount of further composition will break the tie. So annotation leaves us between two failure modes — a base that says too much and contradicts itself, or one that says too little and abstains. Which of those a reasoner should do about — repair the contradiction, or accept the abstention — is the question the algebra raises but cannot answer.

Why it matters

Neuro-symbolic systems increasingly reason over data that is timestamped, streaming, and uncertain — sensor logs, clinical timelines, event graphs — where the useful signal is almost never exact clock values but the relationships between spans. Allen's thirteen relations give the symbolic half of such a system a complete, decidable vocabulary for those relationships, and composition gives it exact inference over them, computed here (not asserted) so every cell is checkable. That crisp temporal target is precisely what a learned model over time-series data is trying to approximate, and what a hybrid engine like PyReason threads together with confidence bounds. Time is not an afterthought bolted onto logic; it is a first-class structure with its own algebra, and knowing where that algebra is sharp (single-relation compositions) and where it shrugs (the total-uncertainty cells) is knowing exactly what a temporal reasoner can promise.

Key terms

• Interval — a time span $I = (a, b)$ with $a \lt b$; a fact holds over an interval rather than at an instant.
• Allen's interval algebra — the classification proving every ordered pair of intervals stands in exactly one of thirteen basic relations.
• The thirteen relations — six inverse pairs (before/after, meets/met-by, overlaps/overlapped-by, during/contains, starts/started-by, finishes/finished-by) plus the self-inverse equals, each fixed by an endpoint test.
• Inverse relation — the same configuration read from the other interval: $I\,\text{before}\,J$ iff $J\,\text{after}\,I$.
• Composition ($r_1 \circ r_2$) — the set of relations possible between $I$ and $K$ given $I\,r_1\,J$ and $J\,r_2\,K$; the temporal form of transitive inference.
• Total-uncertainty cell — a composition (e.g. before ∘ after) whose result is all thirteen relations, so the inference is vacuous; only three of the table's 169 cells are like this.
• Path consistency — Allen's cubic constraint-propagation method: sound but incomplete, since general interval-network satisfiability is NP-complete.
• PyReason — an open-world, annotated, temporal logic engine that scales interval-and-confidence reasoning to whole graphs over time.

Where this leads

Composition sometimes narrows possibility to a single certain relation and sometimes returns all thirteen — a reasoner that abstains. And annotated bases can push the other way, past silence into outright contradiction. Both outcomes are consequences of the same open-world, annotated setting this part has built up. The next chapter, Open-World and Inconsistency: Abstention and Repair, faces them head-on: what a reasoner should do when its knowledge base entails nothing (abstain) or entails everything (a contradiction, from which classical logic derives all facts at once), and how to repair a base back to sanity without throwing away the good facts along with the bad.