Intervals Chain

An intervals chain is an n-tuple of natural numbers that represents the distance between equal elements in a sequence, if and only if there is an operation that takes as an input current \((index, interval)\) and returns the next index. The operation makes the intervals chained to each other, which is a required condition for the existence reverse function that restores by intervals chain a sequence with the same with the original sequence order.

The idea of intervals chain is easy to explain by a concrete example:

From a sequencewith a bindingget correspoding indexesand calculate intervals chain

block-beta
    columns 8
    space        p1["1"] space:3         p5["5"]                p6["n"] space
    space s1["A"] s2["C"] s3["T"] s4["C"] s5["A"] s6["G"] space

    classDef imaginary fill:#526cfe09,color:#000,stroke-dasharray: 10 5;
    classDef position fill:#fff,color:#000,stroke-width:0px;
    class inf,sup imaginary
    class p0,p1,p5,p6,p7 position

    classDef c1 fill:#ff7f0e,color:#fff;
    classDef c2 fill:#ffbb78,color:#000;
    classDef c2a fill:#ffbb788a,color:#000;
    classDef c3 fill:#2ca02c,color:#fff;
    classDef c4 fill:#98df8a,color:#000;
    classDef c4a fill:#98df8a8a,color:#000;
    classDef c5 fill:#d62728,color:#fff;
    classDef c6 fill:#ff9896,color:#000;
    classDef c6a fill:#ff98968a,color:#000;
    classDef c7 fill:#9467bd,color:#fff;
    classDef c8 fill:#c5b0d5,color:#000;
    classDef c9 fill:#8c564b,color:#fff;
    classDef c10 fill:#c49c94,color:#000;
    classDef c11 fill:#e377c2,color:#fff;
    classDef c12 fill:#f7b6d2,color:#000;
    classDef c13 fill:#bcbd22,color:#fff;
    classDef c14 fill:#dbdb8d,color:#000;
    classDef c14a fill:#dbdb8d8a,color:#000;
    classDef c15 fill:#17becf,color:#fff;
    classDef c16 fill:#9edae5,color:#000;

Let there be a sequence length of \(n=6\) (indexed from 1 to n=6)

block-beta
  columns 7
  p0["0"]        p1["1"] space:3         p5["5"]                p6["6"]
  inf["⊥"] s1["A"] s2["C"] s3["T"] s4["C"] s5["A"] s6["G"]
  e0["0 = Iterator(1)"]:2 space:5
  space      t1["1 = Iterator(5)"]:5         space

  classDef imaginary fill:#526cfe09,color:#000,stroke-dasharray: 10 5;
  classDef position fill:#fff,color:#000,stroke-width:0px;
  class inf,sup imaginary
  class p0,p1,p5,p6,p7 position

  classDef c1 fill:#ff7f0e,color:#fff;
  classDef c2 fill:#ffbb78,color:#000;
  classDef c2a fill:#ffbb788a,color:#000;
  classDef c3 fill:#2ca02c,color:#fff;
  classDef c4 fill:#98df8a,color:#000;
  classDef c4a fill:#98df8a8a,color:#000;
  classDef c5 fill:#d62728,color:#fff;
  classDef c6 fill:#ff9896,color:#000;
  classDef c6a fill:#ff98968a,color:#000;
  classDef c7 fill:#9467bd,color:#fff;
  classDef c8 fill:#c5b0d5,color:#000;
  classDef c9 fill:#8c564b,color:#fff;
  classDef c10 fill:#c49c94,color:#000;
  classDef c11 fill:#e377c2,color:#fff;
  classDef c12 fill:#f7b6d2,color:#000;
  classDef c13 fill:#bcbd22,color:#fff;
  classDef c14 fill:#dbdb8d,color:#000;
  classDef c14a fill:#dbdb8d8a,color:#000;
  classDef c15 fill:#17becf,color:#fff;
  classDef c16 fill:#9edae5,color:#000;

  class s1,s5 c4
  class inf,t1,e0 c4a
  class pomn,p00,p01,p06,p07,p02n position
  class t1,t2,t5,e0,e1 position

Define Binding as a pair of an Iterator function, that seeks a corresponding referenced element, and set of terminate states, to determine the interval when there is no matching element in the sequence.

In the example, Iterator seeks a position of a previous equivalent element as a matching reference. If there is no such element, it returns \(0\). That means terminate states set is \(\bot = {0}\). This particular method is called - Start binding.

