<jupyter_start><jupyter_text>Intro 1: Allen's Algebra of Proper Time Intervals "Allen's interval algebra is a calculus for temporal reasoning that was introduced by <NAME> in 1983. The calculus defines possible relations between time intervals and provides a composition table that can be used as a basis for reasoning about temporal descriptions of events." -- [Wikipedia](https://en.wikipedia.org/wiki/Allen%27s_interval_algebra)Allen's algebra is based on the 13 possible ways that proper time intervals can be related to each other, as shown in the following [figure from Wikipedia](https://en.wikipedia.org/wiki/Allen%27s_interval_algebraRelations)(Note: A few of the relation symbols in this notebook differ from those in the figure: B instead of , and E instead of =):  References 1. ["Maintaining Knowledge about Temporal Intervals" by <NAME>](https://cse.unl.edu/~choueiry/Documents/Allen-CACM1983.pdf) - Allen's original paper (PDF)1. [Allen's Interval Algebra](https://www.ics.uci.edu/~alspaugh/cls/shr/allen.html) or [here](https://thomasalspaugh.org/pub/fnd/allen.html) - summarizes Allen's algebra of proper time intervals1. ["Intervals, Points, and Branching Time" by <NAME>](https://www.researchgate.net/publication/220810644_Intervals_Points_and_Branching_Time) - basis for the extensions to Allen's algebra  Dependencies<jupyter_code>import qualreas as qr
import os
path = os.path.join(os.getenv('PYPROJ'), 'qualreas')<jupyter_output><empty_output><jupyter_text>Instantiate an Algebra Algebras are defined in JSON format.  The definition of Allen's algebra of proper time intervals, published in 1983, is a "Linear Interval Algebra" and is instantiated as follows:<jupyter_code>alg = qr.Algebra(os.path.join(path, "Algebras/Linear_Interval_Algebra.json"))<jupyter_output><empty_output><jupyter_text>Algebra Summary Two important aspects of an algebra are defined in the JSON file that was loaded above:1. The algebra's set of relations and their properties1. The algebra's composition or transitivity table (called TransTable in the JSON file)The first of these aspects, the set of relations, is described by the Algebra's summary method, as shown below.Composition/Transitivity tables are used to implement the Algebra's compose method, and are generally too large to print out.  (Note: Composition is often referred to as "multiplication".)<jupyter_code>alg.summary()<jupyter_output>Algebra Name: Linear_Interval_Algebra
   Description: Allen's algebra of proper time intervals (w/ new trans table format)
 Equality Rels: E
     Relations:
            NAME (SYMBOL)         CONVERSE (ABBREV)  REFLEXIVE  SYMMETRIC TRANSITIVE   DOMAIN        RANGE
             Before (  B)               After ( BI)    False      False       True       PInt          PInt
              After ( BI)              Before (  B)    False      False       True       PInt          PInt
             During (  D)            Contains ( DI)    False      False       True       PInt          PInt
           Contains ( DI)              During (  D)    False      False       True       PInt          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    [...]<jupyter_text>Algebra Element Summary Here are a few random individual element summaries:<jupyter_code>from random import sample

sample_size = 3

for element in sample(list(alg.elements), sample_size):
    print(50*"-")
    alg.element_summary(element)
print(50*"-")<jupyter_output>--------------------------------------------------
                  Symbol: D
                    Name: During
                  Domain: ['ProperInterval']
                   Range: ['ProperInterval']
                Converse: Contains
           Is Reflexive?: False
           Is Symmetric?: False
          Is Transitive?: True
Is an Equality Relation?: False
--------------------------------------------------
                  Symbol: O
                    Name: Overlaps
                  Domain: ['ProperInterval']
                   Range: ['ProperInterval']
                Converse: Overlapped-By
           Is Reflexive?: False
           Is Symmetric?: False
          Is Transitive?: False
Is an Equality Relation?: False
--------------------------------------------------
                  Symbol: S
                    Name: Starts
                  Domain: ['ProperInterval']
                   Range: ['ProperInterval']
                Converse: Started-By
           Is Reflexive?:[...]<jupyter_text>Equality Relations The number and type of equality relations in an algebra depends on the number and type of entities (e.g., 'Point', 'ProperInterval') related by relations in the algebra.<jupyter_code>print(f"\n{alg.description}")
print(f"has the following Equality Relation(s): {alg.all_equality_relations}")<jupyter_output>Allen's algebra of proper time intervals (w/ new trans table format)
has the following Equality Relation(s): E<jupyter_text>Allen's algebra has only one equality relation because the domains and ranges of the relations are only of one type, ProperInterval.Here is the element summary of Allen's equality relation:<jupyter_code>for eq_rel in alg.all_equality_relations:
    print(50*"-")
    alg.element_summary(eq_rel)
print(50*"-")<jupyter_output>--------------------------------------------------
                  Symbol: E
                    Name: Equals
                  Domain: ['ProperInterval']
                   Range: ['ProperInterval']
                Converse: Equals
           Is Reflexive?: True
           Is Symmetric?: True
          Is Transitive?: True
