arXiv CSopen access

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

· arxiv_cs

arXiv CS · Papers · License: Open Access

artificial intelligence, reasoning, knowledge representation

PAA: The Probabilistic Allen Algebra A generative and complete probabilistic extension of Allen’s interval relations Julian Eggert∗ September 17, 2026

arXiv:2609.20634v1 [cs.AI] 17 Sep 2026

Abstract Allen’s interval algebra provides a qualitative calculus for temporal relations, but its base relations are crisp predicates over exact interval boundaries. This is inadequate for temporal information extracted from language, perception, databases, or uncertain histories, where event times, durations, and boundaries are uncertain and where expressions such as just before, roughly during, or starting with have graded semantics. We develop the probabilistic Allen algebra: a generative and complete extension of Allen’s calculus in which relation probabilities are derived from distributions over interval boundaries rather than assigned as scores. Time points are Gaussian variables; intervals are represented by Gaussian midpoints and non-negative durations obtained by truncating latent Gaussian duration variables. Each relation is then a measurable boundary-ordering predicate in one common temporal probability space, rather than an independently assigned class score. Point–point relations admit closed forms using the error function and complementary error function. Point–interval and interval–interval relations become multivariate Gaussian orthant probabilities induced by linear inequalities. Equality and contact relations, such as meets, starts, finishes, and equals, are treated through confidence borders or soft membership kernels. The construction derives Allen’s taxonomy rather than positing it: the thirteen relations arise as the sign-partition cells of the boundary geometry, their coarse predicates such as precedence, overlap, and containment are unions of leaves whose probabilities are the corresponding leaf sums, and this hierarchy is the invariant preserved as intervals collapse to points and the thirteen relations reduce to five and then three. For temporal language, we distinguish contact or boundary-sharing relations from verbal grading: expressions such as shortly before, rather before, or long before can be modeled by the graded strength of a relation family relative to alternatives, while meets, starts, and finishes remain contact relations controlled by tolerance parameters. Because the Gaussian relation probabilities depend only on standardized temporal separations, jointly scaling means, durations, uncertainty, and tolerances leaves every probability unchanged: the algebra is scale-invariant. Under a single tolerance the thirteen relations form a true partition that recovers crisp Allen as the tolerance vanishes. As in well-established logical reasoning frameworks such as CIDOC CRM, where relations are expressed through primitives, each relation decomposes into elementary boundary comparisons (temporal primitives), here lifted to a correlation-aware probabilistic form. The model therefore provides a robust bridge between metric temporal uncertainty, qualitative interval reasoning, and vague temporal adverbials in natural language. Beyond the complete theory, we provide an open, fully tested implementation that computes the relation probabilities directly.

Contents 1 Introduction 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ∗

3 3 5

Honda Research Institute, Carl-Legien-Str. 30, 63073 Offenbach, Germany. Email: [email protected]. Accompanying open-source implementation: https://github.com/HRI-EU/probabilistic-allen-algebra

2 Previous Work 2.1 Allen Interval Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Probabilistic Temporal Reasoning and Temporal Indeterminacy . . . . . . . . . . 2.3 Probabilistic Extensions of Allen Relations . . . . . . . . . . . . . . . . . . . . . 2.4 Usage and Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 5 6 6 7

3 Approach 3.1 Overview: From the Generative Definition to Closed Forms . . . . . . . . . . . . 3.2 Uncertain Times and Durations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Placing the Uncertainty: Which Quantities Are Known . . . . . . . . . . . . . . 3.4 A Common Linear-Inequality Semantics . . . . . . . . . . . . . . . . . . . . . . . 3.5 Relations Between Two Gaussian Points . . . . . . . . . . . . . . . . . . . . . . . 3.6 Confidence Borders and Graded Membership . . . . . . . . . . . . . . . . . . . . 3.7 Relations Between a Point and an Interval . . . . . . . . . . . . . . . . . . . . . . 3.8 Relations Between Two Intervals: Distribution-Induced Allen Algebra . . . . . . 3.8.1 The Tolerance Partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.9 Taxonomy as Probability Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . 3.10 Temporal Primitives and the (De)composition of Relations . . . . . . . . . . . . 3.11 Consistency of Limiting Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 8 8 9 10 10 10 11 12 13 14 16 18

4 Validation 18 4.1 A Worked Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 5 Discussion, Conclusions, and Applications 5.1 Comparison to Allen’s Hourglass . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 The Relation Phase Diagram, Taxonomy, and Dimensional Reduction . . . . . . 5.3 NLP: Relation Families, Verbal Grading, and Contact . . . . . . . . . . . . . . . 5.4 From Discrete Cuts to Graded Membership . . . . . . . . . . . . . . . . . . . . . 5.5 Scale Invariance and Context-Sensitivity Normalization . . . . . . . . . . . . . . 5.6 Where the Reference Scale Comes From: Extents, Spreads, and the Point Limit . 5.7 From Geometry to a Testable Hypothesis . . . . . . . . . . . . . . . . . . . . . . 5.8 Robustness and Inadequacy of Flat Relation Assignment . . . . . . . . . . . . . . 5.9 Selecting a Best-Fitting Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.10 Extension to Spatial Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.11 Limitations and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.12 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20 20 21 23 24 25 26 27 28 29 29 30 30

A The Thirteen Relations, Grouped

B Limiting Cases When Intervals Collapse to Points

C Alternative Interval Parameterizations 32 C.1 General Linear Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 D Primitive Factorization of the Probabilistic Algebra

E Software Interface and Implementation Notes

Lack of robustness: shifting Y by 0.4 flips the crisp relation, while the probabilities vary smoothly crisp: before

crisp: meets

X Y

crisp: overlaps

X Y

graded:

P(before)=0.68 P(meets)=0.24 P(overlaps)=0.09

P(meets)=0.35 P(before)=0.32 P(overlaps)=0.32

P(overlaps)=0.68 P(meets)=0.24 P(before)=0.09

Figure 1: Lack of robustness. Shifting Y by 0.4 flips the crisp relation before→meets→overlaps, while the distribution-induced probabilities (computed with boundary uncertainty) vary smoothly.

Introduction

1.1

Motivation

Temporal reasoning has two complementary traditions. In symbolic artificial intelligence and knowledge representation, qualitative temporal calculi abstract away metric time and reason with relations between intervals. Allen’s interval algebra is the canonical example: it represents the configuration of two intervals using relations such as before, meets, overlaps, during, starts, and finishes [1]. In probabilistic temporal reasoning, by contrast, probability is often used to describe how states or events evolve over time, for example in temporal graphical models, stochastic processes, filtering, and probabilistic temporal logics [22]. A different and less uniformly developed problem arises when the temporal objects themselves are uncertain. An event may be known to have happened, but its occurrence time may be imprecise; an interval may have uncertain start, end, midpoint, or duration; and a naturallanguage expression may communicate a qualitative temporal relation without committing to exact boundaries. Temporal database work has studied valid-time indeterminacy and probabilistic temporal data [14, 9], and probabilistic variants of interval algebra have been proposed [29, 30]. However, much of this work either assigns probabilities to relations directly or treats relation prediction as a flat classification problem over the thirteen Allen labels. Two failure modes of crisp relations motivate a graded treatment. First, relations are brittle: a sub-threshold shift of a single boundary flips the qualitative label (Figure 1). Second, crisp relations are inadequate: one label can cover markedly different configurations (Figure 2). In both cases the distribution-induced probabilities developed here vary smoothly and distinguish the situations, as the annotations in the two figures show. This paper argues for a distribution-induced view. The primitive uncertainty lives on the quantities that specify the temporal objects: the location of a time point and, for an interval, any consistent choice among its start, end, midpoint, and duration—these parameterizations are interchangeable, and we adopt midpoint and duration (Section 3.3; Appendix C). Because every Allen relation between two uncertain temporal objects X and Y (time points or intervals) is fixed by how their boundary points—both starts and ends—are ordered relative to one another (does X finish before Y starts? do they start together?), and each boundary is a linear function of these uncertain quantities, a relation holds on exactly a region of those quantities: the values that produce its ordering. Its probability is then how much of the distribution falls in that region. This has two consequences. First, it gives a direct probabilistic semantics to every

Inadequacy: three very different configurations, all crisply 'overlaps', distinguished by the probabilities

crisp: overlaps X

graded:

P(overlaps)=0.68 P(meets)=0.24 P(before)=0.09

P(overlaps)=0.99

P(overlaps)=0.61 P(equals)=0.14 P(finished_by)=0.07

Figure 2: Inadequacy. Three configurations are all crisply overlaps, yet they differ markedly; the probabilities separate the near-before case from the near-equals case. relation R:

Z P (X R Y ) =

1[X R Y ] p(X, Y ) dX dY.

(1)

Equation (1) is the conceptual core of the approach. Picture the two uncertain intervals as a recipe for producing concrete pairs: each time we draw from the uncertainty we obtain two ordinary intervals with definite start and end points. For any such definite pair a plain Allen relation either holds or it does not—either X lies entirely before Y , say, or it does not. The symbol 1[X R Y ] simply records this yes/no answer: it equals 1 when the relation holds and 0 when it does not. The density p(X, Y ) records how plausible each concrete pair is. The integral multiplies these two quantities and sums over all possible pairs, thereby accumulating the plausibility of exactly those pairs for which the answer is “yes.” The result is the probability that the relation holds. Equivalently, and more concretely: if we generated a large collection of concrete interval pairs according to the assumed uncertainty and checked the ordinary Allen relation for each, then P (X R Y ) would be the fraction of the collection in which R is true. Because every relation is a yes/no question about the same underlying pair, the thirteen probabilities are shares of one whole and add up to one; and none of them is assigned by hand—each is fixed entirely by the uncertainty placed on the time points and durations. The remainder of the paper turns this definition into closed-form expressions by taking the time points and durations to be Gaussian, under which the “yes” region is described by a few linear inequalities and the integral reduces to a standard multivariate Gaussian probability. This strict probabilistic approach makes the taxonomy of temporal relations explicit. The Allen leaves are not independent classes. Coarser predicates such as precedence, non-disjointness, containment, and contact are unions of leaves, and their probabilities are obtained by summing the probabilities of their refinements. Thus, if meets holds, then the coarser predicate “precedes or touches” also holds; if containment is probable, one can refine it into starts, during, finishes, or equals. This taxonomic view is essential for robustness. A small perturbation of boundaries can transform a crisp before relation into meets, or a during relation into starts. A flat classifier sees this as a label discontinuity. A hierarchical probabilistic model sees it as a transfer of probability mass within a stable parent predicate. For NLP, the same hierarchy suggests a separation between qualitative relation families and verbal grading. Contact relations such as meets or starts encode boundary correspondence and therefore require a margin or tolerance in continuous probability spaces. By contrast, many adverbials grade a temporal relation rather than asserting contact. Expressions such as just before, shortly before, rather before, some time before, and long before all describe how one 4

event stands in time relative to another—they are graded forms of the before family of Allen’s relations—and differ only in degree, not in whether the boundaries touch. Spatial language has the same structure: just above, far to the left of, and right beside grade qualitative spatial relations in the same way. Such adverbials express the degree to which a coarse relation family, for example precedence, is supported relative to its alternatives—that is, the relation probabilities themselves. Since these probabilities are dimensionless and depend on metric distances only after normalization by temporal uncertainty and duration scale, the model naturally normalizes context-sensitivity: one month before a two-month interval can receive the same graded beforeness as one hour before a two-hour interval when the underlying parameters are scaled consistently.

1.2

Contributions

The contributions are: (C1) We formalize uncertain time points as Gaussian variables and uncertain intervals as Gaussian midpoints with non-negative truncated-Gaussian durations. (C2) We derive closed point–point probabilities using erf and erfc, including confidence borders for equality. (C3) We derive point–interval relations as bivariate Gaussian CDFs in the general truncatedduration case, with error-function limits for deterministic durations. (C4) We derive interval–interval Allen relation probabilities as multivariate Gaussian CDFs over linear boundary inequalities. (C5) We introduce confidence borders for equality/contact relations and identify outer adjacency (meets, met by) and inner adjacency (starts, started by, finishes, finished by, equals). (C6) We show Allen’s relation taxonomy is derived, not stipulated : the thirteen leaves are the sign-partition cells of the boundary-difference geometry, their coarse predicates are unions of leaves whose probabilities are the leaf sums, and this hierarchy is the invariant preserved as intervals collapse to points. (C7) We position the approach relative to Allen’s Hourglass, arguing that our model gives distributional semantics and a principled treatment of equality/contact while preserving the robustness motivation. (C8) We discuss the bidirectional mapping between metric temporal uncertainty, graded relation membership, and vague temporal adverbials in NLP. (C9) We identify scale invariance as a desirable normalization property: verbal grading can be tied to relation probabilities rather than absolute distances, thereby reducing contextsensitivity across temporal scales.

Previous Work

2.1

Allen Interval Algebra

Allen’s interval algebra defines thirteen basic relations between two intervals X = [aX , bX ] and Y = [aY , bY ], assuming aX ≤ bX and aY ≤ bY [1]. The relations are mutually exclusive and jointly exhaustive for definite intervals. Table 1 gives the standard orientation X R Y , with the boundary ordering and an example arrangement (X filled, Y outlined) for each. 5

Relation

Boundary ordering

before meets overlaps starts during finishes equals finished by contains started by overlapped by met by after

aX < bX < aY < bY aX < bX = aY < bY aX < aY < bX < bY aX = aY < bX < bY aY < aX < bX < bY aY < aX < bX = bY aX = aY < bX = bY aX < aY < bX = bY aX < aY < bY < bX aX = aY < bY < bX aY < aX < bY < bX aY < bY = aX < bX aY < bY < aX < bX

Example

