# PAA: The Probabilistic Allen Algebra: A Generative and Complete Probabilistic Extension of Allen's Interval Relations

arXiv: https://arxiv.org/abs/2609.20634 · HTML: https://mlsanity.com/paper/2609.20634/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 49 references that are in the map.
- First posted on arXiv 17 Sep 2026.

## Builds on (most cited first, 9 of 9)

- [Probabilistic Object Detection: Definition and Evaluation](https://mlsanity.com/paper/1811.10800/) (2018)
- [Backpropagation through Signal Temporal Logic Specifications: Infusing Logical Structure into Gradient-Based Methods](https://mlsanity.com/paper/2008.00097/) (2020)
- [Fine-Grained Temporal Relation Extraction](https://mlsanity.com/paper/1902.01390/) (2019)
- [Control from Signal Temporal Logic Specifications with Smooth Cumulative Quantitative Semantics](https://mlsanity.com/paper/1904.11611/) (2019)
- [More than Classification: A Unified Framework for Event Temporal Relation Extraction](https://mlsanity.com/paper/2305.17607/) (2023)
- [Allen's Interval Algebra Makes the Difference](https://mlsanity.com/paper/1909.01128/) (2019)
- [TRAVELER: A Benchmark for Evaluating Temporal Reasoning across Vague, Implicit and Explicit References](https://mlsanity.com/paper/2505.01325/) (2025)
- [Probabilistic Temporal Reasoning with Endogenous Change](https://mlsanity.com/paper/1302.4954/) (2013)
- [A Factorized Probabilistic Model of the Semantics of Vague Temporal Adverbials Relative to Different Event Types](https://mlsanity.com/paper/2505.01311/) (2025)

## Abstract (arXiv)

Allen's interval algebra is a qualitative calculus for temporal relations, but its thirteen base relations are crisp predicates over exact interval boundaries. This is inadequate for temporal information from language, perception, databases, or uncertain histories, where times, durations, and boundaries are uncertain and expressions such as "just before" or "roughly during" have graded meaning. We develop the probabilistic Allen algebra (PAA): a generative and complete extension in which relation probabilities are derived from distributions over interval boundaries rather than assigned as scores. Time points are Gaussian; intervals have Gaussian midpoints and truncated-Gaussian durations. Every relation is a boundary-ordering predicate in one common probability space: point-point relations reduce to error functions, and point-interval and interval-interval relations to multivariate Gaussian orthant probabilities induced by linear inequalities. Contact relations (meets, starts, finishes, equals) receive positive measure through a tolerance band, and under a single tolerance the thirteen relations form a true partition that recovers crisp Allen as the tolerance vanishes. The construction derives Allen's taxonomy rather than positing it: coarse predicates such as precedence, overlap, and containment are unions of leaves whose probabilities are leaf sums, and this hierarchy is preserved as intervals collapse to points and thirteen relations reduce to five and then three. Each relation further decomposes into correlation-aware temporal primitives in the spirit of CIDOC CRM. The algebra is scale-invariant and separates graded expressions such as "shortly before" from contact relations. All results are Monte-Carlo validated and shipped as an open, tested Python package.