Is an Equality Relation?: True
--------------------------------------------------<jupyter_text>Creating Relation Sets A set of relations ("relset") represents a disjunction.For example, if $r_1, r_2, r_3$ are relations, and $A$ & $B$ are proper time intervals, then:$ A \{r_1,r_2,r_3\} B \Leftrightarrow (A r_1 B) \vee (A r_2 B) \vee (A r_3 B)$ There are two acceptable input formats for creating relation sets, the first of which, shown below, is also the print representation of a relset:<jupyter_code>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}")<jupyter_output>B|FI|M
B|FI|M
Same? True<jupyter_text>Singleton sets can also be created in two ways:<jupyter_code>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}")<jupyter_output>B
B
Same? True<jupyter_text>And, there are two ways the empty set can be created:<jupyter_code>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...<jupyter_output>Same? True<jupyter_text>Operations on Relation Sets  Addition Addition (+) is set intersection:<jupyter_code>alg.relset('B|M|O') + alg.relset('F|O|M|S')
alg.relset('B|M|O') + alg.relset('F|S')<jupyter_output><empty_output><jupyter_text>Composition Composition, sometimes referred to as "multiplication", is relation composition 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 describes how singleton relation sets compose with each other.  When more than one relation appears in a set, the result of composition is the union of all pairwise compositions of the individual relations in the sets.For example, below, we calculate (F|MI);(O|D) and then break it down into 4 different compositions involving single relations, representing the pairwise compositions of F|MI and O|D:<jupyter_code>rel1 = "F"
rel2 = "O"
rel3 = "MI"
rel4 = "D"

print(f"({rel1}|{rel3});({rel2}|{rel4}) = {alg.compose(alg.relset('F|MI'), alg.relset('O|D'))}")
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))}")<jupyter_output>F;O = D|O|S
F;D = D
MI;O = D|F|OI
MI;D = D|F|OI<jupyter_text>Converses NOTATION:  Here, we'll denote the converse operation with "!".  So, if $A$ and $B$ are Temporal Entities, and $r$ is a relation between them, then $!r$ is its converse relation.Thus, $A r B \Leftrightarrow B !r A$.  For example, "A before B" if and only if "B after A". Individual relations have converses:<jupyter_code>rel_symbol = 'B'
print(f"The converse of {alg.rel_name(rel_symbol)} is {alg.rel_converse_name(rel_symbol)}")<jupyter_output>The converse of Before is After<jupyter_text>And relation sets also have converses:<jupyter_code>print(f"!{alg.relset(rel_symbol)} = {alg.converse(alg.relset(rel_symbol))}")
print(f"!({alg.converse(relset_version1)}) = {relset_version1}")<jupyter_output>!B = BI
!(BI|F|MI) = B|FI|M<jupyter_text>Complement of a Relation Set The complement of a relation set, R, is the set of all relation elements that are not in R.We'll use ~R to denote the complement of R.<jupyter_code>R = alg.relset('B|BI|D|DI|E|F|FI')
compR = R.complement()

print(f"\nAll Elements = {alg.elements}")
print(f"          R  = {R}")
print(f"         ~R  =                  {compR}")
print(f"       ~(~R) = {compR.complement()}")<jupyter_output>All Elements = B|BI|D|DI|E|F|FI|M|MI|O|OI|S|SI
          R  = B|BI|D|DI|E|F|FI
         ~R  =                  M|MI|O|OI|S|SI
       ~(~R) = B|BI|D|DI|E|F|FI<jupyter_text>Global Properties of an Algebra of Relations There are two properties of an Algebra that are true for all "applicable" elements in the algebra:* The Composition Identity* Associativity, when domains & ranges permit  Composition Identity If $r$ and $s$ are two relations, then $!(r;s) = (!s);(!r)$ Here's an example:<jupyter_code>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}")<jupyter_output>!(O;F) = DI|OI|SI
!F;!O = DI|OI|SI
Same? True<jupyter_text>The check_composition_identity Algebra method checks every possible pairing of individual algebra relations wrt the composition identity, and returns True if all pairs check out.<jupyter_code>alg.check_composition_identity(verbose=True)<jupyter_output>Linear_Interval_Algebra -- Composition Identity Check:
PASSED . 169 products tested.<jupyter_text>Associativity The is_associative Algebra method checks all possible triples of individual algebra relations and, if the domains and ranges are "compatible", checks to see if the triple is associative.  Incompatible triples are skipped.  It returns True if all compatible triples are associative.  Since the relations in Allen's algebra only relate one type of entity, "ProperInterval", there are no relation pairings that are incompatible with respect to composition.<jupyter_code>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.")<jupyter_output>There are 13^3 = 2197 ways we can combine the algebra's elements to test associativity.<jupyter_text>The following method tests all of those ways, skipping the ones that don't make sense due to range-domain mismatches.<jupyter_code>alg.is_associative()<jupyter_output>TEST SUMMARY: 2197 OK, 0 Skipped, 0 Failed (2197 Total)<jupyter_text>The following comment from the source code describes how domains and ranges make some compositions of relations impossible to compute ("incompatible"). This occurs, for example, in the extensions to Allen's algebra found in the paper by [Reich, 1994](https://www.researchgate.net/publication/220810644_Intervals_Points_and_Branching_Time), where ProperIntervals and Points are integrated.<jupyter_code># 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.<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12103703703703704, 'fraction_numerical': 0.011851851851851851, 'mean_word_length': 3.3593800452050373, 'pattern_counts': {'":': 0, '<': 65, '<?xml version=': 0, '>': 67, 'https://': 8, 'lorem ipsum': 0, 'www.': 3, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '19', 'dir': 'jupyter-structured-clean-dedup', 'id': '98756', 'license': 'MIT', 'n_tokens_mistral': 4285, 'n_tokens_neox': 4075, 'n_words': 1340, 'path': 'Notebooks/Intro1_Allens_Interval_Algebra.ipynb', 'repo_name': 'alreich/qualreas', 'size': '13520'}