Table 1: Allen’s thirteen base relations: boundary ordering and an example arrangement of X (filled) and Y (outlined). Allen’s calculus is usually described as qualitative: it suppresses metric distances while retaining the ordering of boundaries. Subsequent work has studied composition tables, tractable subclasses, constraint propagation, and encodings for planning and scheduling [24]; representative results characterize maximal tractable subclasses of Allen’s algebra, including extensions that admit metric time [12], and carry the same constraint-based reasoning to qualitative spatial calculi [33]. These methods typically assume definite intervals or sets of possible qualitative relations, rather than continuous probability distributions over boundaries: they reason about which qualitative relations are consistent, whereas we assign each relation a probability derived from a distribution over the boundaries themselves.

2.2

Probabilistic Temporal Reasoning and Temporal Indeterminacy

The phrase probabilistic temporal reasoning is used in at least two senses. The first studies stochastic systems evolving over time: hidden Markov models, dynamic Bayesian networks, Kalman filters, temporal point processes, and stochastic temporal logics. These models ask which state holds, which event occurs, or which temporal property is satisfied. The second sense concerns uncertainty in temporal objects themselves. Valid-time indeterminacy represents facts whose occurrence time is uncertain [14]. Probabilistic temporal databases extend this idea toward algebraic operations over temporally uncertain tuples [9]. This second sense is closer to the present work, because the question is not only whether an event occurs, but when it occurred and how its temporal extent relates to another uncertain extent.

2.3

Probabilistic Extensions of Allen Relations

Mouhoub and Liu propose a probabilistic interval algebra for managing uncertain temporal relations [29], and probabilistic interval networks attach a probability to each Allen relation and propagate them through a constraint network [34]. Such work typically treats probabilities as annotations on qualitative relations or constraints. That is useful for temporal constraint networks, but differs from the distribution-induced approach here: we do not assume relation probabilities as primitives; we derive them from distributions over points and durations. 6

A parallel line softens Allen’s relations with fuzzy set theory rather than probability. Badaloni and Giacomin propose a fuzzy extension of Allen’s interval algebra in which each of the thirteen base relations carries a graded preference degree, later developed into the constraint algebra IAfuz for qualitative fuzzy temporal reasoning [3, 4]; Schockaert et al. fuzzify the interval relations to compare intervals with imprecise boundaries [36]. These approaches share our robustness motivation—a sub-threshold shift of one boundary should not flip a hard label—but the grading is supplied by membership functions chosen on the relations, not induced by a generative model over the underlying metric quantities, and the resulting degrees do not in general form a single probability distribution that sums to one across the thirteen relations. A complementary line in formal semantics models vagueness probabilistically rather than through fixed memberships—Lassiter and Goodman interpret a gradable adjective by Bayesian inference over an uncertain threshold [27]—but there too the grading attaches to a predicate against a threshold, not to interval relations induced by a distribution over boundary geometry. Allen’s Hourglass is especially relevant [30]. It diagnoses the brittleness of crisp Allen relations under noisy intervals and proposes a two-dimensional mapping based on relative position and relative size. The hourglass representation provides a robust probabilistic treatment of relation assignment and makes some symmetries of the Allen relations visually explicit. Its probabilities, however, are defined through primitive position and size relation functions rather than through a generative probability model over boundaries, midpoints, and durations. Moreover, equality-based relations such as contact are intrinsically delicate in continuous probability spaces. Our confidence-border treatment directly addresses this issue by replacing zero-measure boundary equalities with tolerance bands or soft membership kernels.

2.4

Usage and Applications

Temporal relations are central in NLP, planning, scheduling, robotics, healthcare, and event recognition. TimeML and TempEval provide annotation and evaluation frameworks for temporal expressions, events, and relations in text [31, 39]. Bayesian chronology tools also compute empirical probabilities of Allen relations from posterior samples of uncertain periods [13, 2]. In temporal relation extraction, the difficulty of distinguishing fine Allen relations has motivated coarse-to-fine and aggregated label schemes [38, 23], which our taxonomy renders principled as conditional refinement within a parent predicate. These works demonstrate the utility of probabilistic temporal relations, but they do not provide a general analytic Gaussian algebra for all point, point–interval, and interval–interval cases. Vague temporal adverbials are a particularly relevant application. Words such as recently, just, shortly, and long ago specify graded constraints over temporal distance and relation. Recent work has modeled such adverbials probabilistically as distributions conditioned by event type [26]. A distribution-induced Allen algebra provides a mechanism for mapping between such graded linguistic categories and concrete temporal probability distributions. A central modeling choice is whether these adverbials should be tied to absolute temporal distances or to confidence in qualitative relation families. Absolute-distance accounts are strongly context-sensitive: shortly before may mean seconds in one domain and months in another. In our framework, relation probabilities provide a dimensionless intermediate representation. The modifier shortly can be associated with a weak but dominant precedence probability, while long before can be associated with near-certain precedence, optionally combined with a context-specific expected gap.

2. Region 1[X R Y ] = {LR ≤ 0} in A, B, G, H (Tab. 2)

1. Definition P R (X R Y ) = 1[X R Y ] p

3. Substitution polytope in U : P(LR ≤ 0, D ≥ 0)/Q

4. Evaluation Gaussian mass = Φk (erf / erfc)

Figure 3: From the generative definition to a closed form in four steps, threaded by the running overlaps example (this section; the inequality table is Table 2, the orthant form Equation (31)).

Approach

3.1

Overview: From the Generative Definition to Closed Forms

The construction turns the generative definition into closed-form probabilities in four steps (Figure 3); the remainder of this section develops each, and we carry one relation, overlaps, through all four (Section 3.8). 1. Definition. AR relation’s probability is the mass of its indicator under the joint density, P (X R Y ) = 1[X R Y ] p(X, Y ) dX dY (Equation (1)). 2. Region. The indicator is a system of linear inequalities in the four boundary differences A, B, G, H—one row of Table 2 per relation, with a tolerance τ for contact (Section 3.8). 3. Substitution. The boundaries, hence the differences, are affine in a latent Gaussian vector U ; the region becomes a polytope in U , and the integral a conditional Gaussian mass P (R) = P(LR (U ) ≤ 0, D ≥ 0)/Q, writing P for the probability of a latent event (Equation (31); the same map underlies any parameterization, Appendix C). 4. Evaluation. A Gaussian mass over a polytope is a multivariate-normal CDF Φk (the k-variate generalization of the error function), reducing to erf / erfc for two points (Section 3.5) and to the bivariate Φ2 for a point and an interval (Section 3.7).

3.2

Uncertain Times and Durations

A time point x is represented by tx ∼ N (µx , σx2 ). An interval X is represented by a midpoint tX and non-negative duration dX : dX dX X = [aX , bX ] = tX − , tX + . 2 2

(2)

(3)

The midpoint is Gaussian, 2 tX ∼ N (µX , σX ),

(4)

and the duration is a lower-truncated latent Gaussian, DX ∼ N (µdX , σd2X ).

dX = DX | DX ≥ 0,

(5)

For σdX > 0, and writing Φ for the standard normal cumulative distribution function, the truncation normalizer is µdX QX = P(DX ≥ 0) = Φ . (6) σdX For σdX = 0, the duration is deterministic and the formula is interpreted as a limit.

We carry two forms of the duration throughout, and the distinction matters below. The lowercase dX ≥ 0 is the duration itself —the non-negative quantity that enters the boundaries aX , bX and hence the boundary differences A, B, G, H. The uppercase DX is its untruncated latent, which may be negative but is genuinely Gaussian, so that the vector collecting the latent quantities stays jointly Gaussian and every relation probability is a closed-form multivariatenormal orthant integral (Section 3.8); non-negativity is imposed by conditioning on {DX ≥ 0}, with normalizer QX . On that admissible event the two coincide, dX = DX , so the differences written in d equal their latent representation in D. Unless stated otherwise, all primitive Gaussian variables are independent. Correlated temporal quantities can be handled by replacing diagonal covariance matrices with the appropriate joint covariance matrix. Running example. We thread one example through the paper. Let X be an uncertain storm and Y an uncertain power outage, in hours, with X : µX = 2, σX = 0.5, µdX = 4, σdX = 0.5;

Y : µY = 3, σY = 0.6, µdY = 3, σdY = 0.6,

so the storm spans roughly [0, 4] h and the outage roughly [1.5, 4.5] h. A report might say “the power went out during the storm,” but the times are uncertain. We return to this example to read off graded relations and their coarse-predicate and primitive structure (Section 4.1).

3.3

Placing the Uncertainty: Which Quantities Are Known

An interval has two degrees of freedom, so a model is fixed by placing Gaussian uncertainty on two of its temporal quantities and deriving the rest. The natural pair is a temporal anchor together with the duration, and which anchor to choose is dictated by what the source actually pins down. Natural language makes the choice vivid: each of the following utterances constrains a different pair and leaves the complementary quantity uncertain. • Start and duration. “I went there on 11 February and stayed for about two months.” The start is sharp and the duration is vague, so the end is the uncertain quantity; model it with a tight standard deviation on the start and a loose one on the duration. • Midpoint and duration. “I was there for ten days during the summer.” Here the duration is sharp but its position is vague—the ten days sit somewhere in summer—so the uncertainty lives on the midpoint. This is the parameterization used throughout the body. • End and duration. “After a week’s holiday I got home on Wednesday evening.” The end is anchored and the duration is roughly a week, so the start is what floats. All three describe the same kind of object and produce the same Allen machinery: the duration d ≥ 0 is truncated as above, the chosen anchor is Gaussian, the boundaries are affine in the two, and every relation remains a conditional Gaussian orthant probability. They differ only in which two quantities are taken as independent and Gaussian, and hence in the correlation they induce between midpoint and duration—zero for the midpoint pair, +σd2 /2 for start– duration, and −σd2 /2 for end–duration. Appendix C gives the explicit boundary maps, and the accompanying implementation provides dedicated constructors for each interval specification— by start, end, or midpoint together with the duration. The modelling task is therefore only to name the two quantities the data constrains and attach an uncertainty to each; the relation probabilities then follow.

3.4

A Common Linear-Inequality Semantics

The central observation is that all Allen relations are conjunctions of linear boundary inequalities. If boundaries are affine functions of Gaussian variables, each relation R is an event of the form AR U ≤ bR , where U is a Gaussian vector containing time points and latent durations. Folding the right-hand side into the map, we write this system throughout as LR (U ) ≤ 0,

LR (U ) = AR U − bR ,

(7)

and use the LR form from here on. Its coefficient matrix and offset factor as AR = SR M and bR : the interval parameterization enters only through the difference map M , the relation only through the signed selector SR read off its signature (Table 3); Appendix C develops this decomposition. If some duration variables are truncated, relation probabilities are conditional Gaussian orthant probabilities: P LR (U ) ≤ 0, Di ≥ 0 ∀i P (R | Di ≥ 0) = . (8) P(Di ≥ 0 ∀i) This formulation is more general than the closed forms below and is the basis for numerical implementation.

3.5

Relations Between Two Gaussian Points

Let tx ∼ N (µx , σx2 ),

ty ∼ N (µy , σy2 ),

(9)

q σx2 + σy2 ,

(10)

independently. Define ∆ = µy − µx ,

σxy =