block-beta
  columns 7
  p0["0"]  p1["1"] p2["2"] p3["3"] p4["4"] p5["5"] p6["6"]
  inf["⊥"] s1["A"] s2["C"] s3["T"] s4["C"] s5["A"] s6["G"]
  space i1["0"] i2["0"] i3["0"] i4["2"] i5["1"] i6["0"]

  classDef imaginary fill:#526cfe09,color:#000,stroke-dasharray: 10 5;
  classDef position fill:#fff,color:#000,stroke-width:0px;
  class inf,sup imaginary
  class p0,p1,p2,p3,p4,p5,p6,p7 position

  classDef c1 fill:#ff7f0e,color:#fff;
  classDef c2 fill:#ffbb78,color:#000;
  classDef c2a fill:#ffbb788a,color:#000;
  classDef c3 fill:#2ca02c,color:#fff;
  classDef c4 fill:#98df8a,color:#000;
  classDef c4a fill:#98df8a8a,color:#000;
  classDef c5 fill:#d62728,color:#fff;
  classDef c6 fill:#ff9896,color:#000;
  classDef c6a fill:#ff98968a,color:#000;
  classDef c7 fill:#9467bd,color:#fff;
  classDef c8 fill:#c5b0d5,color:#000;
  classDef c9 fill:#8c564b,color:#fff;
  classDef c10 fill:#c49c94,color:#000;
  classDef c11 fill:#e377c2,color:#fff;
  classDef c12 fill:#f7b6d2,color:#000;
  classDef c13 fill:#bcbd22,color:#fff;
  classDef c14 fill:#dbdb8d,color:#000;
  classDef c14a fill:#dbdb8d8a,color:#000;
  classDef c15 fill:#17becf,color:#fff;
  classDef c16 fill:#9edae5,color:#000;

  class s1,s5,i1,i5 c4
  class s2,s4,i2,i4 c1
  class s3,i3 c5
  class s6,i6 c7
  class pomn,p00,p01,p06,p07,p02n position
  class t1,t2,t5,e0,e1 position

With Binding we can get a sequence of corresponding indexes. For all first appearances of the elements it would be \(0\), and for C at position 4 corresponding index would be 2, for A at position 5 - 1.

block-beta
  columns 7
  p0["0"]  p1["1"] p2["2"] p3["3"] p4["4"] p5["5"] p6["6"]
  space i1["0"] i2["0"] i3["0"] i4["2"] i5["1"] i6["0"]
  space s1["1"] s2["2"] s3["3"] s4["2"] s5["4"] s6["6"]

  classDef imaginary fill:#526cfe09,color:#000,stroke-dasharray: 10 5;
  classDef position fill:#fff,color:#000,stroke-width:0px;
  class inf,sup imaginary
  class p0,p1,p2,p3,p4,p5,p6,p7 position

  classDef c1 fill:#ff7f0e,color:#fff;
  classDef c2 fill:#ffbb78,color:#000;
  classDef c2a fill:#ffbb788a,color:#000;
  classDef c3 fill:#2ca02c,color:#fff;
  classDef c4 fill:#98df8a,color:#000;
  classDef c4a fill:#98df8a8a,color:#000;
  classDef c5 fill:#d62728,color:#fff;
  classDef c6 fill:#ff9896,color:#000;
  classDef c6a fill:#ff98968a,color:#000;
  classDef c7 fill:#9467bd,color:#fff;
  classDef c8 fill:#c5b0d5,color:#000;
  classDef c9 fill:#8c564b,color:#fff;
  classDef c10 fill:#c49c94,color:#000;
  classDef c11 fill:#e377c2,color:#fff;
  classDef c12 fill:#f7b6d2,color:#000;
  classDef c13 fill:#bcbd22,color:#fff;
  classDef c14 fill:#dbdb8d,color:#000;
  classDef c14a fill:#dbdb8d8a,color:#000;
  classDef c15 fill:#17becf,color:#fff;
  classDef c16 fill:#9edae5,color:#000;

  class s1,s5,i1,i5 c4
  class s2,s4,i2,i4 c1
  class s3,i3 c5
  class s6,i6 c7
  class pomn,p00,p01,p06,p07,p02n position
  class t1,t2,t5,e0,e1 position

Calculated interval by \(Intervals\) function is the absolute value of difference the corresponding index and the index. For example, for index 5 interval would be \(|5-1|=4\)

---

There should exists an inverse function that restores by interval chain a sequence with the original order

From an interval chaincalculate correspoding indexesand use binding⁻¹to reconstruct sequence

