Docs / Logic / Temporal / Allen

Allen's interval relations

import Linglib.Logic.Temporal.Allen · namespace Allen

This file defines the relations between closed intervals of a linear order Allen 1983, extended to point intervals. How one interval stands to another is the order type of their four endpoints, recorded as the comparisons among them, and the relations are the comparisons that two intervals realize, twenty-six in all. The relation of two intervals survives an order embedding, and two pairs of intervals stand in the same relation exactly when a partial isomorphism pairs their endpoints.

Implementation notes

A relation records whether each interval is a point; with the four cross comparisons alone composition is not exact.

References

  • Allen 1983, Maintaining Knowledge about Temporal Intervals

Declarations

The comparisons among the endpoints of two intervals: the first interval's start and end against the second's start and end, and each interval's start against its own end, lt for a proper interval and eq for a point.

structure ComparisonsL40–56
  • fstFst : Ordering

    The first interval's start against the second's start.

  • fstSnd : Ordering

    The first interval's start against the second's end.

  • sndFst : Ordering

    The first interval's end against the second's start.

  • sndSnd : Ordering

    The first interval's end against the second's end.

  • firstShape : Ordering

    The first interval's start against its end.

  • secondShape : Ordering

    The second interval's start against its end.

Derives DecidableEq, Repr.

Used by ofEndpoints, Comparisons.swap, Comparisons.swap_swap, Comparisons.dual, Comparisons.dual_dual, realizable, Comparisons.swap_mem_realizable, Comparisons.dual_mem_realizable, Relation

L62–65
L96–100
L107–113

A relation is how one interval of a linear order stands to another: comparisons among the endpoints of two intervals that some two intervals realize.

structure RelationL128–132
extends Comparisons :

Built from ,

Instances instInsertRelationIntervalAlgebra, instMembershipRelationIntervalAlgebra, instSingletonRelationIntervalAlgebra

Used by Relation.ext_iff, Relation.ext, Relation.instDecidableEq, Relation.equivRealizable, Relation.instFintype, Relation.inv, Relation.inv_inv, Relation.dual, Relation.dual_dual, card_relation, relation, exists_relation_eq, Relation.position

Used in Fragments/Manambu/Clause, Logic/Temporal/IntervalAlgebra, Semantics/Aspect/Viewpoint, BonehDoron2013

L152
L158

There are twenty-six relations: Allen's thirteen between proper intervals, five between a point and a proper interval, five between a proper interval and a point, and three between points.

theorem card_relationL162–165
:
Fintype.card Relation = 26

Built from

The relation of two intervals

The relation of the interval i to the interval j.

def relationL173–175
{T : Type u_1} [LinearOrder T] (i j : NonemptyInterval T) :
  • relation i j = { toComparisons := ofEndpoints i.toProd.1 i.toProd.2 j.toProd.1 j.toProd.2, mem_realizable := ⋯ }

Built from ,

Used by toComparisons_relation, relation_map, exists_relation_eq, inv_relation, dual_relation, relation_eq_of_mem_partialIso, exists_partialIso_of_relation_eq, position_relation

Used in Fragments/Manambu/Clause, Logic/Temporal/IntervalAlgebra, Aikhenvald2008

The relation of two intervals survives an order embedding.

theorem relation_mapL180–188
{T : Type u_1} [LinearOrder T] {β : Type u_2} [LinearOrder β] (f : T ↪o β) (i j : NonemptyInterval T) :
relation (NonemptyInterval.map f.toOrderHom i) (NonemptyInterval.map f.toOrderHom j) = relation i j

Built from

L192–196
L203–204
L206–208

Partial isomorphisms

Mathlib's Order.PartialIso pairs finitely many points of two linear orders that compare alike, so intervals whose endpoints it pairs stand in the same relation.

L221–230
L232–248