α**. Since TRANSIT is always true in the MO mode, all**
automata would be tracking ET occurrences. Since COPYAUTOMATON is true in MO mode whenever an automaton transits out of start state, we will always have an automaton in the start state. **This, along with the fact that**
TRANSIT is always true, implies that the i th **initialized automaton would be tracking** h e i**, the** i th ET occurrence. **Let us**
denote by A
α i the i th **initialized automaton. However, since**
JOIN-AUTOMATON is also always true, not all automata
(initialized for this episode) would result in incrementing the frequency; some of them would be removed when one automaton transits into a state already occupied by some other automaton. In view of Lemma 2 and Remark 4, if we show that the automaton A
α i **results in increment of frequency if and only if** h e i**, the occurrence tracked by it, is**
such that h e i (vN ) < he i+1(vN **), then, the proof of correctness**
of MO algorithm is complete.

Lemma 3. **In the MO algorithm the** i th **automaton that**
was initialized for α**, referred to as** A
α i**, contributes to the**
frequency count iff h e i (vN ) < he i+1(vN ).

Proof.

A
α
i **does not contribute to the frequency**
=⇒ Aα
i**is removed by a more recently initialized automaton**
=**⇒ ∃ A**α
k , k > i, **which transits into a state**
already occupied by A
α i
=⇒ ∃k, j s.t. k > i, 1 < j ≤ N and h
e
i (vj ) = h
e
k(vj ).
=⇒ ∃j 1 < j ≤ **N s.t. h**e
i (vj ) = h
e
i+1(vj ).
because, by Remark 3, for **k > i,**
h
e
i (vj ) ≤ h
e
i+1(vj ) ≤ h
e
k(vj ), ∀j
=⇒ h
e
i (vN ) = h
e
i+1(vN )
The last step follows because both h
e
i and h
e
i+1 **are ET occurrences and hence** h
e
i (vj ) = h
e
i+1(vj **) implies** h
e
i (vj
′ ) =
h
e
i+1(vj
′ ), ∀j
′ > j.
Conversely, we have
$$\begin{array}{r l}{{}}&{{\mathcal{A}_{i}^{\alpha}\mathrm{~contributes~to~the~frequency}}}\\ {{}}&{{\Longrightarrow}}\quad\forall j,\ 1<j\leq N,\,h_{i}^{e}(v_{j})<h_{i+1}^{e}(v_{j}),}\\ {{}}&{{\Longrightarrow}}\quad h_{i}^{e}(v_{N})<h_{i+1}^{e}(v_{N}).}\end{array}$$
The first step follows because, if A
α
i **contributes to the frequency then no automaton initialized after it would ever** come to the same state occupied by it and since all occurrences tracked are earliest transiting, this must mean
h
e
i (vj ) < he
i+1(vj ), ∀j**. This completes proof of the lemma.**
Another interesting observation is that if h e i**is minimal,**
then it is non-interleaved with h e i+1**. Suppose** h e i**is minimal and** h e i**is not non-interleaved with** h e i+1**. Since** h e iis minimal, we have h e i (vj
′ ) < he i+1(vj
′ ), ∀j
′**. If** h e i**is not**
non-interleaved with h e i+1, there exists a j < N **such that**
h e i+1(vj ) < he i (vj+1**). Thus we must have** h e i (vj ) < he i+1(vj ) <
h e i (vj+1) < he i+1(vj+1**). But this can not be because** Ehe i
(vj+1)
is the earliest α[j **+ 1] after** h e i (vj **) and if it is also after**
h e i+1(vj **) then the fact that both** h e i and h e i+1 **are ET occurrences should mean** h e i (vj+1) = h e i+1(vj+1**) which contradicts that** h e i**is minimal. Hence** h e i and h e i+1 **are noninterleaved.**
Thus, given the sequence of minimal windows, the earliest transiting occurrences from each of these minimal windows gives a sequence of (same number of) non-interleaved occurrences. This leads to fmi ≤ fni **as stated earlier in (3).**

## 4.2 Other Et Occurrences-Based Algorithms

4.2.1 Proofs of correctness for NO-X and NO-I
The NO-X algorithm can be viewed as a slight modification to the MO algorithm. As in the MO algorithm, we always have an automaton in the start state and all automata make transitions as soon as possible and when an automaton transits into a state occupied by another, the older one is removed. However, in the NO-X algorithm, the INCREMENT-FREQ variable is true only when we have an occurrence satisfying TX **constraint. Hence, to start with,**
we look for the first minimal occurrence which satisfies the expiry time constraint and increment frequency. At this point, (unlike in the MO algorithm) we terminate all automata except the one in the start state since we are trying to construct a non-overlapped set of occurrences. Then we look for the next earliest minimal occurrence (which will be non-overlapped with the first one) satisfying expiry time constraint and so on. Since minimal occurrences locally have the least time span, this strategy of searching for minimal occurrences satisfying expiry time constraint in a non-overlapped fashion is quite intuitive. Let HnX =
{h nX
1 , hnX
2 **. . . h**nX
f′ } **denote the sequence of occurrences tracked**
by the NO-X algorithm (for an N**-node episode). Then the** following property of HnX **is obvious.**
Property 1. h nX
1 **is the earliest minimal occurrence satisfying expiry time constraints.** h nX
i**is the first minimal occurrence (satisfying expiry time constraint) that starts after**
h nX
i−1(vN )**. There is no minimal occurrence satisfying expiry**
time constraint which starts after h nX
f′ (vN ).

Theorem 1. HnX **is a maximal non-overlapped sequence**
satisfying expiry time constraint TX.

Proof. **Consider any other set of non-overlapped occurrences satisfying expiry constraints,** H′ = {h
′
1, h′2 . . . h′l} **such**
that h
′
i <⋆ h
′
i+1. Let m = min{f
′, l}. **Then we first show**
h nX
i (vN ) ≤ h
′
i(vN ) ∀i = 1, 2**, . . . m.**
Suppose h
′
1(vN ) < hnX
1 (vN **). Consider the earliest transiting occurrence** h
′′ **starting from** h
′
1(v1**). This ends at or**
before h
′
1(vN **) by lemma 1. Among all ET occurrences that**
end at the same event as h
′′**, the last one (under the lexicographic ordering) is a minimal occurrence by lemma 2.**
Its window is contained in that of h
′
1 **which satisfies the**
expiry time constraint. Hence we have found a minimal occurrence satisfying expiry constraint ending before h nX 1 which contradicts the first statement of property 1. Hence h nX
1 (vN ) ≤ h
′
1(vN **). Now applying the same argument to**
the data stream starting with the first event after h nX
1 (vN ),
we get h nX
2 (vN ) ≤ h
′
2(vN **) and so on and thus can conclude** h nX
i (vN ) ≤ h
′
i(vN ) ∀i**. This shows that no other set**
of non-overlapped occurrences can have more number of occurrences than those in HnX. Hence, HnX **is maximal.**
If we choose TX **equal to the time span of the data stream,**
the NO-X algorithm reduces to the NO-I algorithm because every occurrence satisfies expiry constraint. Hence proof of correctness of NO-I algorithm is immediate.

4.2.2 Relation between NO-I and NO algorithms We now explain the relation between the sets of occurrences tracked by the NO and NO-I algorithms. As proved in [10]