block-beta
  columns 7
  space  p1["1"] p2["2"] p3["3"] p4["4"] p5["5"] p6["6"]
  space s1["1"] s2["2"] s3["3"] s4["2"] s5["4"] s6["6"]

  classDef imaginary fill:#526cfe09,color:#000,stroke-dasharray: 10 5;
  classDef position fill:#fff,color:#000,stroke-width:0px;
  class inf,sup imaginary
  class p0,p1,p2,p3,p4,p5,p6,p7 position

  classDef c1 fill:#ff7f0e,color:#fff;
  classDef c2 fill:#ffbb78,color:#000;
  classDef c2a fill:#ffbb788a,color:#000;
  classDef c3 fill:#2ca02c,color:#fff;
  classDef c4 fill:#98df8a,color:#000;
  classDef c4a fill:#98df8a8a,color:#000;
  classDef c5 fill:#d62728,color:#fff;
  classDef c6 fill:#ff9896,color:#000;
  classDef c6a fill:#ff98968a,color:#000;
  classDef c7 fill:#9467bd,color:#fff;
  classDef c8 fill:#c5b0d5,color:#000;
  classDef c9 fill:#8c564b,color:#fff;
  classDef c10 fill:#c49c94,color:#000;
  classDef c11 fill:#e377c2,color:#fff;
  classDef c12 fill:#f7b6d2,color:#000;
  classDef c13 fill:#bcbd22,color:#fff;
  classDef c14 fill:#dbdb8d,color:#000;
  classDef c14a fill:#dbdb8d8a,color:#000;
  classDef c15 fill:#17becf,color:#fff;
  classDef c16 fill:#9edae5,color:#000;

  class pomn,p00,p01,p06,p07,p02n position
  class t1,t2,t5,e0,e1 position

Let there be an interval chain.

block-beta
  columns 7
  p0["0"]  p1["1"] p2["2"] p3["3"] p4["4"] p5["5"] p6["6"]
  space s1["1"] s2["2"] s3["3"] s4["2"] s5["4"] s6["6"]
  space i1["0"] i2["0"] i3["0"] i4["2"] i5["1"] i6["0"]

  classDef imaginary fill:#526cfe09,color:#000,stroke-dasharray: 10 5;
  classDef position fill:#fff,color:#000,stroke-width:0px;
  class inf,sup imaginary
  class p0,p1,p2,p3,p4,p5,p6,p7 position

  classDef c1 fill:#ff7f0e,color:#fff;
  classDef c2 fill:#ffbb78,color:#000;
  classDef c2a fill:#ffbb788a,color:#000;
  classDef c3 fill:#2ca02c,color:#fff;
  classDef c4 fill:#98df8a,color:#000;
  classDef c4a fill:#98df8a8a,color:#000;
  classDef c5 fill:#d62728,color:#fff;
  classDef c6 fill:#ff9896,color:#000;
  classDef c6a fill:#ff98968a,color:#000;
  classDef c7 fill:#9467bd,color:#fff;
  classDef c8 fill:#c5b0d5,color:#000;
  classDef c9 fill:#8c564b,color:#fff;
  classDef c10 fill:#c49c94,color:#000;
  classDef c11 fill:#e377c2,color:#fff;
  classDef c12 fill:#f7b6d2,color:#000;
  classDef c13 fill:#bcbd22,color:#fff;
  classDef c14 fill:#dbdb8d,color:#000;
  classDef c14a fill:#dbdb8d8a,color:#000;
  classDef c15 fill:#17becf,color:#fff;
  classDef c16 fill:#9edae5,color:#000;

  class pomn,p00,p01,p06,p07,p02n position
  class t1,t2,t5,e0,e1 position

The \(Intervals^{-1}\) function for calculating corresponding index based on the current index and interval is closly coupled with direction in selected Binding. The function has to be defined for each particular Binding method. Whether it is possible to obtain direction of Binding given an interval chain, and whether there are two equivalent interval chains obtained by different Binding methods, are open questions that need to be investigated.

In the example \(Intervals^{-1}(IC)(i) = IC(i)-i\)