2 ). Then so that Z = ty − tx ∼ N (∆, σxy

P (x < y) = P(Z > 0) ∆ =Φ σxy " 1 1 + erf = 2

(11) √

∆ 2σxy

!# =

1 ∆ erfc − √ 2 2σxy

! ,

and P (x > y) = P(Z < 0) ∆ =Φ − σxy " !# 1 ∆ 1 = 1 − erf √ = erfc 2 2 2σxy

(12) √

∆ 2σxy

! .

Exact equality has probability zero for non-degenerate continuous Gaussians.

3.6

Confidence Borders and Graded Membership

Allen relations involving equality, for example meets, starts, finishes, and equals, occupy lower-dimensional subsets of the continuous configuration space. Their exact probabilities are therefore zero unless deterministic boundary atoms are present. For practical reasoning, and especially for vague linguistic categories, exact equality should be replaced by a confidence border or membership function.

With a hard confidence border τ ≥ 0,1 approximate equality is x ≈τ y

⇐⇒

τ −∆ σxy

|ty − tx | ≤ τ.

(13)

Its probability is P (x ≈τ y) = Φ

" 1 = erf 2

−τ − ∆ σxy

−Φ ! τ −∆ √ − erf 2σxy

−τ − ∆ √ 2σxy

(14)

!# .

This equality border should be distinguished from the verbal grading of non-contact relations. A tolerance τ is required for contact relations because exact boundary equality has zero probability in a continuous model. It is not, however, the primary representation of expressions such as shortly before. Those expressions can be modeled by the strength of the coarser precedence predicate relative to overlap and after. A soft alternative is a membership kernel meq (z) ∈ [0, 1], for example Gaussian or logistic, and the graded truth becomes E[meq (ty − tx )]. (15) The hard-border formulas are used below because they remain expressible as Gaussian CDFs over linear inequalities.

3.7

Relations Between a Point and an Interval

Let x be a Gaussian point and Y an uncertain interval. Define Z = tY − t x ,

∆Y x = µY − µx ,

σZ2 = σY2 + σx2 .

(16)

The interval boundaries are aY = tY −dY /2 and bY = tY +dY /2. The point is before the interval iff tx < aY , equivalently Z > dY /2; it is after iff Z < −dY /2; and it is inside iff |Z| ≤ dY /2. For DY ∼ N (µdY , σd2Y ) conditioned on DY ≥ 0, define µdY µd QY = Φ (17) , αY = Y , σdY σdY r 1 σd σpI = σZ2 + σd2Y , ρY = − Y . (18) 4 2σpI Let Φ2 (a, b; ρ) denote the standard bivariate normal CDF with correlation ρ. For a separation margin τ ≥ 0, define pI β+ (τ ) =

Then

∆Y x − τ − 12 µdY , σpI

pI β− (τ ) =

−∆Y x − τ − 21 µdY . σpI

(19)

pI Φ2 (αY , β+ (τ ); ρY ) pI Pbefore (τ ) = P(tx < aY − τ ) = , QY

(20)

pI Φ2 (αY , β− (τ ); ρY ) pI Pafter (τ ) = P(tx > bY + τ ) = . QY

(21)

We use the same tolerance τ for the strict separation margins and for the equality/contact bands. This identity is what makes the thirteen relations a partition whose probabilities sum to one (Proposition 1): each boundary difference v is split into v > τ , |v| ≤ τ , and v < −τ , and these three tile the line without gap or overlap only when the band half-width equals the separation margin. A distinct contact tolerance τeq ̸= τ is admissible but forfeits the partition—a narrower band leaves a gap (total mass < 1), a wider band overlaps (total mass > 1).

The point-in-interval probability is pI pI pI Pinside = 1 − Pbefore (0) − Pafter (0).

(22)

Boundary correspondence uses τ : P(|tx − aY | ≤ τ ),

P(|tx − bY | ≤ τ ),

(23)

which are again bivariate Gaussian CDF differences because tx − aY and tx − bY are affine functions of (Z, DY ).

3.8 Let

Relations Between Two Intervals: Distribution-Induced Allen Algebra dX dX , , tX + X = tX − 2 2

dY dY Y = tY − . , tY + 2 2

(24)

Define Z = tY − t X ,

∆ = µY − µX ,

2 σZ2 = σX + σY2 .

(25)

The four boundary differences are dX − dY , 2 dX − dY B = bY − bX = Z − , 2 dX + dY G = aY − bX = Z − , 2 dX + dY H = aX − bY = −Z − . 2 A = aY − aX = Z +

(26) (27) (28) (29)

Here G is the gap from the end of X to the start of Y , and H is the converse gap. On the admissible event {DX ≥ 0, DY ≥ 0} the durations coincide with their untruncated latents, dX = DX and dY = DY , so the four differences are affine in the latent vector U = (Z, DX , DY )T , which is jointly Gaussian with mean µU = (∆, µdX , µdY ) and, in the independent case, covariance ΣU = diag(σZ2 , σd2X , σd2Y ). The system LR (U ) ≤ 0 of a relation is read directly from Table 2: put each inequality listed there in the form ≤ 0 and expand it through the differences A, B, G, H above. A strict margin such as G > τ contributes a single affine row τ − G ≤ 0; a contact band such as |A| ≤ τ contributes two rows, A−τ ≤ 0 and −A−τ ≤ 0. For overlaps (the row A > τ, B > τ, G < −τ of Table 2),     τ − Z − 21 (DX − DY ) τ −A   Loverlaps (U ) = τ − B  = τ − Z + 21 (DX − DY ) ≤ 0, (30) 1 G+τ Z − 2 (DX + DY ) + τ each row affine in U ; adjoining the truncation rows −DX ≤ 0 and −DY ≤ 0 completes the system LR (U ) = AR U − bR ≤ 0 of Equation (7). The relation’s probability is the Gaussian mass of that region, P(LR (U ) ≤ 0, DX ≥ 0, DY ≥ 0) P (R) = . (31) P(DX ≥ 0)P(DY ≥ 0) The numerator is a multivariate Gaussian CDF, obtained by standardizing the stacked rows by their induced mean AR µU − bR and covariance AR ΣU AT R . Reading a row of Table 2, substituting the differences A, B, G, H, and standardizing is thus the complete recipe that reproduces the concrete closed form of any of the thirteen relations. In one or two active dimensions this CDF is an ordinary error function: before and after reduce to a single tail 21 erfc(·) (Section 3.5) and the point–interval relations to a bivariate Φ2 (Section 3.7); the running example 12

overlaps, whose three rows {τ − A, τ − B, G + τ } ≤ 0 are active, evaluates to the trivariate normal probability Φ3 of those standardized rows. Equation (1), Table 2, Equation (31), and this evaluation are precisely the four steps of the roadmap (Section 3.1). 3.8.1

The Tolerance Partition

A single tolerance τ ≥ 0 governs both the separation margins of the full-dimensional relations and the half-width of the equality/contact bands. Introduce the thresholded sign   +1 v > τ, sgnτ (v) = (32) 0 |v| ≤ τ,   −1 v < −τ. The pair (sgnτ A, sgnτ B) partitions the boundary-difference plane into nine cells; the two diagonal corners are split by sgnτ G and sgnτ H into separation/contact triples. Table 2 lists the thirteen resulting inequality systems. Table 2: The thirteen relations as a single-tolerance partition in boundary differences. Relation

Inequality form

Interpretation

before meets overlaps starts during finishes equals finished by contains started by overlapped by met by after

G>τ A > τ, B > τ, |G| ≤ τ A > τ, B > τ, G < −τ |A| ≤ τ, B > τ A < −τ, B > τ A < −τ, |B| ≤ τ |A| ≤ τ, |B| ≤ τ A > τ, |B| ≤ τ A > τ, B < −τ |A| ≤ τ, B < −τ A < −τ, B < −τ, H < −τ A < −τ, B < −τ, |H| ≤ τ H>τ

X ends before Y starts external contact from X to Y X starts before Y and ends inside Y shared start, X shorter X properly inside Y shared finish, X shorter shared start and finish shared finish, Y shorter Y properly inside X shared start, Y shorter Y starts before X and ends inside X external contact from Y to X X starts after Y ends

Proposition 1 (Tolerance partition). For every τ ≥ 0 and every joint law of the boundaries with aX ≤ bX and aY ≤ bY almost surely, the thirteen relations of Table 2 are pairwise disjoint and cover the sample space. Hence their probabilities sum to one, and as τ → 0+ they converge to the crisp Allen relations, with the seven equality/contact relations having probability zero under continuous boundary distributions. Proof. The maps a = sgnτ A and b = sgnτ B are single-valued and exhaustive, so the nine cells {(a, b)} partition the sample space. The seven cells with (a, b) ∈ / {(+, +), (−, −)} are each labelled by exactly one relation. On the cell (+, +) the single-valued map sgnτ G yields the disjoint cover {overlaps, meets, before}; symmetrically sgnτ H splits (−, −) into {overlapped by, met by, after}. A disjoint cover of each cell of a partition is again a partition, so the thirteen relations partition the space. The limiting claim follows because each band | · | ≤ τ shrinks to a measure-zero hyperplane as τ → 0. A single tolerance is a requirement, not a convenience: the equality bands tile with the strict regions only when the band half-width equals the separation margin. Two independent tolerances reopen gaps or overlaps and break the partition. We verify numerically that the analytic probabilities sum to one within Monte-Carlo precision for every τ (Section 4). 13

3.9

Taxonomy as Probability Calculus

A central claim of this paper is that Allen relations should not be treated as independent flat classes. They are leaves of a relation taxonomy. Let L be the set of Allen leaf predicates. For any coarse predicate C defined as a union of leaves, [ C= R, (33) R∈LC

and for disjoint leaves, P (C) =

P (R).

(34)

R∈LC

This is not merely a post-processing convention; it follows from the fact that all relations are regions of the same probability space. For example, precedence with contact is P (X ⪯ Y ) = P (before) + P (meets).

(35)

P (X ⊆ Y ) = P (starts) + P (during) + P (finishes) + P (equals).

(36)

Containment of X in Y is

Reverse containment is P (X ⊇ Y ) = P (started by) + P (contains) + P (finished by) + P (equals).

(37)

Partial overlap is P (partial overlap) = P (overlaps) + P (overlapped by).

(38)

External adjacency is P (outer contact) = P (meets) + P (met by),

(39)

and inner adjacency is P (inner contact) = P (starts) + P (started by) + P (finishes) + P (finished by) + P (equals).

(40)

This enables top-down refinement. For instance, P (meets) , P (before) + P (meets)

(41)

P (starts) . P (starts) + P (during) + P (finishes) + P (equals)

(42)

P (meets | X ⪯ Y ) = and P (starts | X ⊆ Y ) =

A flat classifier over thirteen labels cannot express these inheritance relations unless the taxonomy is added externally.

relation between X and Y separated / externally touching X precedes / touches Y before meets X follows / touched by Y met by after non-separated partial overlap overlaps overlapped by X ⊂ Y (strict) starts during finishes X ⊃ Y (strict) started by contains finished by equals

Figure 4: Relation taxonomy as a strict partition tree. Each leaf shows the relation with the reference interval Y (outlined) held fixed and the event X (filled) placed accordingly— dotted ticks mark Y ’s edges, so the leaves are directly comparable (compare the crisp boundary orderings of Table 1). The children of every node are mutually exclusive and exhaustive, so each node’s probability is the sum of its children’s. equals is its own cell rather than being shared by the two containment directions; the non-strict views X ⊆ Y and X ⊇ Y (each of which also includes equals) are overlapping coarse predicates, not nodes of this tree.

3.10

Temporal Primitives and the (De)composition of Relations

The thirteen relations are not atomic. Each is a conjunction of elementary assertions about the order of two interval boundaries. With X = [aX , bX ] and Y = [aY , bY ], the within-interval orders aX < bX and aY < bY are fixed, so a relation can only constrain the cross comparisons of one interval’s boundaries against the other’s. We call these comparisons temporal primitives. They are a general logical foundation for interval relations: the relation algebra is generated by the order type of the boundaries, and every relation is recovered as a conjunction of primitive orderings. The CIDOC CRM ontology adopts exactly this stance, replacing Allen relations by temporal primitives such as “starts before the start of” so that statements stay individually attestable and amenable to reasoning [10]; for instance overlaps is recorded as aX ≺ aY , bX ≻ aY , and bX ≺ bY . Our partition realizes the same foundation in metric, probabilistic form. The four primitives are precisely the thresholded signs of the boundary differences A, B, G, H of Section 3.8, sgnτ A,

sgnτ B,

sgnτ G,

sgnτ H,

(43)

comparing startX /startY , endX /endY , endX /startY , and endY /startX respectively. Each is three-valued : the strict states ±1 are CRM’s qualitative “before”/“after”, while the middle state 0 (the band | · | ≤ τ ) is the metric predicate “the two boundaries coincide within τ ” — the graded notion of contact that crisp primitives cannot express. Composition is then read directly off the partition. Table 3 lists the primitive signature (sgnτ A, sgnτ B, sgnτ G, sgnτ H) of every relation. The contact relations are exactly those with a coincident primitive. As a worked example, meets has signature (+, +, 0, −), meets ⇐⇒ aX ≺ aY ∧ bX ≺ bY ∧ bX ≈τ aY ,

(44)

where ≈τ denotes coincidence within τ . It shares the primitives A, B, H with before and overlaps and differs from them only in sgnτ G, which runs through +, 0, −; thus meets is before with its single discriminating primitive flipped from strict precedence to contact — not the conjunction of before with a contact predicate, which would be contradictory. Table 3: Primitive signature (sgnτ A, sgnτ B, sgnτ G, sgnτ H) of each relation and its number of coincident primitives c. Strict relations have c = 0; the six touching/aligning relations c = 1; equals has c = 2. Relation

before meets overlaps starts during finishes equals finished by contains started by overlapped by met by after

+ + + 0 − − 0 + + 0 − − −

+ + + + + 0 0 0 − − − − −

+ 0 − − − − − − − − − − −

− − − − − − − − − − − 0 +

0 1 0 1 0 1 2 1 0 1 0 1 0

Read as inequalities, each signature is the relation’s selector SR —a matrix with entries in {−1, 0, +1} acting on (A, B, G, H)T (Appendix C): a strict sign σv contributes the row −σv v ≤ 16

−τ and a coincidence σv = 0 the pair ±v ≤ τ . For the six strict relations SR = − diag(σR ); the contact relations add a ± row per coincident primitive. Each relation’s linear inequality system is thus read directly off this table. The coincident-primitive count characterizes equality and contact exactly. Proposition 2 (Equality and contact as coincident primitives). Let c(R) = #{v ∈ {A, B, G, H} : sgnτ v = 0} be the number of coincident primitives of a relation R. Then c equals the codimension of R’s defining set in boundary-difference space: the six relations {before, overlaps, during, contains, overlapped by, after} have c = 0; the six touching/aligning relations {meets, starts, finishes, finished by, started by, met by} have c = 1; and equals has c = 2. Consequently R retains positive probability under every continuous boundary law in the crisp limit τ → 0+ if and only if c(R) = 0; the seven relations with c ≥ 1 are precisely the equality/contact relations of Proposition 1, whose mass is carried entirely by bands of width O(τ ). Proof. From Table 2, the coincidence state sgnτ =0 occurs for A on {starts, equals, started by}, for B on {finishes, equals, finished by}, for G on {meets}, and for H on {met by}. Collecting by relation gives c = 2 for equals, c = 1 for the other six listed, and c = 0 for the remaining six, which is the stated trichotomy. Each coincident primitive constrains its difference to the band |v| ≤ τ , whose τ → 0 limit is the hyperplane {v = 0} of codimension one; the coincident primitives of each relation are linearly independent (for equals, A and B span two dimensions; the others impose a single constraint), so c of them cut out a set of codimension c. A set of positive codimension is Lebesgue-null and carries zero probability under any continuous law, giving the equivalence; for τ > 0 each band has width 2τ in its difference coordinate, so the contact mass is O(τ ). This factorization holds for the whole algebra at once. Proposition 3 (Primitive factorization). Let Φ(U ) = (sgnτ A, sgnτ B, sgnτ G, sgnτ H) with U = (Z, DX , DY )T . On the feasible cone {DX , DY ≥ 0} each relation is a primitive fiber, {R} = Φ−1 (σR ), where σR is the signature of Table 3. Hence every relation probability is the joint law of the four primitives at a single atom, T v = σ (v)} D , D ≥ 0 , (45) {sgn P (R) = P R X Y τ v∈{A,B,G,H} a single multivariate-Gaussian band–orthant integral; and the marginal of each primitive is the P coarse predicate P (sgnτ v = s) = R: σR (v)=s P (R), a one-dimensional Gaussian tail or band. Since the four differences span only three dimensions (H = G − A − B), the joint of (45) is not the product of these marginals. Finally, the decomposition has two probabilistic levels. Marginally, each primitive is a proper three-way distribution—its states partition the corresponding axis—and its probabilities are sums of leaf probabilities, i.e. coarse predicates of the taxonomy (Section 3.9). The start/start primitive, for example, induces the coarsening P (sgnτ A = +) = P (before) + P (meets) + P (overlaps) + P (finished by) + P (contains), P (sgnτ A = 0) = P (starts) + P (equals) + P (started by), P (sgnτ A = −) = P (during) + P (finishes) + P (overlapped by) + P (met by) + P (after), (46) whose middle cluster is precisely “shared start”; the four primitives are thus four three-way coarsenings of the leaf set, dual to the taxonomy’s nodes. A relation, by contrast, is the joint law of its primitives. Because all four differences are linear in the shared latent U = (Z, DX , DY ) (indeed H = G − A − B), the primitives are strongly correlated and a relation is never the product of its primitive marginals: the gap primitive alone entails the leading-edge orders, since 17

G > τ ⇒ A, B > τ and hence P (before) = P (sgnτ G = +), whereas at a shared midpoint A ≈ −B precludes both from being large. The derivation, with the one-dimensional closed forms for the primitive marginals, is given in Appendix D. This is what the probabilistic lift adds to the CRM foundation: each primitive remains an independently attestable, now graded, statement, while a single covariance over U supplies the dependence needed to compose them into coherent relation probabilities. On the running example this localization is striking: the entire thirteen-way distribution reduces to uncertainty in a single primitive (Section 4.1).

3.11

Consistency of Limiting Cases

The taxonomy makes boundary limits semantically stable. Consider the gap g = a Y − bX .

(47)

In crisp Allen algebra, g > 0 gives before and g = 0 gives meets. A flat model treats this as a class switch. In the taxonomy, both are children of the coarser predicate X ⪯ Y , and by the partition of Section 3.8.1 this parent probability is their sum, P (X ⪯ Y ) = P (before) + P (meets),

(48)

which is stable even though the leaf mass migrates between before (the region g > τ ) and meets (the band |g| ≤ τ ) as the tolerance or the expected gap varies. As the expected gap approaches zero, probability mass moves from strict before to approximate meets, while the parent probability remains well-defined. Analogously, during can approach starts or finishes as one boundary aligns with the container, while containment remains stable: P (X ⊆ Y ) = P (starts) + P (during) + P (finishes) + P (equals).

(49)

This is a key robustness advantage over flat multiclass relation assignment.

Validation

The accompanying open-source implementation computes the multivariate Gaussian orthant probabilities and, independently, a Monte-Carlo estimate that samples boundaries and classifies each draw by Table 2. All claims below are reproduced by that package. Partition. The thirteen probabilities sum to one for every tolerance τ , confirming Proposition 1; the Monte-Carlo classifier assigns every sample to exactly one relation. By contrast, a naive one-sided contact band (assigning meets to 0 ≤ G ≤ τ rather than |G| ≤ τ ) loses several percent of the probability mass into uncovered buffer zones. Agreement. The analytic probabilities match the Monte-Carlo frequencies to within sampling noise across all thirteen relations: the maximum absolute deviation is about 2 × 10−4 at 4 × 106 samples. Graded transitions and limits. As one interval slides past the other, probability mass transfers smoothly between relations (Figure 5). As a duration shrinks to zero, the thirteen relations reduce continuously to the five point–interval relations {before, starts, during, finishes, after} (Figure 6), and to {before, equals, after} for two points, with the partition preserved at every step. Scale invariance. Scaling all means, durations, standard deviations, and the tolerance by a common factor leaves every relation probability unchanged, as the standardized arguments are invariant. 18

Relation probabilities vs. separation (τ = 0.3)

relation probability

before

during

overlaps

overlapped_by

after

1.00 0.75 0.50 0.25 0.00

−8

−6 before meets

−4

−2 0 2 relative position (μe − μr) overlaps starts

during finishes

overlapped_by met_by

after sum (=1)

Figure 5: Relation probabilities as one interval slides across the other. Mass transfers smoothly through the relations while the curves sum to one everywhere.

4.1

A Worked Example

We collect the threads on the running storm/outage example of Section 3.2. Figure 7 shows the two uncertain intervals and the resulting relation probabilities at τ = 0.4 h. Graded relations. A crisp classifier sees only the mode, overlaps (P ≈ 0.52): the storm starts first and the outage runs past its end. But the distribution is broad—finished by (0.27), contains (0.10), started by and equals (a few percent each)—so the single label discards most of the picture. Taxonomy. The coarse predicates make the real question legible: the outage spilling past the storm and the outage being contained within it are almost equally likely, P (partial overlap) ≈ 0.53 against P (Y ⊆ X) ≈ 0.44, while precedence is negligible (≈ 0.01). Neither coarse probability is a separate bar in Figure 7; each is the sum of its leaves there, following the taxonomy rule that a parent’s probability is the total of its children’s. Containment is the sum of its four leaves, P (Y ⊆ X) = P (finished by) + P (contains) + P (started by) + P (equals) ≈ 0.27 + 0.10 + 0.04 + 0.03 ≈ 0.44, and partial overlap is P (overlaps) + P (overlapped by). The graded model reports this neareven split; a flat overlaps label cannot. Primitive localization. The relational uncertainty collapses onto a single temporal primitive. The storm almost surely starts first, P (sgnτ A = +) ≈ 0.90 (“the outage began after the storm started”), and the two certainly overlap: sgnτ G and sgnτ H are determinate—each concentrated on a single sign with probability ≈ 1—since the outage almost surely begins before 19

Interval → point: 13 relations reduce to 5 (bold solid); the other 8 vanish (faint dotted) μde = 3

μde = 1

μde = 2

μde = 0

relation probability

1.00 0.75 0.50 0.25 0.00

3.0

2.5 2.0 1.5 1.0 0.5 event duration μd (e shrinks to a point → 0)

0.0

before meets overlaps

starts during finishes

equals finished_by

started_by overlapped_by

met_by after

Figure 6: Interval-to-point limit: as the event duration µde → 0 (right edge), the thirteen interval–interval relations reduce continuously to the five point–interval relations {before, starts, during, finishes, after} (bold solid); the others lose their mass and vanish (faint dotted). The top panels show the constellation at four durations: the event e (filled, with faint copies for its positional uncertainty) shrinks against the fixed reference r (outlined) down to a point, offset from r’s midpoint so the starts/finishes and before/after curves separate. The thirteen probabilities sum to one throughout. the storm ends (sgnτ G = −) and the storm before the outage ends (sgnτ H = −), so neither a leading nor a trailing gap can open. What is undecided is whether the storm ends before, together with, or after the outage—primitive B—with probabilities ≈ 0.55, 0.30, 0.15. The thirteen-way uncertainty is, at heart, one attestable boundary comparison. Limits and scale. If the outage is reported as an instant rather than an interval (duration → 0), the relations reduce to the point–interval set, now dominated by contains (≈ 0.77)—the blackout instant falling within the storm. Expressing the same scenario in minutes rather than hours (scaling means, durations, spreads, and τ by 60) leaves every probability unchanged to 2 × 10−5 . Language. The report’s “during the storm” is, quantitatively, a roughly even mixture of containment and trailing overlap; a sharper adverbial such as “well into the storm” would concentrate sgnτ A = + and shift mass from starts and equals toward during and contains. The algebra turns vague temporal language into a distribution over boundary orderings.

Discussion, Conclusions, and Applications

5.1

Comparison to Allen’s Hourglass

Allen’s Hourglass and the present model share a motivation: crisp Allen relations are brittle under uncertain interval boundaries [30]. The hourglass representation organizes relations by relative position and relative size, thereby producing a robust graded treatment of relation assignment. It also makes limiting cases such as durationless intervals geometrically visible.

Uncertain intervals: mean span (bar) and ±1σ endpoints (whiskers) storm X outage Y

−1

2 time (h)

Relation probabilities (τ = 0.4 h); crisp label = overlaps probability

0.5 0.4 0.3 0.2 0.1 afte r

met _by

y ove rlap ped _by

star ted _b

co n tain s

finis hed _b

equ als

finis hes

dur ing

star ts

ove rlap s

mee ts

befo

0.0

Figure 7: Running example. Top: the uncertain storm X and power outage Y (mean span as a bar, ±1σ boundary uncertainty as whiskers). Bottom: the thirteen relation probabilities at τ = 0.4 h; the crisp mode overlaps (black) accounts for only about half the mass. The present approach differs in three respects. First, it gives a generative semantics: relation probabilities are induced by probability distributions over time points, midpoints, and durations. Second, equality and contact are handled explicitly through confidence borders, avoiding the zero-measure problem of exact boundary equalities in continuous spaces. Third, it preserves the relation taxonomy as probability calculus rather than treating the thirteen Allen labels as independent classes. Thus, Allen’s Hourglass can be seen as a conceptual geometry of robust relation assignment, while the present model provides a distributional semantics and analytic computation of relation probabilities. The two approaches are complementary: the hourglass is valuable for visualization and intuition; the Gaussian inequality formulation is valuable for inference, limiting cases, and integration with metric uncertainty.

5.2

The Relation Phase Diagram, Taxonomy, and Dimensional Reduction

The hourglass is usefully read as a phase diagram over relation classes: a stratification of configuration space by the codimension of the defining equalities. The six relations defined by strict inequalities are full-dimensional “bulk phases”; the six contact relations are codimensionone “phase boundaries”; and equals, defined by two equalities, is a codimension-two multiphase point. Our contribution is to place a generative measure on this geometry: a relation probability is the mass that the boundary density assigns to a phase, the tolerance τ is the finite width of the coexistence bands, and (as future work) the gradients of relation probabilities are response functions peaked at the boundaries. Computing the most probable relation over this plane reproduces the hourglass geometry directly from the generative model (Figure 8, left), beside the dimensional reduction discussed below (right). The correspondence is exact in our coordinates. With Z = tY − tX , the start and finish

Most-probable relation over the hourglass plane

Dimensional reduction interval–interval

relative size ŝ = (dX − dY)/(dX + dY)

0.75

13 relations

0.50 dX

0.25

before meets overlaps starts during finishes equals

0.00

−0.25

finished_by contains started_by overlapped_by met_by after

5: before, starts, during, finishes, after dY

→0

point–point

−0.50

3: before, equals, after

−0.75 −6

→0

point–interval

−4

−2 0 2 relative position μX − μY

Figure 8: Left: the most probable relation over the hourglass plane of relative position and relative size, reproducing the hourglass geometry from the generative model. Right: the 13 → 5 → 3 reduction as intervals collapse to points. comparisons satisfy A + B = 2Z,

A − B = dX − dY ,

(50)

so the (A, B) plane is the hourglass plane of relative position and relative size, rotated by 45◦ . The gaps carry the duration sum, G = Z − 12 (dX + dY ) and H = −Z − 21 (dX + dY ), which the two hourglass axes suppress; this third coordinate reappears as the hourglass’s characteristic waist, and it is precisely what carries the contact relations meets, met by that the hourglass cannot represent. Hourglass position is thus our relative mean occurrence time and hourglass size our duration contrast, but as relative, normalized combinations rather than the per-object means. The taxonomy is the invariant of the reduction to lower-dimensional objects. As a duration shrinks to zero the latent space loses a dimension and leaves collapse, but the coarse predicates survive: object pair

surviving relations

count

interval–interval point–interval point–point

all before, starts, during, finishes, after before, equals, after

13 5 3

The collapse is continuous and the partition is preserved in every limit (Figure 6). Equivalently, the taxonomy is a hierarchical coarse-graining of the relation phase diagram, and the intervalto-point reductions conserve probability within each taxonomic parent while redistributing it among its leaves. This is exact. Proposition 4 (Taxonomy invariance under reduction). Let X, Y be uncertain intervals under the single-tolerance partition of Table 2, and let dX → 0 in distribution, so X degenerates to the Gaussian point tX . Then (i) the thirteen-relation partition converges to the five-relation point–interval partition {before, starts, during, finishes, after}, and the remaining eight relations carry probability → 0; (ii) every coarse predicate C that is a node of the taxonomy tree (Figure 4) has P (C) continuous at the limit; and 22

(iii) the limit reallocates probability only among the leaves of a common parent—no mass crosses between distinct coarse nodes. A second collapse dY → 0 reduces the five to {before, equals, after} by the same statement. The taxonomy tree, not the leaf catalogue, is the invariant of the reduction. Proof. At dX = 0 the point boundaries coincide, aX = bX = tX , so two of the four boundary differences of Section 3.8 become dependent: A = G and H = −B, with B − A = dY ≥ 0. Each of the eight relations outside {before, starts, during, finishes, after} combines these identities into a contradiction under the thresholded signs—meets needs A > τ with |G| ≤ τ and G = A; contains needs A > τ, B < −τ against A ≤ B—so its region is empty on {dX = 0} and, for dX > 0, a sliver of vanishing measure; hence its probability → 0, giving (i) (the full sign bookkeeping is Appendix B). Each surviving region converges to its point–interval cell in the S coordinates (A, B) = (aY − tX , bY − tX ). For (ii), a taxonomy node C = R∈LC R has indicator 1C that converges pointwise almost everywhere and is bounded by 1, so P (C) → P (C | dX =0) by dominated convergence. For (iii), the leaf boundaries interior to a parent are the bands |A| ≤ τ and |B| ≤ τ ; as dX → 0 they shift and a vanishing leaf’s mass passes to its siblings— equals empties into during, starts, finishes as the point falls inside Y —but the union defining the parent is unchanged, so no mass leaves the parent.

5.3

NLP: Relation Families, Verbal Grading, and Contact

For NLP it is useful to separate three dimensions that are often conflated. The first is the qualitative relation family, for example precedence, overlap, containment, or succession. The second is the strength of evidence for that family, represented by its probability relative to alternatives at the same taxonomic level. The third is boundary contact, such as meets, starts, finishes, or equals, which requires equality margins in continuous models. Let the top-level alternatives be the three coarse families of Section 3.9, each a union of leaves, T = {before, overlap, after}, (51) where before = {before, meets}, after = {met by, after} are its converse, and overlap collects the remaining nine (non-separated) leaves. Their probabilities are the corresponding leaf sums (Equation (34)) and therefore partition the unit mass, pb + po + pa = 1, with pb = P (before),

po = P (overlap),

pa = P (after).

(52)

A before-type expression is licensed when pb > max(po , pa ),

(53)

while the verbal modifier can be tied to the strength of this dominance, which we measure by the margin δ = pb − max(po , pa ) ∈ (0, 1] (54) by which the before family leads its closest competitor. The adverbials at issue here are precisely the graded temporal-relation expressions of Section 1.1: phrases such as just before, shortly before, rather before, some time before, and long before all place one event before another and differ only in how far before. They therefore need not denote different Allen leaves. They can denote different grades of the same before relation family. A weak but dominant value of pb supports shortly before; a near-certain value of pb supports long before. This makes shortly before distinct from meets: meets is a contact relation, while shortly before is a verbal grading of precedence. Spatial language has the same structure: just above, far to the left of, and right beside grade qualitative spatial relations by the same mechanism, so the construction here transfers directly to a spatial Allen-style algebra (Section 5.10). 23

One possible schematic mapping places three ordered thresholds 0 < θ1 < θ2 < θ3 < 1 on the margin δ: 0 < δ ≤ θ1 θ1 < δ ≤ θ 2 θ2 < δ ≤ θ 3 θ3 < δ ≤ 1

⇒ ⇒ ⇒ ⇒

“just / shortly before” “rather before” “some time before” “long before”

(weakly dominant), (moderately dominant), (strongly dominant), (near-total dominance).

(55)

Here “moderately” and “strongly dominant” are simply the middle bands θ1 < δ ≤ θ2 and θ2 < δ ≤ θ3 ; a representative calibration is (θ1 , θ2 , θ3 ) = (0.2, 0.5, 0.8), and δ → 1 exactly as pb → 1. The thresholds are not universal lexical constants. They may depend on language, genre, and task. The important point is that the algebra supplies a normalized graded variable that can be calibrated empirically. Adjacency-dependent relations behave differently. For meets, met by, starts, started by, finishes, finished by, and equals, the relevant probability depends directly on a tolerance or soft boundary kernel: P (meetsτ ) = P (|aY − bX | ≤ τ, aX < aY , bX < bY ),

(56)

P (startsτ ) = P (|aY − aX | ≤ τ, bX < bY ).

(57)

Thus contact words such as touches, starts with, ends with, or at the same time are marginsensitive, whereas non-contact verbal gradings are primarily relation-probability-sensitive. The same framework supports both, but it keeps their semantics separate. This distinction gives a bidirectional NLP interface. In interpretation, linguistic evidence can be translated into constraints or likelihood terms over relation probabilities and boundary margins. In generation, a system can choose the relation family by the most probable taxonomic predicate and choose the verbal modifier by the strength of that probability, while reserving contact expressions for high margin-dependent contact probability. A fourth cue is structural rather than gradable: an utterance usually reveals which temporal quantities the speaker has fixed, and hence how its interval should be parameterized (Section 3.3). “I arrived on the 11th and stayed about two months” anchors a start and leaves the end uncertain; “ten days during the summer” fixes a duration and leaves its position uncertain; “a week’s holiday, home by Wednesday evening” anchors an end. The same sentence therefore supplies both the relation-level evidence above and the boundary-level uncertainty beneath it—which anchor is sharp, which quantity floats—and the framework consumes both through the same Gaussian parameters.

5.4

From Discrete Cuts to Graded Membership

The mapping (55) is a hard partition—each δ yields one adverbial—which human usage overruns: asked which word fits a configuration, speakers spread across adjacent adverbials (just and recently both fit a recent event, the balance tipping smoothly as it recedes). This is a graded variability a hard partition cannot express, since fit to the measured responses it collapses each configuration onto a single winner. The remedy, confirmed on the human data of the companion paper [15], is a soft read-out: one smooth membership kernel per adverbial over the margin, Aa (δ) ∈ [0, 1], overlapping its neighbours, so that a configuration yields a distribution P (a | δ) ∝ Aa (δ) over the competing adverbials, with (55) recovered only as the kernel width vanishes—smooth bells on the (log-)margin, a skew-normal per adverbial, reproduce the measured usage closely where the cuts fail. An embodied or conversational agent closes the loop from this distribution, emitting a single word either as the mode argmaxa P (a | δ), the canonical choice, or by sampling a ∼ P (a | δ) to reproduce natural variability; and the same kernels run backward, a heard adverbial contributing the likelihood Aa (δ) for the inverse map to concrete times. 24

Expressed adverbial: observed usage and the soft skew-normal read-out (event: own year abroad) 4d

4 mo

match

lon g

n/a

en tly

som e

n/a

jus t

rec

lon g

som e

en tly

jus t

rec

lon g

som e

en tly

jus t

rec

lon g

som e

en tly

jus t

n/a

rec

n/a

lon g

en tly

jus t

rec

1.0

som e

0.5 0.0

match

0.5 lon g

som e

jus t

en tly rec

lon g

som e

en tly

jus t

rec

lon g

som e

en tly

jus t

rec

lon g

som e

en tly

jus t

lon g

rec

en tly

0.0 jus t

soft skew-normal (fit to votes)

1 mo

som e

observed vote share

1.0

Figure 9: Graded recency adverbials that persons use to describe the recency of something that happens after a single event—e.g. a person asked at a given time period after a year abroad —as the time period recedes from a few days into the past (left) to several years ago (right). Top: which word people actually reach for, shown as the share of speakers preferring each one; the preference slides smoothly from just through recently and some time ago to long time ago as the event ages (gaps mark distances at which a word was not offered). Bottom: the soft readout—one skew-normal membership curve per word over the beforeness margin—reproducing that sliding preference, its mode matching the observed word at every distance. An illustrative example; the companion paper [15] reports the full data and quantitative evaluation. This soft read-out is not merely a repair of the hard cuts: it can be estimated directly from how people speak, and a companion paper [15] confirms it on a human corpus of graded recency judgements spanning the before-family adverbials just, recently, some time ago, and long time ago. Each adverbial is given one smooth membership kernel over the margin—a skew-normal, a Gaussian allowed to fall off at different rates on its two sides, since adverbial preference is asymmetric (just drops sharply toward the very recent yet fades slowly as an event recedes toward recently). Fit to the data these kernels reproduce the measured usage closely, picking the expressed word at a macro-F1 of 0.84, where the one-hot cuts of Equation (55) cannot express the graded spread at all. With soft margins we can thus model the variability of adverbial expression accurately, and a human corpus of graded temporal adverbials confirms it. Figure 9 is one illustrative event: as the distance grows the expressed word walks just→recently→some→long, and the fitted read-out tracks that walk. The companion paper [15] develops the estimation, metrics, and kernel comparison in full.

5.5

Scale Invariance and Context-Sensitivity Normalization

A desirable property of the distribution-induced formulation is scale invariance. Suppose all metric temporal quantities are scaled by a positive constant c > 0: t′ = ct,

d′ = cd,

µ′ = cµ,

σ ′ = cσ,

τ ′ = cτ.

(58)

Then all standardized Gaussian arguments used in the relation probabilities remain unchanged. For the point–point before relation,   µy − µ x  P (x < y) = Φ  q , (59) σx2 + σy2 25

and after scaling, µy − µ x c(µy − µx ) q =q . c2 σx2 + c2 σy2 σx2 + σy2

(60)

The same cancellation holds for interval relations. For example, the thresholded separation term (µY − µX ) − τ − 12 (µdX + µdY ) β+ (τ ) = q (61) 2 + σ 2 + 1 (σ 2 + σ 2 ) σX Y dY 4 dX is invariant under simultaneous scaling of means, durations, standard deviations, and thresholds. The correlation matrices are invariant as well, because their entries are ratios of standard deviations. This provides a principled normalization of context-sensitivity. A one-month gap before a two-month interval and a one-hour gap before a two-hour interval should receive the same graded beforeness if the uncertainty and duration parameters scale in the same way. The model therefore does not require a fixed absolute meaning for shortly or long. Instead, verbal grading can be grounded in dimensionless relation probabilities, while domain- or discourse-specific scales enter through the distributions and tolerances themselves. The property is not meant to remove all context. Language still depends on event type, discourse goals, and pragmatic expectations. Rather, the algebra separates two sources of context-sensitivity. Metric scale is normalized by standardized probability calculations; lexical and pragmatic variation can then be learned as mappings from relation probabilities, expected gaps, and task context to verbal expressions.

5.6

Where the Reference Scale Comes From: Extents, Spreads, and the Point Limit

Scale invariance (Section 5.5) holds because every argument of a relation probability is a standardized ratio. Grading a relation into verbal degrees—shortly versus long before, well inside versus dead centre—likewise requires a dimensionless margin, and it is worth making explicit which quantity supplies the yardstick, because the answer differs across relation families and changes under the interval→point limits of Appendix B. Two yardsticks arise. Separation is measured against the spread. For the precedence and succession families the graded quantity is the gap between the two objects, standardized by the combined uncertainty. In the point–interval case (Section 3.7) the standardized separation at zero margin is ∆Y x − 12 µdY expected gap β= = , (62) σpI combined spread and the dominance margin δ of Section 5.3 reads this ratio through a saturating link (δ = 2Φ(β) − 1 for two points). The yardstick is the spread σ; no interval extent is involved. Containment is measured against an extent. For the containment and overlap families the natural graded quantities are ratios of a boundary offset to a duration: κ=

dX ∈ [0, 1] dY

(coverage),

γ=

2 (tX − tY ) ∈ [−1, 1] dY

(centrality),

(63)

together with the insideness margins (aX −aY )/dY and (bY −bX )/dY . These are ratios of times, hence dimensionless, and—unlike the separation gap—bounded : throughout demands κ → 1, in the middle of demands γ → 0, well inside demands large insideness margins. The yardstick is the container’s own extent dY , already present in the configuration. 26

The point limit selects the yardstick. Which yardstick survives is decided by what degenerates. Sending the contained object to a point (dX → 0) sends coverage κ → 0—a point covers nothing—so the throughout family collapses. But centrality γ and the insideness margins depend on the container ’s extent dY , not the point’s, and survive intact: a point inside an interval still has a well-defined, bounded, scale-free position within it, because the interval supplies the yardstick. Sending both objects to points removes every extent at once, leaving only the spread σ. The principle, and the one configuration that is not self-scaling. A graded relation carries an intrinsic margin normalized by a quantity the configuration already contains: an interval extent for the containment and position gradings, present whenever the container is not a point; the joint spread for the separation gradings, present always. The separation margin δ is thus always scale-free—but it saturates (δ → 1 for well-separated objects), so resolving fine degrees in the far tail—long versus very long before—needs a metric distance scale beyond the probability. When an interval extent survives it supplies one intrinsically: a longer event sets a longer scale, as expected—shortly after a decade-long war spans years, shortly after a brief meeting only minutes. Between two bare points—a past event and the utterance instant—no extent remains to play this role, and the metric scale must come from outside the geometry, from the event type, and enters on a logarithmic (ratio) axis, in keeping with the Weber–Fechner character of human time perception [17, 41]. This is the single configuration in which grading is not intrinsically scale-free—the fully collapsed, saturated separation of two points—and it is exactly where a factorized, event-type-conditioned account of temporal distance must locate a per-event characteristic timescale [26]: the scale a point event lacks by geometry, restored by its kind. Everywhere an interval extent survives, no external scale is needed. Why that imported scale is logarithmic—and why the sigmoid is not already it. The logarithm acts only on this residual magnitude, never on the relation itself. Which relation holds is fixed by the signs of the boundary differences, and the orthant probabilities that decide it require those differences to be Gaussian in linear time—a logarithm is not even defined across a sign change. Only once a relation is settled does a positive magnitude remain to be graded, and the scale on which it is read is then free. One might expect the saturating link to supply the compression already: with p = Φ(∆/σ) the before-probability, δ = 2p − 1 does flatten large separations. But it flattens with a Gaussian tail, not logarithmically. Measuring resolution as the change in p per ratio of distance, dp/d ln ∆ = (∆/σ) ϕ(∆/σ), the linear-time law vanishes super-exponentially in the far tail: configurations of very different magnitude—long versus very long before—collapse onto p ≈ 1 and become mutually indistinguishable. A logarithmic argument, p = Φ(ln(∆/t0 )/s) (with the dimensionless log-width s), instead spreads resolution 1 s ϕ(ln(∆/t0 )/s) evenly across decades. The saturating sigmoid is thus a compression but the wrong one; scale-free grading of the far tail requires the logarithm—precisely the external ratio scale the collapsed point pair must import, and the one on which human elapsed-time judgement runs [17, 41].

5.7

From Geometry to a Testable Hypothesis

The yardsticks of Section 5.6 are derived : the algebra fixes which quantity normalizes each family’s margin. Whether human grading actually uses them is an empirical question, and because the geometry is sharp so are the predictions. We state them as a falsifiable hypothesis— identifying where the two extents combine, where an extent is present yet contributes nothing, and where a further, non-geometric factor must enter.

Two extents, and the sign the relation fixes. When both objects are extended, both extents feed the scale, and the relation family decides how. A separation grades the gap, which carries the duration sum G = Z − 12 (dX + dY ): lengthening either object closes the gap alike, so the two extents enter with the same sign. A containment is graded against the container’s extent alone, through the coverage κ = dX /dY : enlarging the container dY supports the relation while enlarging the contained dX opposes it, so the extents enter with opposite signs. The prediction is a measurable sign structure—summed extents for separation, container-minus-contained for containment—keyed to the relation and visible wherever the two extents are varied independently. Present but inert: the pinning of the boundary. An extent contributes only when the relation turns on the boundary that extent moves, and which boundary that is depends on how the object is pinned (Section 3.3). A point behind an end -pinned interval grades on the gap to the pinned end, and the interval’s duration—extending backward from that end—never enters it; a point before a start-pinned interval is the mirror case. The extent becomes active only when the relation turns on the unpinned, duration-carried edge, as for a point after a start-pinned interval. The prediction—duration inert in the pinned-edge configuration, active in the unpinned one—is borne out by companion analysis of the FuzzyLLI corpus [26]: elapsedtime judgements of past events pin the recent edge, and the event’s duration leaves graded pastness unchanged, whereas re-pinning the onset makes the same duration matter. Pinning these parameters to their known physical values rather than fitting them is enough: on the spatial companion corpus, fixing the boundary to the given geometry and freeing only the positional uncertainty still recovers the human proximity judgements (R2 ≈ 0.97, matching the free fit), so the edge-shift prediction holds in the operational regime an agent actually faces [15]. Where geometry supplies no scale: a role for salience. Between two bare points no extent survives (Section 5.6) and the scale must be imported from the event kind, on a logarithmic axis. We add a tentative refinement: what the kind supplies is better read as the event’s salience than its physical extent. In the same companion analysis the fitted per-event timescale is predicted by rated importance, frequency, and richness rather than by duration—a brief but consequential event stays “recent” as long as a protracted one. An extent may therefore feed the imported scale (longer events are often more salient) without setting it. The working hypothesis is thus that the grading scale is a relation-dependent combination of the surviving extents, modulated by salience, collapsing to a purely salience- and kind-set scale in the fully degenerate point pair. A clean test. Separating these claims needs objects of independently varied extent in both separation and containment relations—two disks of variable radius in a spatial judgement, say, where near should grade the gap against the summed radii while inside or around should grade against the container radius alone, and where matching salience across sizes isolates the geometric contribution. The algebra fixes the geometric skeleton of these predictions; behavioural data must supply the salience weighting and settle the degenerate cases.

5.8

Robustness and Inadequacy of Flat Relation Assignment

The inadequacy of flat relation assignment is not merely numerical. It is structural. If a model predicts thirteen independent relation scores, it does not know that meets is a specialization of precedence/contact, or that starts is a specialization of containment. It may therefore report low confidence in every fine relation while missing that a coarse relation has high probability. The distribution-induced taxonomy avoids this. Coarse probabilities are computed as sums over leaves or directly as broader boundary inequalities. This lets reasoning proceed at the

appropriate level of granularity: first infer that X is probably contained in Y , then refine into starts, during, finishes, or equals; first infer that X precedes or touches Y , then refine into strict before or approximate meets. This hierarchical behavior is especially important near boundary cases, where classical Allen leaves change discontinuously but the parent predicate remains stable.

5.9

Selecting a Best-Fitting Relation

A natural request is a single best-fitting relation for a configuration. The obvious choice, the maximiser of the thirteen leaf probabilities, is biased by relation measure and should be used with care. The six relations defined by strict inequalities (before, overlaps, during, contains, overlapped by, after) are full-dimensional regions, whereas the seven equality and contact relations occupy thin confidence bands of width on the order of τ . The probability of meets or starts is therefore structurally small, and a flat arg max over all thirteen leaves systematically disfavours contact relations and depends on τ : as τ → 0 a contact relation can never win. Comparing P (before) directly with P (meets) compares the mass of a region with that of a boundary. A flat maximum is thus meaningful only among siblings of comparable measure, for example within a single taxonomic level such as precedence versus overlap versus succession. Two selection rules respect the structure. The first is a top-down maximum-a-posteriori decoding over the taxonomy: choose the most probable coarse family by its summed leaf mass, descend into it, and refine, so that every decision weighs alternatives of comparable measure. Because the coarse probabilities are large and stable, the family decision is robust even where the leaf decision is delicate. The second is the relation of the most probable arrangement: classify the mode of the latent distribution, that is, the modal midpoints and durations, which yields a definite configuration whose relation is read off without any band-width bias. These two rules answer different questions. The taxonomic maximum identifies the most probable relation category under uncertainty, while the modal-arrangement relation identifies the relation of the single most likely configuration. They agree for well-separated fulldimensional relations and can diverge near contact: when the modal boundaries align within τ , the modal-arrangement relation is a contact relation such as meets, while the probability mass may still favour a thicker neighbour such as before or overlaps. Both are legitimate; the taxonomy makes explicit that the robust quantities are the coarse predicates, and that fine selection should proceed conditionally within them rather than as a flat comparison across heterogeneous leaves. The accompanying implementation provides all three selectors.

5.10

Extension to Spatial Relations

The construction transfers from time to space without new probabilistic machinery. Allen’s algebra already has a well-developed qualitative spatial counterpart: applying the interval relations independently to each Cartesian axis yields the rectangle algebra for axis-aligned rectangles, with 132 = 169 base relations, and in n dimensions the block algebra with 13n relations [19, 5, 6]. Two further calculi describe orthogonal facets of the same scene: the region connection calculus represents topology—disconnected, touching, overlapping, contained [32]—and the cardinal direction calculus represents projective direction [37]. These spatial relations are the analogue of the adverbial families of Section 5.3: just above, far to the left of, and right beside grade a directional relation exactly as shortly before grades precedence. Our generative semantics lifts to the rectangle algebra directly. A rectangle is two intervals, one per axis, each carrying the same midpoint-and-duration uncertainty used here; every edge is therefore an affine function of the latent Gaussians, and a rectangle relation (rx , ry ) holds on the intersection of the two axes’ linear-inequality regions. Its probability is the product of the per-axis orthant integrals when the axes are independent, and a single higher-dimensional 29

Gaussian orthant integral when they are correlated—the three- and four-dimensional integrals of the temporal case become six- and eight-dimensional. The 13n relations remain a complete partition for any tolerance, and contact relations again acquire positive measure through the tolerance band. The covariance-agnostic engine of Appendix C already evaluates the correlated case unchanged. What is novel is the combination, not the ingredients. The qualitative rectangle and block algebras are entirely crisp [5, 6]. Uncertainty has reached spatial relations only as fuzzy membership—Bloch’s morphological “fuzzy landscape” for directional relations [7], and fuzzy two-dimensional Allen relations [35]—or as probabilities annotated onto qualitative relations and propagated through a network, as in probabilistic region connection calculus [18]. The one line of work that, like ours, induces relation probabilities from a distribution over geometry assigns them to topological relations through a raster error model rather than in closed form [40]; and the computer-vision practice of modelling box corners as Gaussians [21] supplies our affine-Gaussian premise but never connects it to a relation algebra. Learned generative models of spatial language likewise fit a separate density per relation, without a closed-form partition [8]. A distribution-induced spatial algebra—rectangle and block relations as closed-form Gaussian orthant probabilities over a complete partition—therefore appears to be unoccupied, and is the natural next step for this work.

5.11

Limitations and Future Work

Several modelling choices can be relaxed. Midpoints and durations are taken to be independent and the primitive Gaussian variables uncorrelated; correlated temporal quantities require only the appropriate joint covariance in place of the diagonal one. Computation rests on multivariate Gaussian CDFs, which lack an elementary closed form beyond the bivariate case and are evaluated by specialised quadrature; this is inexpensive for the tri- and quadri-variate systems used here but is worth noting for large temporal networks. Three extensions are natural. First, because the relation probabilities are smooth functions of the temporal parameters, their gradients provide a differentiable signal of temporal tendency, connecting to robustness gradients in signal temporal logic [16, 11, 20, 28]. Second, the constraint-compilation view supports posterior updating from observed relations and networklevel inference over many events, in the spirit of probabilistic interval networks [34]. Third, the taxonomy and scale invariance suggest a calibrated mapping between relation probabilities and vague temporal language, building on factorized adverbial models [26] and fuzzy interval algebras [36, 4]; benchmark evidence that language models resolve vague temporal references markedly worse than explicit ones [25] underscores the need for such a principled mapping.

5.12

Conclusion

We have presented a probabilistic Allen algebra in which uncertain temporal points and intervals induce probabilities over qualitative relations. The approach unifies point–point, point– interval, and interval–interval reasoning; gives closed forms using error functions and multivariate Gaussian CDFs; treats equality/contact through confidence borders; and expresses relation taxonomy directly in terms of calculated probabilities. For NLP, the framework distinguishes contact from verbal grading and provides scale-invariant relation probabilities that normalize much of the context-sensitivity of vague temporal adverbials. This positions the framework as a bridge between metric temporal uncertainty, qualitative interval reasoning, temporal-relation taxonomies, and vague temporal language.

The Thirteen Relations, Grouped

Figure 10 lays out the same thirteen relations as the taxonomy tree of Figure 4, but as nested boxes: the two-way split into separated and non-separated configurations boxes the coarse families, and each family boxes its Allen leaves. Nested boxes are nested partition cells, so a family’s probability is the sum of the probabilities of the sketches it contains. SEPARATED / externally touching X precedes / touches Y

before

X follows / met by Y

meets

met by

after

NON-SEPARATED X ⊂ Y (strict)

partial overlap

X=Y

X ⊃ Y (strict)

starts during finishes

overlaps overlapped by

equals

finished by contains started by

Figure 10: The thirteen relations grouped by their partition. In every cell the reference interval Y (outlined) is held fixed—dotted ticks mark its edges—and the event X (filled) moves against it. Colour marks the coarse family, converse families sharing a hue and mirrored left↔right (before/after, starts/started by, . . . ). Nested boxes mirror the taxonomy of Figure 4: a family’s probability is the sum of its members’—e.g. P (X ⊆ Y ) = P (starts) + P (during) + P (finishes) + P (equals). The two containment blocks are the strict directions; equals is the separate central cell they share as a boundary.

Limiting Cases When Intervals Collapse to Points

Degenerate durations should be handled as limits. If dX = dY = 0, then X = {tX } and Y = {tY }. The only non-zero exact relations are ∆ −∆ P (X before Y ) = Φ , P (X after Y ) = Φ , (64) σZ σZ 2 + σ 2 . Approximate equality is where ∆ = µY − µX and σZ2 = σX Y τ −∆ −τ − ∆ P(|tY − tX | ≤ τ ) = Φ −Φ . σZ σZ

Exact equality has probability zero unless both points are deterministically identical. If only X collapses to a point, then X ⊆ Y becomes point-in-interval: dY P (X ⊆ Y ) = P |tY − tX | ≤ , 2

(65)

(66)

while Y ⊆ X is zero unless Y also collapses to the same point. Boundary correspondence becomes approximate equality between the point and aY or bY .

The thirteen-to-five fold in detail. This is the sign bookkeeping behind Proposition 4. Setting dX = 0 in the midpoint parameterization gives aX = bX = tX , and the four boundary differences of Section 3.8 collapse onto two through the identities A = aY − tX = G,

H = tX − bY = −B,

(67)

leaving the independent pair (A, B) = (aY − tX , bY − tX ) with B − A = dY ≥ 0, so A ≤ B. Reading Table 2 under these identities sorts the thirteen relations exactly. The five survivors reduce to point position within Y : relation

inequality at dX = 0

point tX relative to Y

before starts during finishes after

A>τ |A| ≤ τ, B > τ A < −τ, B > τ A < −τ, |B| ≤ τ B < −τ

before aY at aY strictly inside at bY after bY

The other eight are infeasible under A = G, H = −B, and A ≤ B: meets (A > τ, |G| ≤ τ ) and overlaps (A > τ, G < −τ ) both set G = A > τ ; finished by (A > τ, |B| ≤ τ ) and contains (A > τ, B < −τ ) violate A ≤ B; started by (|A| ≤ τ, B < −τ ) forces A ≤ B < −τ ; overlapped by (B < −τ, H < −τ ) and met by (B < −τ, |H| ≤ τ ) both set H = −B > τ ; and equals (|A| ≤ τ, |B| ≤ τ ) requires dY = B − A ≤ 2τ . Seven are thus outright empty on {dX = 0}; the eighth, equals, is feasible only for a near-degenerate Y (dY ≤ 2τ ) and otherwise contributes vanishing probability, its mass passing to during, starts, and finishes as the collapsing X falls inside Y . For dX > 0 each of the eight occupies a band of width O(dX ) that closes as dX → 0. Because every coarse taxonomy node is a fixed union of leaves, dominated convergence carries its probability continuously through the limit; the reduction therefore conserves probability within each parent while reallocating it among the leaves above. The symmetric collapse dY → 0 eliminates B against A the same way and reduces the five point– interval relations to {before, equals, after}; applying both collapses recovers the two-point case at the head of this appendix.

Alternative Interval Parameterizations

The midpoint–duration parameterization used in the body is convenient but not required. An interval has two degrees of freedom, and any pairing of one location quantity with the duration fixes it: midpoint and duration (t, d), start and duration (s, d), or end and duration (e, d), related by s = t − d/2 and e = t + d/2—or the two boundaries themselves, start and end (s, e), with the duration as their difference d = e − s. The duration d ≥ 0 is common to the first three, whose location quantities differ only by ±d/2; in the fourth it is derived, and d ≥ 0 reads as the end not preceding the start. In each case both boundaries are affine in the latent variables, so every Allen relation stays a conjunction of linear inequalities and its probability a conditional multivariate Gaussian orthant probability. Concretely, the thirteen relations see the two intervals only through the four boundary differences A = aY − aX ,

B = b Y − bX ,

G = a Y − bX ,

H = a X − bY

(68)

(the quantities tabulated in Table 2), so a parameterization is pinned down once these are written in its latent variables. Throughout, dX , dY ≥ 0 denote the truncated-Gaussian durations, shared by the three location–duration forms.

Start and duration. Take X = [sX , sX + dX ], so aX = sX and bX = sX + dX . With the start difference S = sY − sX ∼ N (µsY − µsX , σs2X + σs2Y ), A = S,

B = S + dY − dX ,

G = S − dX ,

H = −S − dY .

(69)

Here the latent start difference is the start/start primitive A. End and duration. Take X = [eX − dX , eX ], so aX = eX − dX and bX = eX . With the end difference E = eY − eX ∼ N (µeY − µeX , σe2X + σe2Y ), A = E + dX − dY ,

G = E − dY ,

B = E,

H = −E − dX .

(70)

Symmetrically, the latent end difference is the finish/finish primitive B. The midpoint form of the body sits between the two: with Z = tY − tX , A = Z + 12 (dX − dY ), B = Z − 21 (dX − dY ), G = Z − 21 (dX + dY ), and H = −Z − 12 (dX + dY ). Start and end. Take X = [sX , eX ] with independent Gaussian boundaries, so aX = sX , bX = eX , and the duration is derived, dX = eX − sX . The four differences are then the boundary differences read literally, A = sY − sX ,

B = e Y − eX ,

G = s Y − eX ,

H = s X − eY ,

(71)

and the truncation dX ≥ 0 is the half-space eX ≥ sX : the law is that of independent boundaries q conditioned on each interval being well formed, with normalizer QX = Φ (µeX −µsX )/ σs2X + σe2X . In the body’s coordinates this is a midpoint–duration pair that is correlated : tX = 21 (sX + eX ) and DX = eX − sX are jointly Gaussian with 2 2 2 2 2 1 σt2X = 14 σs2X + σe2X , σD = σ + σ , Cov(t , D ) = σ − σ , (72) X X s e e s 2 X X X X X so a sharp start (σsX = 0) is the start form, a sharp end is the end form, and equally uncertain boundaries give Cov(tX , DX ) = 0 with σDX = 2σtX : the independent midpoint–duration model of the body is exactly the symmetric-boundary case. Conversely, independent latent (t, D) with 2 /4 and arbitrary σt , σD are boundaries s = t − D/2, e = t + D/2 of equal variance σt2 + σD 2 2 2 2 correlation (σt − σD /4)/(σt + σD /4). The independence assumed in Section 3.2 is therefore not a different model from a boundary one, but the choice of which pair is taken uncorrelated. Each form is the same inequality system in different coordinates: the latent vector ( · , DX , DY ) and the truncation DX , DY ≥ 0 are unchanged—the boundary form either in its own four coordinates or, through Equation (72), in (Z, DX , DY ) with a non-diagonal Σ—and only the linear map to (A, B, G, H) differs, so the orthant machinery is identical. What the choice does change is the modelled law—which two quantities are taken as independent and Gaussian—so one selects the pair best matched to the data (start times for events with a known onset, end times for deadlines, the midpoint for symmetric jitter, the two boundaries when each is timestamped on its own), while the derivation, closed forms, and partition carry over verbatim.

C.1

General Linear Form

The start, end, and midpoint forms are instances of one template, and nothing in the derivation, the closed forms, or the partition depends on the choice. Collect every latent Gaussian temporal quantity of the two objects into a vector U ∼ N (µ, Σ)—in the midpoint form of Section 3.8, U = (Z, DX , DY )T ; in the start and end forms, (S, DX , DY )T and (E, DX , DY )T ; in the boundary form, (SX , EX , SY , EY )T . The truncation D ≥ 0 of Section 3.2 is a set of half-spaces of U —its duration coordinates where the form has them, the rows EX − SX ≥ 0 where it does not—with

Q normalizer Q = X P(DX ≥ 0). The form enters through one object only—a linear difference map—while the relations are read the same way for every form. First, the boundaries are linear in U , so the four boundary differences of Table 2 are too:   A B    = M U, (73) G H with the difference map M read off the boundaries—the only object the parameterization changes. From the start and end differences above and the midpoint form of Section 3.8,       1 − 12 1 1 0 0 1 1 −1 2 1   1 −1  1 −1 1  1 0 0 2 2     , MM =  (74)  1 − 1 − 1  , MS =  1 −1 0  , ME =  1 0 −1 2 2 −1 − 12 − 12 −1 0 −1 −1 −1 0 each acting on its form’s U (columns ordered as that form’s coordinates); MM is the matrix M of Appendix D. The boundary form has the simplest map of all, acting on (SX , EX , SY , EY )T ,   −1 0 1 0  0 −1 0 1   MSE =  (75)  0 −1 1 0  , 1 0 0 −1 each row one of the four boundary differences written out. No constant term is needed in any form—the differences are purely linear in U . Second, each relation R is a sign pattern on those four differences—its signature σR ∈ {−1, 0, +1}4 of Table 3 (the +, 0, − of that table), the same for every form. The signature is the selector: a matrix SR with entries in {−1, 0, +1} acting on (A, B, G, H)T , where a strict sign σv ∈ {±1} gives the single row −σv v ≤ −τ and a coincidence σv = 0 the contact pair +v ≤ τ, −v ≤ τ . For the six strict relations this is just SR = − diag(σR ) with bR = −τ 1; each coincidence of a contact relation replaces that diagonal entry by a ± row pair. Explicitly, before (σ = (+, +, +, −), strict) and meets (σ = (+, +, 0, −), with G in contact) give     −1 0 0 0 −1 0 0 0  0 −1 0 0  0 −1 0 0    0 ,  0 1 0 , S = (76) Sbefore =  meets   0 0 −1 0 0 0 −1 0 0 0 0 1 0 0 0 1 with bbefore = −τ 1 and bmeets = τ (−1, −1, 1, 1, −1)T ; the coincident G of meets supplies the two band rows ±G ≤ τ , and rows beyond the minimal defining set of Table 2 are entailed and harmless. Substituting the difference map (73) carries the constraints to U , SR M U ≤ b R ,

(77)

which is the relation system LR (U ) = AR U − bR ≤ 0 of Equation (7) with AR = SR M ; the truncation D ≥ 0 enters separately, as the conditioning event below. The parameterization thus lives entirely in M and the relation entirely in its signature σR (Table 3)—a relation is a choice of which signs the four differences take, not an additive shift of them. Hence P LR (U ) ≤ 0, D ≥ 0 P (R) = , (78) Q the conditional Gaussian mass of a polytope, evaluated by standardizing its affine rows with µ and Σ as in Section 3.8. Between parameterizations only (M, µ, Σ) change; the signatures of Table 3, the closed forms, and the partition carry over verbatim. 34

Example: before in two coordinate systems. From Table 2, before is the single row G > τ . In the midpoint form G = Z − 12 (DX + DY ), so P Z − 12 (DX + DY ) > τ, DX , DY ≥ 0 P (before) = ; (79) Q in the start form G = S −DX , giving P(S −DX > τ, DX , DY ≥ 0)/Q. These are one probability written in different latent coordinates, and both collapse, when the durations are sharp, to the one-dimensional tail 21 erfc(·) of Section 3.5. Example: correlated quantities. If the two events share an onset cue, their start times are correlated and Σ is no longer diagonal. Nothing else changes: LR and the truncation are as above, and the off-diagonal entries of Σ merely propagate into the standardizing covariance of the orthant integral. The independence assumed in Section 3.2 is thus a convenience, not a requirement.

Primitive Factorization of the Probabilistic Algebra

This appendix derives Proposition 3: the probabilistic algebra of Section 3.8 is exactly the joint law of the four temporal primitives, and its primitive marginals have one-dimensional Gaussian closed forms. Latent model and the primitive map. Let U = (Z, DX , DY )T , with Z = tY − tX ∼ 2 +σ 2 , independent of the latent durations D , D conditioned N (∆, σZ2 ), ∆ = µY −µX , σZ2 = σX X Y Y on DX , DY ≥ 0. The four boundary differences are linear in U :     1 1 − 21 A 2  1 −1 1  B   2 2    = MU, M = (80)  . G  1 − 12 − 12  H −1 − 12 − 12 The rows obey MH = MG − MA − MB , so H = G − A − B and rank M = 3; the triple (A, B, G) is an invertible image of U . Write Φ(U ) = (sgnτ A, sgnτ B, sgnτ G, sgnτ H) and let Mv denote the row of M for difference v. Step 1: each relation is a primitive fiber. Table 2 defines each relation by sign constraints on (A, B) and, on the two diagonal cells, on G or H; the remaining signs are entailed on the feasible cone. For instance G > τ means bX < aY − τ ; with aX < bX and aY < bY this forces aX < bX < aY < bY , hence A > τ , B > τ , H < −τ , so {G > τ } = Φ−1 (+, +, +, −) = {before}. The same entailment closes every row, giving {R} = Φ−1 (σR ); the thirteen signatures σR of Table 3 are exactly the feasible values of Φ. This is the partition of Proposition 1 read in primitive coordinates. T Step 2: relation probability is a joint primitive integral. Because {R} = v {sgnτ v = σR (v)}, Z hY i 1 P (R) = 1{sgnτ v = σR (v)} 1{DX ≥ 0, DY ≥ 0} ϕ(u; µ, Σ) du, (81) QX QY R3 v with QX = P(DX ≥ 0) and QY = P(DY ≥ 0). Each factor is a slab or half-space in U : {sgnτ v = +} = {Mv U > τ }, {sgnτ v = −} = {Mv U < −τ }, and the contact band {sgnτ v = 0} = {|Mv U | ≤ τ }. Hence {R} is a (possibly lower-dimensional) polytope and P (R) is the 35

Gaussian measure of that polytope — the conditional multivariate-Gaussian orthant probability of Section 3.8. Each contact band expands by inclusion–exclusion, 1{|Mv U | ≤ τ } = 1{Mv U ≤ τ } − 1{Mv U < −τ },

(82)

so P (R) is a signed sum of pure orthant probabilities; the number of bands equals the contact count c(R) of Proposition 2. Step 3: primitive marginals in closed form. PMarginalizing the joint over three coordinates gives the coarse predicate P (sgnτ v = s) = R: σR (v)=s P (R). Each is one-dimensional: conditioning on (dX , dY ) leaves Z ∼ N (∆, σZ2 ) as the only free Gaussian, and each difference is ±Z plus a duration shift. With the expectation Ed taken over the truncated durations, the gap G = Z − 12 (dX + dY ) gives !# " ∆ − τ − 12 (dX + dY ) = P (before), (83) P (sgnτ G = +) = Ed Φ σZ " ! !# ∆ + τ − 12 (dX + dY ) ∆ − τ − 21 (dX + dY ) P (sgnτ G = 0) = Ed Φ −Φ σZ σZ = P (meets),

(84)

and the start/start difference A = Z + 21 (dX − dY ) yields shared start, " ! !# τ + 12 (dX − dY ) − ∆ −τ + 12 (dX − dY ) − ∆ P (sgnτ A = 0) = Ed Φ −Φ σZ σZ

(85)

= P (starts) + P (equals) + P (started by). These one-dimensional forms agree with the full multivariate engine to Monte-Carlo precision. Step 4: the joint does not factor. Since rank M = 3 < 4, the primitives obey the determinQ istic identity H = G − A − B, and Σ couples them; thus P (R) ̸= v P (sgnτ v = σR (v)) except in degenerate limits. Two regimes make the gap explicit. Entailment: G > τ ⇒ A, B > τ , so P (before) = P (sgnτ G = +), well below the product of the three marginals. Conflict: at a shared midpoint (∆ = 0, small σZ ) one has A ≈ −B, so {A > τ } and {B > τ } are nearly mutually exclusive and their joint falls far below the product. The covariance Σ is precisely the dependence a logical primitive ontology such as CIDOC CRM omits and that the probabilistic algebra restores.

Software Interface and Implementation Notes

The algebra ships as an open, MIT-licensed, tested Python package (import name paa, distribution probabilistic-allen-algebra). This appendix documents the user-facing interface—the functions you need to call to obtain the probabilities derived in the body—and the implementation choices that bear on the paper’s claims, in particular cost and numerical accuracy. Every quantity below is the analytic object defined earlier, not a Monte-Carlo estimate; sampling is used only for validation (Section 3.8.1). Availability and contents. The package is at https://github.com/HRI-EU/probabilisticallen-algebra and installs with pip install probabilistic-allen-algebra (Python ≥ 3.11, depending only on numpy and scipy). It is analytic and self-contained: it needs no data, no network, and no API access, and reproduces every number and figure in this paper from source. 36

1. What are the two objects X, Y ? both points → point–point (3 relations, erf/erfc); one point, one interval → point–interval (5 relations, Φ2 ); two intervals → interval–interval (13 relations, Φ3 /Φ4 ). 2. For each interval, which quantities are known? position + duration → IntervalGaussian(mu t, sigma t, mu d, sigma d); start + duration → from start(...); end + duration → from end(...); a point → point(mu t, sigma t). 3. Choose the tolerance τ ; then the query. all thirteen probabilities → relation probabilities(e, r, tau); a coarse family → coarse predicates / refine; a single best label → hierarchical decode / map relation.

Figure 11: Using the formulas and software in three decisions. The object types fix the closedform family and how many relations are non-trivial (Sections 3.5–3.8); the known quantities fix each interval’s constructor (Section 3.3); the desired output fixes the call. The first decision is conceptual—points are degenerate intervals, so relation probabilities serves all three cases through one call—so the chart maps the formulas rather than forcing a branch in code. objects (X, Y )

relations

closed form

point, point point, interval interval, interval

3 5 13

erf/erfc bivariate Φ2 Φ3 /Φ4 orthant

constructor(s) point point + interval ctor interval ctor

Table 4: Object types fix the closed-form family and the number of non-trivial relations; Step 2 of Figure 11 fixes the constructor for each interval. Six modules realize the constructions of the preceding sections—intervals (the uncertain objects of Section 3.2), relations (the thirteen orthant probabilities of Section 3.8), taxonomy (the partition tree and coarse predicates of Section 3.9), decode (the best-relation selectors of Section 5.9), primitives (the boundary-difference factorization of Appendix D), and plotting (the figure generators)—and a command-line interface (paa prob | coarse | decode | ..., equivalently python -m paa) exposes the same queries from the shell. A pytest suite enforces the partition, the Monte-Carlo agreement, the limiting reductions, and the invariances (Section 4), so every reported result is reproducible from source. The optional viz extra adds matplotlib for the figure generators; nothing else is required. Choosing the right call. Three decisions route a problem to its formula and function (Figure 11, Table 4): the object types, the quantities known for each interval, and the desired output. Constructing uncertain objects. An uncertain interval is created as IntervalGaussian( mu t, sigma t, mu d, sigma d), a Gaussian midpoint t ∼ N (µt , σt2 ) and a latent duration D ∼ N (µd , σd2 ) truncated to D ≥ 0 (Section 3.2). A time point is the helper point(mu t, sigma t=0.0), the degenerate interval with zero duration. Deterministic limits are admissible: σt = 0 fixes the midpoint and σd = 0 fixes the duration. Computing relation probabilities. The single entry point is relation probabilities(e, r, tau=0.0), which returns the thirteen probabilities for the event e against the reference r as a dictionary keyed by relation name. The object-oriented form ProbabilisticAllenRelations(e, r) exposes one method per relation (e.g. .before(tau)) and .all relations(tau); the tol-

erance τ is the single partition parameter of Section 3.8.1. Listing 1 runs the full flow end to end. Listing 1: Minimal end-to-end example: construct two uncertain intervals, compute the thirteen relation probabilities (a partition summing to one), and traverse the taxonomy of Section 3.9— coarse-predicate node masses, a within-parent refinement, and the hierarchical decode. Each print displays the value shown in the trailing comment. from paa import (IntervalGaussian, relation_probabilities, coarse_predicates, refine, hierarchical_decode) e = IntervalGaussian(mu_t=0.0, sigma_t=1.0, mu_d=2.0, sigma_d=0.3) r = IntervalGaussian(mu_t=3.0, sigma_t=1.0, mu_d=1.5, sigma_d=0.4) p = relation_probabilities(e, r, tau=0.25) # dict: 13 relations -> probability print(sum(p.values())) # ~ 1.0 (a true partition) c = coarse_predicates(p) # masses of every taxonomy node print(c["separated"], c["non_separated"]) # parent masses, sum to 1 print(refine(p, "precede")) # {’before’:.., ’meets’:..}, sums to 1 print(hierarchical_decode(p)) # [(’separated’,..),(’precede’,..),(’before’,..)]

Coarse predicates, refinement, and selection. Given the leaf dictionary p, the taxonomy calculus of Section 3.9 is realized by coarse predicates(p) (the probability of every node, each the sum of its leaves) and refine(p, parent) (the conditional distribution P (leaf | parent)). The partition tree itself is the data structure TREE, with LEAVES, leaves of, and the overlapping non-strict containment unions VIEWS. Three best-fitting-relation selectors implement the discussion of Section 5.9: most probable relation (flat arg max, measure-biased), hierarchical decode (top-down maximum-a-posteriori over the taxonomy), and map relation (the relation of the modal arrangement). The primitive decomposition of Appendix D is exposed by primitive probabilities (the four three-way marginals), decompose, contacts, and the signatures CANONICAL SIGNS. Implementation and cost. Inference is analytic and sampling-free. Each relation is the Gaussian measure of a polytope in the latent U = (Z, DX , DY )T with Z = tY − tX (Section 3.8), evaluated as a multivariate-normal CDF in at most three dimensions; before and after collapse to a single half-space (a one-dimensional Φ over the gap), and the point–point and point–interval cases reduce to the error function and a bivariate Φ2 (Appendix B). A call to relation probabilities therefore returns all thirteen from a handful of low-dimensional CDF evaluations in time independent of the temporal scale and of any sample count. Degenerate inputs are handled exactly rather than as a numerical limit: any latent coordinate with standard deviation at or below eps (default 10−12 ) is removed from the Gaussian system and folded into a deterministic constant, so points and fixed durations lower the CDF dimension and realize the collapse limits of Appendix B without singular covariances; the lower-dimensional contact bands are evaluated with a singular-aware CDF. Every probability is divided by the truncation normalizer Q = P(DX ≥ 0) P(DY ≥ 0) that conditions on non-negative durations. Because no random number generator is involved at inference, results are deterministic and reproducible. Numerical validation. The analytic probabilities agree with an independent Monte-Carlo classifier to a maximum absolute error of ≈ 1–2 × 10−4 at 4 × 106 samples, and the thirteen sum to one within that noise for every tolerance tested, confirming Proposition 1 (Section 4); scale invariance and converse symmetry hold to the same tolerance. These checks, together with the limiting reductions and the figure generators, are shipped as the package test suite so that all reported results are reproducible from source. 38

References [1] James F. Allen. Maintaining knowledge about temporal intervals. Communications of the ACM, 26(11):832–843, 1983. [2] ArchaeoPhases Contributors. Allen’s Interval Algebra. CRAN vignette, 2025. Documentation for empirical Allen relation probabilities from Bayesian chronological models. [3] Silvana Badaloni and Massimiliano Giacomin. A fuzzy extension of allen’s interval algebra. In AI*IA 99: Advances in Artificial Intelligence, volume 1792 of Lecture Notes in Computer Science, pages 155–165, Berlin, Heidelberg, 2000. Springer. [4] Silvana Badaloni and Massimiliano Giacomin. The algebra IAfuz : A framework for qualitative fuzzy temporal reasoning. Artificial Intelligence, 170(10):872–908, 2006. [5] Philippe Balbiani, Jean-François Condotta, and Luis Fariñas del Cerro. A model for reasoning about bidimensional temporal relations. In Principles of Knowledge Representation and Reasoning (KR’98), pages 124–130, San Francisco, CA, USA, 1998. Morgan Kaufmann. [6] Philippe Balbiani, Jean-François Condotta, and Luis Fariñas del Cerro. A tractable subclass of the block algebra: Constraint propagation and preconvex relations. In Progress in Artificial Intelligence (EPIA’99), volume 1695 of Lecture Notes in Computer Science, pages 75–89, Berlin, Heidelberg, 1999. Springer. [7] Isabelle Bloch. Fuzzy relative position between objects in image processing: A morphological approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 21(7):657– 664, 1999. [8] Colin R. Dawson, Jeremy Wright, Antons Rebguns, Marco Valenzuela Escárcega, Daniel Fried, and Paul R. Cohen. A generative probabilistic framework for learning spatial language. In IEEE Third Joint International Conference on Development and Learning and Epigenetic Robotics (ICDL-EpiRob), pages 1–8, Piscataway, NJ, USA, 2013. IEEE. [9] Alex Dekhtyar, Robert Ross, and V. S. Subrahmanian. Probabilistic temporal databases, i: Algebra. ACM Transactions on Database Systems, 26(1):41–95, 2001. [10] Martin Doerr. The CIDOC conceptual reference module: An ontological approach to semantic interoperability of metadata. AI Magazine, 24(3):75–92, 2003. [11] Alexandre Donzé and Oded Maler. Robust satisfaction of temporal logic over real-valued signals. In Formal Modeling and Analysis of Timed Systems (FORMATS), volume 6246 of Lecture Notes in Computer Science, pages 92–106, Berlin, Heidelberg, 2010. Springer. [12] Thomas Drakengren and Peter Jonsson. Eight maximal tractable subclasses of Allen’s algebra with metric time. Journal of Artificial Intelligence Research, 7:25–45, 1997. [13] Thomas S. Dye and Caitlin E. Buck. Archaeological sequence diagrams and Bayesian chronological models. Journal of Archaeological Science, 63:84–93, 2015. [14] Curtis E. Dyreson and Richard T. Snodgrass. Supporting valid-time indeterminacy. ACM Transactions on Database Systems, 23(1):1–57, 1998. [15] Julian Eggert, Svenja Kenneweg, Jörg Deigmöller, and Philipp Cimiano. From vague temporal adverbials to uncertain times and back: A complete generative mapping with the probabilistic Allen algebra. Companion paper; arXiv preprint forthcoming, 2026.

[16] Georgios E. Fainekos and George J. Pappas. Robustness of temporal logic specifications for continuous-time signals. Theoretical Computer Science, 410(42):4262–4291, 2009. [17] Gustav Theodor Fechner. Elemente der Psychophysik. Breitkopf und Härtel, Leipzig, 1860. [18] Codruta Girlea and Eyal Amir. Probabilistic region connection calculus. In Knowledge Representation and Reasoning: Integrating Symbolic and Neural Approaches; Papers from the 2015 AAAI Spring Symposium, pages 66–70, Palo Alto, CA, USA, 2015. AAAI Press. [19] Hans Werner Güsgen. Spatial reasoning based on allen’s temporal logic. Technical Report TR-89-049, International Computer Science Institute (ICSI), Berkeley, 1989. [20] Iman Haghighi, Noushin Mehdipour, Ezio Bartocci, and Calin Belta. Control from signal temporal logic specifications with smooth cumulative quantitative semantics. In Proceedings of the 58th IEEE Conference on Decision and Control (CDC), pages 4361–4366, Piscataway, NJ, USA, 2019. IEEE. [21] David Hall, Feras Dayoub, John Skinner, Haoyang Zhang, Dimity Miller, Peter Corke, Gustavo Carneiro, Anelia Angelova, and Niko Sünderhauf. Probabilistic object detection: Definition and evaluation. In IEEE Winter Conference on Applications of Computer Vision (WACV), pages 1031–1040, Piscataway, NJ, USA, 2020. IEEE. [22] Steve Hanks, David Madigan, and Jonathan Gavrin. Probabilistic temporal reasoning with endogenous change. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence (UAI), pages 245–254, San Francisco, CA, USA, 1995. Morgan Kaufmann. [23] Quzhe Huang, Yutong Hu, Shengqi Zhu, Yansong Feng, Chang Liu, and Dongyan Zhao. More than classification: A unified framework for event temporal relation extraction. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 9631–9646, Toronto, Canada, 2023. Association for Computational Linguistics. [24] Tomi Janhunen and Michael Sioutis. Allen’s interval algebra makes the difference. In Declarative Programming and Knowledge Management (DECLARE 2019), volume 12057 of Lecture Notes in Computer Science, pages 89–98, Cham, 2020. Springer. [25] Svenja Kenneweg, Jorg Deigmoller, Philipp Cimiano, and Julian Eggert. TRAVELER: A benchmark for evaluating temporal reasoning across vague, implicit and explicit references, 2025. [26] Svenja Kenneweg, Jorg Deigmoller, Julian Eggert, and Philipp Cimiano. A factorized probabilistic model of the semantics of vague temporal adverbials relative to different event types, 2025. [27] Daniel Lassiter and Noah D. Goodman. Adjectival vagueness in a Bayesian model of interpretation. Synthese, 194(10):3801–3836, 2017. [28] Karen Leung, Nikos Aréchiga, and Marco Pavone. Backpropagation through signal temporal logic specifications: Infusing logical structure into gradient-based methods. In Algorithmic Foundations of Robotics XIV (WAFR 2020), volume 17 of Springer Proceedings in Advanced Robotics, pages 432–449, Cham, 2021. Springer. [29] Malek Mouhoub and Li Liu. Managing uncertain temporal relations using a probabilistic interval algebra. In Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, pages 3399–3404, Piscataway, NJ, USA, 2008. IEEE.

[30] Sergios Petridis, Georgios Paliouras, and Stavros J. Perantonis. Allen’s hourglass: Probabilistic treatment of interval relations. In Proceedings of the 17th International Symposium on Temporal Representation and Reasoning (TIME), pages 87–94, Los Alamitos, CA, USA, 2010. IEEE Computer Society. [31] James Pustejovsky, Jose Castano, Robert Ingria, Roser Sauri, Robert Gaizauskas, Andrea Setzer, and Graham Katz. TimeML: Robust specification of event and temporal expressions in text. In New Directions in Question Answering: Papers from the 2003 AAAI Spring Symposium, pages 28–34, Menlo Park, CA, USA, 2003. AAAI Press. [32] David A. Randell, Zhan Cui, and Anthony G. Cohn. A spatial logic based on regions and connection. In Principles of Knowledge Representation and Reasoning (KR’92), pages 165–176, San Mateo, CA, USA, 1992. Morgan Kaufmann. [33] Jochen Renz and Bernhard Nebel. Efficient methods for qualitative spatial reasoning. Journal of Artificial Intelligence Research, 15:289–318, 2001. [34] Vladimir Ryabov and André Trudel. Probabilistic temporal interval networks. In Proceedings of the 11th International Symposium on Temporal Representation and Reasoning (TIME), pages 64–67, Los Alamitos, CA, USA, 2004. IEEE Computer Society. [35] Nadeem Salamat and El-hadi Zahzah. Two-dimensional fuzzy spatial relations: A new way of computing and representation. Advances in Fuzzy Systems, 2012:167939, 2012. [36] Steven Schockaert, Martine De Cock, and Etienne E. Kerre. Fuzzifying allen’s temporal interval relations. IEEE Transactions on Fuzzy Systems, 16(2):517–533, 2008. [37] Spiros Skiadopoulos and Manolis Koubarakis. Composing cardinal direction relations. Artificial Intelligence, 152(2):143–171, 2004. [38] Siddharth Vashishtha, Benjamin Van Durme, and Aaron Steven White. Fine-grained temporal relation extraction. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics (ACL), pages 2906–2919, Florence, Italy, 2019. Association for Computational Linguistics. [39] Marc Verhagen, Robert Gaizauskas, Frank Schilder, Mark Hepple, Graham Katz, and James Pustejovsky. SemEval-2007 Task 15: TempEval temporal relation identification. In Proceedings of the Fourth International Workshop on Semantic Evaluations (SemEval2007), pages 75–80, Prague, Czech Republic, 2007. Association for Computational Linguistics. [40] Stephan Winter. Uncertain topological relations between imprecise regions. International Journal of Geographical Information Science, 14(5):411–430, 2000. [41] Gal Zauberman, B. Kyu Kim, Selin A. Malkoc, and James R. Bettman. Discounting time and time discounting: Subjective time perception and intertemporal preferences. Journal of Marketing Research, 46(4):543–556, 2009.

Record · ID 978465 · SHA-256 e7de7d293931513d
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.