Docs / Logic / Temporal / IntervalAlgebra

The interval algebra

import Linglib.Logic.Temporal.IntervalAlgebra

An element of the interval algebra is a set of the relations of Allen 1983 in which one interval of a linear order may stand to another, read as their disjunction. Elements form a Boolean algebra with a converse and a composition whose unit is equality; composition distributes over joins, which the IdemSemiring instance records. Each element is a relation between intervals. On an order with four points the relations order as the elements do, and on a dense order without endpoints the relation of a product is the composite of the relations, so the laws of composition are those of relations on the rationals. The point algebra embeds as the relations between point intervals.

Implementation notes

The sum of the semiring is the join. The composite of two elements is read off the intervals among six points, placing a second interval only beside first intervals that stand to it in the second element, which keeps it small enough for decide +kernel. The named elements are irreducible, so that elaboration, which never needs their values, does not compute them, and are built by IntervalAlgebra.ofPred from a predicate on relations.

References

Declarations

L40–43
L65–66
L73

The relation of an element

The relation of an element relates an interval to the intervals that stand to it in one of the element's relations.

def IntervalAlgebra.toSetRelL81–84
{T : Type u_1} [LinearOrder T] (C : IntervalAlgebra) :
SetRel (NonemptyInterval T) (NonemptyInterval T)

Built from

Used by IntervalAlgebra.mem_toSetRel, IntervalAlgebra.instDecidableMemProdNonemptyIntervalSetRelToSetRelMk, IntervalAlgebra.toSetRel_bot, IntervalAlgebra.toSetRel_sup, IntervalAlgebra.toSetRel_mono, IntervalAlgebra.toSetRel_subset_toSetRel_iff, IntervalAlgebra.forall_toSetRel_subset_iff, IntervalAlgebra.toSetRel_injective, IntervalAlgebra.toSetRel_inv, IntervalAlgebra.mem_toSetRel_dual, IntervalAlgebra.toSetRel_comp_subset, IntervalAlgebra.toSetRel_mul, IntervalAlgebra.image_toSetRel_subset_mul, IntervalAlgebra.image_toSetRel_mul, IntervalAlgebra.mem_toSetRel_precedes, IntervalAlgebra.mem_toSetRel_overlaps, IntervalAlgebra.mem_toSetRel_le, IntervalAlgebra.mem_toSetRel_ofPosition, IntervalAlgebra.instIsTransNonemptyIntervalToSetRelPrecedes, IntervalAlgebra.toSetRel_precedes_subset_comp_self_iff, IntervalAlgebra.toSetRel_precedes_comp_self, IntervalAlgebra.toSetRel_one, IntervalAlgebra.HoldsAlong, IntervalAlgebra.instDecidableHoldsAlong, IntervalAlgebra.HoldsAlong.mem_toSetRel_prod, IntervalAlgebra.mem_toSetRel_prod_iff

Used in Semantics/Aspect/Viewpoint, Semantics/Tense/Perspective, Semantics/Tense/Quantificational, AnandToosarvandani2019, ArreguiKusumoto1998 and 12 more

L88
L92–93
L113–119
L121–124

Converse

Reversed time

L160–163

Composition

On dense time without endpoints the relation of a product is the composite of the relations: the middle interval of a configuration of endpoints can be placed between any two intervals that stand as its outer ones do.

theorem IntervalAlgebra.toSetRel_mulL214–231
{T : Type u_1} [LinearOrder T] [DenselyOrdered T] [NoMinOrder T] [NoMaxOrder T] (C D : IntervalAlgebra) :
(C * D).toSetRel = C.toSetRel.comp D.toSetRel

Built from ,

L233–238
L240–243

Named elements

L249–251
L257–259
L282–284
L286–288
L292–294
L296–297
L299
L301–302
L304–305
L307
L309–311
L313
L315
L325–327
L329–331
L333–335
L337–340
L342–344
L350–352
L368–369
L371–372
L374
L380–382
L384–392

Points

The point algebra embeds as the relations between point intervals.

L419–422
L440–455

The laws of composition

The relations of the elements on the rationals are faithful and exact, so each law of composition is the law of relations it names.

L462–466
L486
L488
L522–524

Chains

A clause's times form a chain, each related to the one before it by a head's element.

L534–539
L541–549
L556–563
L565–582