block-beta
  columns 6
  p1["1"] space:3         p5["5"]                p6["6"]
  s1["0"] s2["0"] s3["0"] s4["2"] s5["1"] s6["0"]
  e0["Iterator⁻¹(1) = 1"] space:5
  t1["Iterator⁻¹(5) = 1"]:5         space

  classDef imaginary fill:#526cfe09,color:#000,stroke-dasharray: 10 5;
  classDef position fill:#fff,color:#000,stroke-width:0px;
  class inf,sup imaginary
  class p0,p1,p5,p6,p7 position

  classDef c1 fill:#ff7f0e,color:#fff;
  classDef c2 fill:#ffbb78,color:#000;
  classDef c2a fill:#ffbb788a,color:#000;
  classDef c3 fill:#2ca02c,color:#fff;
  classDef c4 fill:#98df8a,color:#000;
  classDef c4a fill:#98df8a8a,color:#000;
  classDef c5 fill:#d62728,color:#fff;
  classDef c6 fill:#ff9896,color:#000;
  classDef c6a fill:#ff98968a,color:#000;
  classDef c7 fill:#9467bd,color:#fff;
  classDef c8 fill:#c5b0d5,color:#000;
  classDef c9 fill:#8c564b,color:#fff;
  classDef c10 fill:#c49c94,color:#000;
  classDef c11 fill:#e377c2,color:#fff;
  classDef c12 fill:#f7b6d2,color:#000;
  classDef c13 fill:#bcbd22,color:#fff;
  classDef c14 fill:#dbdb8d,color:#000;
  classDef c14a fill:#dbdb8d8a,color:#000;
  classDef c15 fill:#17becf,color:#fff;
  classDef c16 fill:#9edae5,color:#000;

  class s1,s5 c4
  class inf,t1,e0 c4a
  class pomn,p00,p01,p06,p07,p02n position
  class t1,t2,t5,e0,e1 position

For each Binding should exists \(Binding^{-1}\) with an \(Iterator^{-1}\) that allows to relabel elements of interval chain with a unique number of the traversed path that it belongs to.

