This notebook builds on Allen’s Interval Algebra by extending in threeways:
Points & Intervals – time points are integrated with time intervals
Right-Branching Time – building on 1, time can also branch to theright (future)
Left-Branching Time – again, building on 1, time can also branch fromthe left (past)
NOTE: However, left- and right-branching time algebras cannot be mixed.
References
“Intervals, Points, and Branching Time” by A.J.Reich- basis for the extensions here to Allen’s algebra
Allen’s IntervalAlgebra orhere - summarizesAllen’s algebra of proper time intervals
“Maintaining Knowledge about Temporal Intervals” by James F.Allen- Allen’s original paper (PDF)
Dependencies
>>> import qualreas as qr>>> import os
>>> path = os.path.join(os.getenv('PYPROJ'), 'qualreas')1. Linear Interval and Point Algebra
In Allen’s original algebra, time is linear and only applies to propertime intervals, not time points. So, effectively, it is a LinearInterval Algebra, which is the name used for its JSON definition file.
In [Reich,1994],Allen’s algebra was extended to include time points, as well as properintervals, to obtain a Linear Interval & Point Algebra. We’ll describeit in this section.
The Linear Interval & Point algebra extends Allen’s algebra by adding 5new relations, involving time points, and modifies the domains andranges of 4 of the original 13 relations.
# Instantiate algebra and print some basic info about it>>> algX = qr.Algebra(os.path.join(path, "Algebras/Extended_Linear_Interval_Algebra.json"))>>> print(algX.name)>>> print(algX.description)>>> algX_num_elements = len(algX.elements)>>> algX_elem_list = ', '.join(str(algX.elements).split("|"))>>> print(f"This algebra has the following {algX_num_elements} elements:\n{algX_elem_list}")Extended_Linear_Interval_AlgebraExtension of Allen's algebra to include points and intervalsThis algebra has the following 18 elements:B, BI, D, DI, E, F, FI, M, MI, O, OI, PE, PF, PFI, PS, PSI, S, SI
Figure 1, below, from Reich1994,shows the domain and range modifications to the original 13 relations.The subscripts on the temporal entities, X and Y, indicate that they canbe proper intervals (“i”) or points (“p”) or both (“ip”). Where thesubscript is “i” alone for both domain and range (X & Y) the originalrelations are unchanged.
from IPython.display import Image # Only needed to display figures hereImage(filename='../docs/_static/Extension_of_Allens_Interval_Relations.png', width="400")
The 5 additional relations needed to integrate Points with Intervals areshown in Figure 2, below. The meaning of the subscripts remains the sameas above.
Image(filename='../docs/_static/Point_Interval_Relations.png', width="400")
>>> algX.summary()
Algebra Name: Extended_Linear_Interval_Algebra Description: Extension of Allen's algebra to include points and intervals Equality Rels: E|PE Relations: NAME (SYMBOL) CONVERSE (ABBREV) REFLEXIVE SYMMETRIC TRANSITIVE DOMAIN RANGE Before ( B) After ( BI) False False True Pt|PInt Pt|PInt After ( BI) Before ( B) False False True Pt|PInt Pt|PInt During ( D) Contains ( DI) False False True Pt|PInt PInt Contains ( DI) During ( D) False False True PInt Pt|PInt Equals ( E) Equals ( E) True True True PInt PInt Finishes ( F) Finished-by ( FI) False False True PInt PInt Finished-by ( FI) Finishes ( F) False False True PInt PInt Meets ( M) Met-By ( MI) False False False PInt PInt Met-By ( MI) Meets ( M) False False False PInt PInt Overlaps ( O) Overlapped-By ( OI) False False False PInt PInt Overlapped-By ( OI) Overlaps ( O) False False False PInt PInt Point-Equals ( PE) Point-Equals ( PE) True True True Pt Pt Point-Finishes ( PF) Point-Finished-By (PFI) False False False Pt PInt Point-Finished-By (PFI) Point-Finishes ( PF) False False False PInt Pt Point-Starts ( PS) Point-Started-By (PSI) False False False Pt PInt Point-Started-By (PSI) Point-Starts ( PS) False False False PInt Pt Starts ( S) Started-By ( SI) False False True PInt PInt Started-By ( SI) Starts ( S) False False True PInt PIntDomain & Range Abbreviations: Pt = Point PInt = Proper Interval
Equality Relations
The number and type of equality relations in an algebra depends on thenumber and type of entities (e.g., ‘Point’, ‘ProperInterval’) related byrelations in the algebra.
The Extended Linear Interval Algebra supports both ProperIntervals andPoints.
>>> print(f"\n{algX.name}")>>> print(f"Set of all equality relations: {algX.all_equality_relations}")>>> for eq_rel in algX.all_equality_relations: print(50*"-") algX.element_summary(eq_rel)>>> print(50*"-")Extended_Linear_Interval_AlgebraSet of all equality relations: E|PE-------------------------------------------------- Symbol: E Name: Equals Domain: ['ProperInterval'] Range: ['ProperInterval'] Converse: Equals Is Reflexive?: True Is Symmetric?: True Is Transitive?: TrueIs an Equality Relation?: True-------------------------------------------------- Symbol: PE Name: Point-Equals Domain: ['Point'] Range: ['Point'] Converse: Point-Equals Is Reflexive?: True Is Symmetric?: True Is Transitive?: TrueIs an Equality Relation?: True--------------------------------------------------
Check Composition Identity
If \(r\) and \(s\) are two relations, then\(!(r;s) = (!s);(!r)\)
The check_composition_identity Algebra method checks every possiblepairing of individual algebra relations wrt the composition identity,and returns True if all pairs check out.
>>> print(f"There are {algX_num_elements**2} ({algX_num_elements}x{algX_num_elements}) possible compositions.")>>> algX.check_composition_identity(verbose=True)There are 324 (18x18) possible compositions.Extended_Linear_Interval_Algebra -- Composition Identity Check:PASSED . 324 products tested.
TrueCheck Associativity
The is_associative Algebra method checks all possible triples ofindividual algebra relations and, if the domains and ranges are“compatible”, checks to see if the triple is associative. Incompatibletriples are skipped. It returns True if all compatible triples areassociative.
>>> print(f"\n{algX.name}:")>>> print(f"There are {algX_num_elements}^3 = {algX_num_elements**3} ways we can combine the algebra's elements to test associativity.\n")>>> algX.is_associative()Extended_Linear_Interval_Algebra:There are 18^3 = 5832 ways we can combine the algebra's elements to test associativity.TEST SUMMARY: 3609 OK, 2223 Skipped, 0 Failed (5832 Total)
True2. Right-Branching Interval and Point Algebra
In [Reich,1994],the Linear Interval and Point Algebra described above was furtherextended to support Branching Time. Both Right-Branching Time andLeft-Branching Time are possible, but not both together at the sametime.
Figure 9 from [Reich,1994]depicts the 6 new relations required to support Right-Branching Time, inaddition to the 18 described above.
# Instantiate algebra and print some basic info about it>>> algR = qr.Algebra(os.path.join(path, "Algebras/Right_Branching_Interval_Algebra.json"))>>> print(algR.name)>>> print(algR.description)>>> algR_num_elements = len(algR.elements)>>> algR_elem_list = ', '.join(str(algR.elements).split("|"))>>> print(f"This algebra has the following {algR_num_elements} elements:\n{algR_elem_list}")Right_Branching_Interval_AlgebraReich's right-branching extension to Allen's time interval algebra (see TIME-94 paper)This algebra has the following 24 elements:B, BI, D, DI, E, F, FI, M, MI, O, OI, PE, PF, PFI, PS, PSI, RB, RBI, RO, ROI, RS, R~, S, SI
Image(filename='../docs/_static/Right_Branching_Time_Relations.png', width="400")
>>> algR.summary()
Algebra Name: Right_Branching_Interval_Algebra Description: Reich's right-branching extension to Allen's time interval algebra (see TIME-94 paper) Equality Rels: E|PE Relations: NAME (SYMBOL) CONVERSE (ABBREV) REFLEXIVE SYMMETRIC TRANSITIVE DOMAIN RANGE Before ( B) After ( BI) False False True Pt|PInt Pt|PInt After ( BI) Before ( B) False False True Pt|PInt Pt|PInt During ( D) Contains ( DI) False False True Pt|PInt PInt Contains ( DI) During ( D) False False True PInt Pt|PInt Equals ( E) Equals ( E) True True True PInt PInt Finishes ( F) Finished-by ( FI) False False True PInt PInt Finished-by ( FI) Finishes ( F) False False True PInt PInt Meets ( M) Met-By ( MI) False False False PInt PInt Met-By ( MI) Meets ( M) False False False PInt PInt Overlaps ( O) Overlapped-By ( OI) False False False PInt PInt Overlapped-By ( OI) Overlaps ( O) False False False PInt PInt Point-Equals ( PE) Point-Equals ( PE) True True True Pt Pt Point-Finishes ( PF) Point-Finished-By (PFI) False False False Pt PInt Point-Finished-By (PFI) Point-Finishes ( PF) False False False PInt Pt Point-Starts ( PS) Point-Started-By (PSI) False False False Pt PInt Point-Started-By (PSI) Point-Starts ( PS) False False False PInt Pt Right-Before ( RB) Right-After (RBI) False False True PInt Pt|PInt Right-After (RBI) Right-Before ( RB) False False True Pt|PInt PInt Right-Overlaps ( RO) Right-Overlapped-By (ROI) False False False PInt PIntRight-Overlapped-By (ROI) Right-Overlaps ( RO) False False False PInt PInt Right-Starts ( RS) Right-Starts ( RS) False True False PInt PInt Right-Incomparable ( R~) Right-Incomparable ( R~) False True False Pt|PInt Pt|PInt Starts ( S) Started-By ( SI) False False True PInt PInt Started-By ( SI) Starts ( S) False False True PInt PIntDomain & Range Abbreviations: Pt = Point PInt = Proper Interval
3. Left-Branching Interval and Point Algebra
Figure 10 from [Reich,1994]depicts the 6 new relations required to support Left-Branching Time, inaddition to the 18 described, above, for the Extended Linear IntervalAlgebra.
# Instantiate algebra and print some basic info about it>>> algL = qr.Algebra(os.path.join(path, "Algebras/Left_Branching_Interval_Algebra.json"))>>> print(algL.name)>>> print(algL.description)>>> algL_num_elements = len(algL.elements)>>> algL_elem_list = ', '.join(str(algL.elements).split("|"))>>> print(f"This algebra has the following {algL_num_elements} elements:\n{algL_elem_list}")Left_Branching_Interval_AlgebraReich's left-branching extension to Allen's time interval algebra (see TIME-94 paper)This algebra has the following 24 elements:B, BI, D, DI, E, F, FI, LB, LBI, LF, LO, LOI, L~, M, MI, O, OI, PE, PF, PFI, PS, PSI, S, SI
Image(filename='../docs/_static/Left_Branching_Time_Relations.png', width="400")
>>> algL.summary()
Algebra Name: Left_Branching_Interval_Algebra Description: Reich's left-branching extension to Allen's time interval algebra (see TIME-94 paper) Equality Rels: E|PE Relations: NAME (SYMBOL) CONVERSE (ABBREV) REFLEXIVE SYMMETRIC TRANSITIVE DOMAIN RANGE Before ( B) After ( BI) False False True Pt|PInt Pt|PInt After ( BI) Before ( B) False False True Pt|PInt Pt|PInt During ( D) Contains ( DI) False False True Pt|PInt PInt Contains ( DI) During ( D) False False True PInt Pt|PInt Equals ( E) Equals ( E) True True True PInt PInt Finishes ( F) Finished-by ( FI) False False True PInt PInt Finished-by ( FI) Finishes ( F) False False True PInt PInt Left-Before ( LB) Left-After (LBI) False False True Pt|PInt PInt Left-After (LBI) Left-Before ( LB) False False True PInt Pt|PInt Left-Finishes ( LF) Left-Finishes ( LF) False True False PInt PInt Left-Overlaps ( LO) Left-Overlapped-By (LOI) False False False PInt PInt Left-Overlapped-By (LOI) Left-Overlaps ( LO) False False False PInt PInt Left-Incomparable ( L~) Left-Incomparable ( L~) False True False Pt|PInt Pt|PInt Meets ( M) Met-By ( MI) False False False PInt PInt Met-By ( MI) Meets ( M) False False False PInt PInt Overlaps ( O) Overlapped-By ( OI) False False False PInt PInt Overlapped-By ( OI) Overlaps ( O) False False False PInt PInt Point-Equals ( PE) Point-Equals ( PE) True True True Pt Pt Point-Finishes ( PF) Point-Finished-By (PFI) False False False Pt PInt Point-Finished-By (PFI) Point-Finishes ( PF) False False False PInt Pt Point-Starts ( PS) Point-Started-By (PSI) False False False Pt PInt Point-Started-By (PSI) Point-Starts ( PS) False False False PInt Pt Starts ( S) Started-By ( SI) False False True PInt PInt Started-By ( SI) Starts ( S) False False True PInt PIntDomain & Range Abbreviations: Pt = Point PInt = Proper Interval
Pick one of the algebras to use for examples
>>> alg = algR # Other choices are algX & algL
Algebra Element Summary
A domain (or range) of [‘Point’, ‘ProperInterval’] means that theTemporal Entity being related can be a ‘Point’ or a ‘ProperInterval’,but not both at the same time.
Here are a few element summaries:
>>> from random import sample>>> sample_size = 3>>> for element in sample(list(alg.elements), sample_size): alg.element_summary(element) print("\n")Symbol: PF Name: Point-Finishes Domain: ['Point'] Range: ['ProperInterval'] Converse: Point-Finished-By Is Reflexive?: False Is Symmetric?: False Is Transitive?: FalseIs an Equality Relation?: False Symbol: ROI Name: Right-Overlapped-By Domain: ['ProperInterval'] Range: ['ProperInterval'] Converse: Right-Overlaps Is Reflexive?: False Is Symmetric?: False Is Transitive?: FalseIs an Equality Relation?: False Symbol: PS Name: Point-Starts Domain: ['Point'] Range: ['ProperInterval'] Converse: Point-Started-By Is Reflexive?: False Is Symmetric?: False Is Transitive?: FalseIs an Equality Relation?: False
Equality Relations
The number and type of equality relations in an algebra depends on thenumber and type of domains and ranges supported by the algebra. (e.g.,‘Point’, ‘ProperInterval’, or both)
>>> print(f"\n{alg.description}")>>> print(f"Set of all equality relations: {alg.all_equality_relations}")Reich's right-branching extension to Allen's time interval algebra (see TIME-94 paper)Set of all equality relations: E|PE
Here are element summaries of the algebra’s equality relations:
>>> for eq_rel in alg.all_equality_relations: print(50*"-") print(f"{eq_rel}:") alg.element_summary(eq_rel)>>> print(50*"-")--------------------------------------------------E: Symbol: E Name: Equals Domain: ['ProperInterval'] Range: ['ProperInterval'] Converse: Equals Is Reflexive?: True Is Symmetric?: True Is Transitive?: TrueIs an Equality Relation?: True--------------------------------------------------PE: Symbol: PE Name: Point-Equals Domain: ['Point'] Range: ['Point'] Converse: Point-Equals Is Reflexive?: True Is Symmetric?: True Is Transitive?: TrueIs an Equality Relation?: True--------------------------------------------------
Creating Relation Sets
There are two acceptable input formats for creating relation sets:
>>> relset_version1 = alg.relset("B|M|FI")>>> relset_version2 = alg.relset(['B', 'FI', 'M'])>>> print(relset_version1)>>> print(relset_version2)>>> print(f"Same? {relset_version1 == relset_version2}")B|FI|MB|FI|MSame? True
Singleton sets can also be created in two ways:
>>> singleton_relset_v1 = alg.relset("B")>>> singleton_relset_v2 = alg.relset(["B"])>>> print(singleton_relset_v1)>>> print(singleton_relset_v2)>>> print(f"Same? {singleton_relset_v1 == singleton_relset_v2}")BBSame? True
And, there are two ways the empty set can be created:
>>> empty_relset_v1 = alg.relset("")>>> empty_relset_v2 = alg.relset([])>>> print(empty_relset_v1) # Nothing will printout here.>>> print(empty_relset_v2) # Nor here.>>> print(f"Same? {empty_relset_v1 == empty_relset_v2}")>>> empty_relset_v1 # Just so we can see something that looks empty...Same? True
relset()
Operations on Relation Sets
Addition
Addition (+) is set intersection:
>>> alg.relset('B|M|O') + alg.relset('F|O|M|S')relset(['M', 'O'])
>>> alg.relset('B|M|O') + alg.relset('F|S')relset()
Composition
Composition, sometimes referred to as “multiplication”, is relationcomposition applied to sets of relations.(https://en.wikipedia.org/wiki/Composition_of_relations)
Loosely speaking, let \(\rho, \sigma, \tau\) be relation sets, then\(\rho ; \sigma = \tau\), if, by transitivity,\((A \rho B) \wedge (B \sigma C) \Rightarrow (A \tau C)\).
The transitivity table in the algebra’s JSON definition file describeshow singleton relation sets compose with each other. When more than onerelation appears in a set, the result of composition is the union of allpairwise compositions of the individual relations in the sets.
For example, below, we calculate (F|MI);(O|D) and then break it downinto 4 different compositions involving single relations, representingthe pairwise compositions of F|MI and O|D:
>>> rel1 = "F">>> rel2= "O">>> rel3 = "MI">>> rel4 = "D">>> print(f"({rel1}|{rel3});({rel2}|{rel4}) = {alg.compose(alg.relset('F|MI'), alg.relset('O|D'))}")(F|MI);(O|D) = D|F|O|OI|ROI|S
>>> print(f"{rel1};{rel2} = {alg.compose(alg.relset(rel1), alg.relset(rel2))}")>>> print(f"{rel1};{rel4} = {alg.compose(alg.relset(rel1), alg.relset(rel4))}")>>> print(f"{rel3};{rel2} = {alg.compose(alg.relset(rel3), alg.relset(rel2))}")>>> print(f"{rel3};{rel4} = {alg.compose(alg.relset(rel3), alg.relset(rel4))}")F;O = D|O|SF;D = DMI;O = D|F|OI|ROIMI;D = D|F|OI|ROI
Some Compositions Will Result in the Empty Set
Not every composition of relations makes sense, in which case, theresult will be the empty relation set.
For example, consider the relations F and PF in the Extended IntervalAlgebra. Their properties are shown below.
Note that the range of F is ‘ProperInterval’, whereas the domain of PFis ‘Point’.
>>> alg.element_summary("F")>>> print("\n")>>> alg.element_summary("PF")Symbol: F Name: Finishes Domain: ['ProperInterval'] Range: ['ProperInterval'] Converse: Finished-by Is Reflexive?: False Is Symmetric?: False Is Transitive?: TrueIs an Equality Relation?: False Symbol: PF Name: Point-Finishes Domain: ['Point'] Range: ['ProperInterval'] Converse: Point-Finished-By Is Reflexive?: False Is Symmetric?: False Is Transitive?: FalseIs an Equality Relation?: False
if A, B, and C are Temporal Entities, then:
the expression (A Finishes B) implies that B is a Proper Interval
the expression (B Point-Finishes C) implies that B is a Point
Since B cannot be both a Point and a Proper Interval, the composition,F;PF, results in the empty set, as shown below:
>>> alg.compose(alg.relset("F"), alg.relset("PF"))relset()
Converses
NOTATION: Here, we’ll denote the converse operation with “!”. So, if\(A\) and \(B\) are Temporal Entities, and \(r\) is arelation between them, then \(!r\) is its converse relation, so,\(A r B\) if and only if \(B !r A\). For example, “A before B”if and only if “B after A”.
Individual relations have converses:
>>> rel_symbol = 'B'>>> print(f"The converse of {alg.rel_name(rel_symbol)} is {alg.rel_converse_name(rel_symbol)}")The converse of Before is After
And relation sets also have converses:
>>> print(f"!{alg.relset(rel_symbol)} = {alg.converse(alg.relset(rel_symbol))}")>>> print(f"!({alg.converse(relset_version1)}) = {relset_version1}")!B = BI!(BI|F|MI) = B|FI|M
Complement of a Relation Set
The complement of a relation set, R, is the set of all relation elementsthat are not in R.
We’ll use ~R to denote the complement of R.
>>> R = alg.relset('B|BI|D|DI|E|F|FI|M|MI|O|OI')>>> compR = R.complement()>>> print(f"\nAll Elements = {alg.elements}")>>> print(f" R = {R}")>>> print(f" ~R = {compR}")>>> print(f" ~(~R) = {compR.complement()}")All Elements = B|BI|D|DI|E|F|FI|M|MI|O|OI|PE|PF|PFI|PS|PSI|RB|RBI|RO|ROI|RS|R~|S|SI R = B|BI|D|DI|E|F|FI|M|MI|O|OI ~R = PE|PF|PFI|PS|PSI|RB|RBI|RO|ROI|RS|R~|S|SI ~(~R) = B|BI|D|DI|E|F|FI|M|MI|O|OI
Global Properties of an Algebra of Relations
There are two properties of an Algebra that are true for all applicableelements in the algebra:
The Composition Identity; true for all elements
Associativity; true when domains & ranges are compatible, undefinedotherwise. See the section on Domain-Range Compatibility, below.
Composition Identity
If \(r\) and \(s\) are two relations, then\(!(r;s) = (!s);(!r)\)
Here’s an example:
>>> r = alg.relset("O")>>> s = alg.relset("F")>>> conv_comp_r_s = alg.converse(alg.compose(r, s))>>> print(f"!({r};{s}) = {conv_comp_r_s}")>>> comp_conv_s_conv_r = alg.compose(alg.converse(s), alg.converse(r))>>> print(f"!{s};!{r} = {comp_conv_s_conv_r}")>>> print(f"Same? {conv_comp_r_s == comp_conv_s_conv_r}")!(O;F) = DI|OI|SI!F;!O = DI|OI|SISame? True
The check_composition_identity Algebra method checks every possiblepairing of individual algebra relations wrt the composition identity,and returns True if all pairs check out.
>>> alg.check_composition_identity(verbose=True)
Right_Branching_Interval_Algebra -- Composition Identity Check:PASSED . 576 products tested.
TrueAssociativity
The is_associative Algebra method checks all possible triples ofindividual algebra relations and, if the domains and ranges are“compatible”, checks to see if the triple is associative. Incompatibletriples are skipped. It returns True if all compatible triples areassociative.
>>> num_elements = len(alg.elements)>>> print(f"There are {num_elements}^3 = {num_elements**3} ways we can combine the algebra's elements to test associativity.")There are 24^3 = 13824 ways we can combine the algebra's elements to test associativity.
The following method tests all of those ways, skipping the ones thatdon’t make sense due to range-domain mismatches.
>>> alg.is_associative()
TEST SUMMARY: 9772 OK, 4052 Skipped, 0 Failed (13824 Total)
TrueDomain-Range Compatibility:
The following comment from the source code describes how domains andranges make some compositions of relations impossible to compute(“incompatible”). This occurs, for example, in the extensions to Allen’salgebra found in the paper by Reich,1994,where ProperIntervals and Points are integrated.
# All relations have a domain and a range. If D1, R1, D2, and R2 are the domains and ranges# of relations r1 & r2, resp., then the composition of r1 and r2 (written r1;r2 in algebraic# logic literature) requires that the intersection of R1 and D2 be non-empty. To see why,# consider what the composition means wrt the associated Temporal Entities, teA, teB, and# teC, where (teA r1 teB) and (teB r2 teC). The ontological classes that teB belongs to# must include the range of r1 (R1) and the domain of r2 (D2) for r1;r2 to make sense.## r1 r2# teA -----> teB -----> teC# D1 R1,D2 R2# | ^# | |# +--------------------+# r1;r2## Matrix multiplication, M x N, provides an analogy: the number of columns of M must# match the number of rows of N.