\[Iterator^{-1}(P)(i) = \Bigg\{\begin{array}{l} \big|<j \in \{1,...i\} | P(j)=0 >\big| & if \ P(i)=0 \\ Iterator^{-1}(P, P(i)) & otherwise \end{array}\]

block-beta
  columns 6
  p1["1"] p2["2"] p3["3"] p4["4"] p5["5"] p6["6"]
  i1["0"] i2["0"] i3["0"] i4["2"] i5["1"] i6["0"]
  s1["1"] s2["2"] s3["3"] s4["2"] s5["1"] s6["4"]

  classDef imaginary fill:#526cfe09,color:#000,stroke-dasharray: 10 5;
  classDef position fill:#fff,color:#000,stroke-width:0px;
  class inf,sup imaginary
  class p0,p1,p2,p3,p4,p5,p6,p7 position

  classDef c1 fill:#ff7f0e,color:#fff;
  classDef c2 fill:#ffbb78,color:#000;
  classDef c2a fill:#ffbb788a,color:#000;
  classDef c3 fill:#2ca02c,color:#fff;
  classDef c4 fill:#98df8a,color:#000;
  classDef c4a fill:#98df8a8a,color:#000;
  classDef c5 fill:#d62728,color:#fff;
  classDef c6 fill:#ff9896,color:#000;
  classDef c6a fill:#ff98968a,color:#000;
  classDef c7 fill:#9467bd,color:#fff;
  classDef c8 fill:#c5b0d5,color:#000;
  classDef c9 fill:#8c564b,color:#fff;
  classDef c10 fill:#c49c94,color:#000;
  classDef c11 fill:#e377c2,color:#fff;
  classDef c12 fill:#f7b6d2,color:#000;
  classDef c13 fill:#bcbd22,color:#fff;
  classDef c14 fill:#dbdb8d,color:#000;
  classDef c14a fill:#dbdb8d8a,color:#000;
  classDef c15 fill:#17becf,color:#fff;
  classDef c16 fill:#9edae5,color:#000;

  class s1,s5,i1,i5 c4
  class s2,s4,i2,i4 c1
  class s3,i3 c5
  class s6,i6 c7
  class pomn,p00,p01,p06,p07,p02n position
  class t1,t2,t5,e0,e1 position

The reconstructed sequence is not equal to the original one, but it preserves the same order of elements and its intervals chain would be equal to the interval chain of the original sequence.

block-beta
  columns 6
  p1["1"] p2["2"] p3["3"] p4["4"] p5["5"] p6["6"]
  s1["1"] s2["2"] s3["3"] s4["2"] s5["1"] s6["4"]
  i1["A"] i2["C"] i3["T"] i4["C"] i5["A"] i6["G"]

  classDef imaginary fill:#526cfe09,color:#000,stroke-dasharray: 10 5;
  classDef position fill:#fff,color:#000,stroke-width:0px;
  class inf,sup imaginary
  class p0,p1,p2,p3,p4,p5,p6,p7 position

  classDef c1 fill:#ff7f0e,color:#fff;
  classDef c2 fill:#ffbb78,color:#000;
  classDef c2a fill:#ffbb788a,color:#000;
  classDef c3 fill:#2ca02c,color:#fff;
  classDef c4 fill:#98df8a,color:#000;
  classDef c4a fill:#98df8a8a,color:#000;
  classDef c5 fill:#d62728,color:#fff;
  classDef c6 fill:#ff9896,color:#000;
  classDef c6a fill:#ff98968a,color:#000;
  classDef c7 fill:#9467bd,color:#fff;
  classDef c8 fill:#c5b0d5,color:#000;
  classDef c9 fill:#8c564b,color:#fff;
  classDef c10 fill:#c49c94,color:#000;
  classDef c11 fill:#e377c2,color:#fff;
  classDef c12 fill:#f7b6d2,color:#000;
  classDef c13 fill:#bcbd22,color:#fff;
  classDef c14 fill:#dbdb8d,color:#000;
  classDef c14a fill:#dbdb8d8a,color:#000;
  classDef c15 fill:#17becf,color:#fff;
  classDef c16 fill:#9edae5,color:#000;

  class s1,s5,i1,i5 c4
  class s2,s4,i2,i4 c1
  class s3,i3 c5
  class s6,i6 c7
  class pomn,p00,p01,p06,p07,p02n position
  class t1,t2,t5,e0,e1 position

---

Formal order analysis identifies two groups of Bindings:

• Bounded - consider a sequence to be finite and bounded. Operates with the minimum data required to determine intervals chains and sequence.
• Cycled - treats a sequence as a subsequence representing an infinite sequence. Connects FOA with the fundamental ideas underlying statistics and probability theory.

Mathematical Definition

Let \(X\) is Carrier set

Let \(S\) is Sequence length of \(n\) described as function \(S : \{1,...,n\} \longrightarrow X\)

Define Bindings

Define a set of terminal values - \(\bot \subset N \setminus \{1,..,n\}\)

Let \(R : \{1,...,n\} \longrightarrow \{1,...,n\} \cup \bot,\) is a corresponding references

Define

\[Iterator : \big\{ S \big\} \longrightarrow \big\{ R \big\},\]

\[Binding = <Iterator, \bot>\]

\[\exists Binding^{-1} = <Iterator^{-1}, \bot>,\]

\[Iterator^{-1} : \big\{ R \big\} \longrightarrow \big\{ \{1,...,n\} \longrightarrow \{1,...,m\} | m \leq n \big\}\]

\[Iterator(S) = Iterator(Iterator^{-1}(Iterator(S)))\]

Define Intervals Chain

as n-tuple of natural numbers

\[IC = <\Delta_1, \Delta_2, ..., \Delta_n> | \forall j \in \{1,...,n\} \exists \Delta_j \in \{1,...,n\},\]

if and only if

\[\exists \ Intervals : \big\{Binding\big\} \times \big\{S\} \longrightarrow \big\{ IC \big\},\]

\[Intervals(<iterator, \bot>, S)(i) = | i - iterator(S)(i)|,\]

\[\exists \ Intervals^{-1} : \big\{Binding^{-1}\big\} \times \big\{ IC \big\} \longrightarrow \big\{ \{1,...,n\} \longrightarrow \{1,...,m\} | m \leq n \big\},\]

\[Intervals(b, S) = Intervals(b, Intervals^{-1}(b^{-1}, Intervals(b, S)))\]

\[\exists \ Follow : \big\{Binding\big\} \times \big\{ IC \big\} \longrightarrow \big\{ R \big\},\]

\[Follow(b, IC)(i) <> Follow(b, IC)(j) \lor Follow(b, IC)(i) \in \bot | \forall i != j \]

\[\exists \ Trace : \big\{Binding\big\} \times \big\{ IC \big\} \longrightarrow \big\{ R \big\}\]

\[Trace(<iterator, \bot>, IC)(i) = \Bigg\{\begin{array}{l} i, & \ i \in \bot \\ Trace\big(Follow(IC, i)\big) & i \in \{1,...,n\} \end{array}\]

\[Trace(IC)(i) \in \bot | \forall i \in \{1,...,n\}\]

Where:

• \(n := |IC|\) is called length of the intervals chained, \(n \in N\)
• \(\Delta_i\)​ is called the \(i\)-th element (or interval) of the intervals chained