Constraints on sliding windows

Question

Let $L\subseteq \Sigma^*$ be a language of finite words and $n>0$ some integer.

I would like to know if anything is known on the time and space complexity with respect to $n$ to check for membership in $L$ for a sliding window of size $n$ over an infinite stream. Here I mean the incremental complexity by moving the window along the stream and computing on the fly the membership of the window seen as a word to the language $L$.

Exemple: It is simple to check with space complexity $\mathcal{O}(\log(n))$ and time complexity $\mathcal{O}(1)$ for the language $\Sigma^* ab \Sigma^*$ with $\Sigma=\{a,b\}$. You simply need to remember the last $ab$ factor seen in a register and to increment it by $1$ at every new symbol, which is constant in the appropriate RAM model.

Case of interest (at least for me) includes:

1. $L$ is the Parity language over $\{0, 1\}$, the number of $1$ is even, or in regexp: $(0^* + 10^*1)^*$
2. $L$ is the Majority language over $\{0,1\}$, there are more $1$ than $0$.
3. $L$ is the language over $\{0,1,e\}$ such that there exists a $0$ before a $1$.
4. $L$ is an arbitary regular language.

In particular, is it needed to store all the window for those languages? It seems so but I fail to see a proof. Even if we allow a space $\mathcal{O}(n)$, can we reply in time $\mathcal{O}(1)$?

Answer 1

Here is a second, simpler and more general answer that was obtained after discussing with a3nm.

Problem

We fix a regular language $\mathcal{L}$ and we are interested in the following word problem. At start, we have an empty word and then we receive updates taking one of the following forms:

• Insert a letter at the beginning of the word
• Insert a letter at the end of the word
• Delete the letter at the beginning of the word
• Delete the letter at the end of the word

After each update we want to know whether the current word is in the language $\mathcal{L}$. Clearly this problem is more general than the one proposed by C.P.

Claim

The problem above can be solved in constant (non amortized) update.

Proof

We note $\bar{\delta}(w) : \mathcal{Q}\rightarrow \mathcal{Q}$ the function that associates $q$ with $\delta(q,w)$, which we call the effect of $w$. For the sake of simplicity we identify a letter $c$ with its effect $\bar{\delta}(c)$. To maintain whether the contents of the window belong to the language, it suffices to maintain the effect of the window, because a word $w$ belongs to $\mathcal{L}$ iff $(\bar{\delta}(w))(q_0) \in \mathcal{F}$.

I suppose that it is obvious to maintain the word after updates in a way that allows to query the letter at any position in the word (e.g. using an amortized circular buffer).

We define the notion of guardian as a position within the word with a left span and right span. Let $w_1 \dots w_m$ be our word. A guardian placed at position $p$ with left span $l$ stores a list $b_1 \dots b_l$ of effects where the element $b_i$ corresponds to the effect of $w_{p-i} \dots w_{p-1}$. Similarly, if it has a right span $r$, then it stores a list $a_1 \dots a_r$ with $a_i$ corresponding to the effect of $w_p \dots w_{p+i}$. We say that a guardian is full whenever it spans the whole word.

Properties of guardians:

• It takes a constant time to increase by a constant number the left and right spans of a guardian.
• If we have a guardian at some position in a word $w$ that is updated and if the guardian was not placed at a position that is deleted, we can get in constant time a guardian for the updated word that has the same span (possibly minus one if the span covered a letter that has been deleted).
• We can maintain after update a full guardian in constant time as long as its position is not deleted.

Here is the sketch of our algorithm: let $N$ denotes the current size of the word. We will maintain a full guardian roughly at the middle of the word (between $N/4$ and $3N/4$). As soon as the full guardian escapes the middle, we start creating a second guardian at position $N/2$. After each update we increase the span of this second guardian by 8. This ensures that the second guardian will become full before our first guardian gets deleted and that the position of our second guardian will stay in the middle (between $3N/7$ and $4N/7$) as long as it is not full. When the second guardian is full, we replace the first guardian with the second.

After each update, we have a full guardian that allows us to answer whether the word belongs to $\mathcal{L}$.

Extension with infix queries

With a3nm we also found out that we can solve an extension of this problem (insert & delete at the beginning and at the end of the word) plus queries of the form "given $(i,j)$, is the factor $w[i:j]$ of the current word $w$ within $\mathcal{L}$?" using Bojańczyk structure described in section 2.2 of its paper Factorization Forests. In his paper Bojańczyk does not describe how we can update the structure and it would require a little care to do it but it can be updated in constant time for a fixed language.

Answer 2

It seems it would depend on your particular model, in particular what information you have access to.

From what I infer, you are thinking of the following model:

• you have a memory $m$, for instance of size $O(\log n)$.

• at each step, you read a new letter $a\in\Sigma$ of your stream, and you are allowed to modify your memory $m$

• you then have to say whether the word under you new sliding window shifted by $1$ is in $L$, based solely on $m$.

In particular, you don't have access to the letter leaving the sliding window. If you had this information, the problem would be more symmetrical, and for instance languages Parity and Majority would be computable with constant and logarithmic memory respectively.

Memory constraint

In the setting above without this information, here is for instance a proof that a linear memory is needed for Parity, so basically you need to remember the whole word. Indeed, if you use sublinear memory, there are two different words $u$ and $v$ of length $n$ that give rise to the same memory state $m$. Then, let $d$ be the first position where $u$ and $v$ differ, and consider that your stream continues with $0^d$. After having read this suffix, you will have the same memory $m'$, so you must answer the same thing in both cases. But since the bit that got out of the window is not the same for $u$ and $v$, your answer is wrong for one of the two.

Time constraint

It is possible to recognize any regular language $L$ with quasi-constant amortized time. The time complexity is the one from a union-find-delete (UFD) data structure. For instance this paper shows that operations union, makeset and delete can be done in constant time, and the find operation in reverse Ackermann (so at most $5$ for any input value making sense in the physical word, see wikipedia on union-find).

Let $A$ be a DFA recognizing $L$, with states $Q$, transition function $\delta:Q\times\Sigma\to Q$, and initial state $q_0.$ Let $k=|Q|$, since $L$ is fixed $k$ is a constant.

Let $a_0a_2\dots a_{n-1}\in\Sigma^n$ be the word currently under the window. The idea is to maintain a memory structure $m$, giving for each word $u_i=a_i\dots a_{n-1}$ the state $q_i$ reached by $A$ after reading $u_i$. We will also maintain an index $\gamma\in[0,n-1]$, giving the identifier associated with $u_0$. The identifier for $u_j$ is $\gamma+j \mod n$.

The UFD structure will store identifiers of all words $u_0\dots u_{n-1}$, and two words $u_i,u_j$ will be in the same partition if and only if $q_i=q_j$. The common state $q$ labels the partition.

So in order to know whether the current word is in $L$, it suffices to identify the label $q$ of partition of the identifier $\gamma$ (corresponding to the word $u_0$), and check whether $q$ is accepting.

When a new letter $a$ is read, we update the memory as follows:

• the identifier $\gamma$ is deleted from the UFD structure
• a new identifier $\gamma$ is added, and joins the partition labeled $q_0$. A new partition is created if none exists. For this we can use the help of an auxiliary memory of constant size, storing which states are currently labelling partitions, and giving a witness identifier for each one.
• the current index $\gamma$ is updated to $\gamma'=\gamma+1\mod n$.
• all labels of partitions are updated to their $a$-successors: $q'=\delta(q,a)$ for each label $q$. Partitions that get the same label are merged.

All these operations are either constant time or in quasi-constant amortized time.

Answer 3

Context

Let $\mathcal{L}$ be a fixed regular language and let ($\mathcal{Q}, \Sigma, \delta, q_0, \mathcal{F})$ be an automaton recognizing $\mathcal{L}$.

I will suppose in this post that we are working in the RAM model with cells of size logarithmic in the maximal size of the window, and that all the operations regarding the automaton are constant time.

Claim

We can maintain $\mathcal{L}$ in constant (non-amortized) time for a window of constant size.

Let us first show how we can maintain in $O(\ln(n))$ time, then how this can be improved to constant amortized time and then finally let us prove how we can have the constant non-amortized result.

Proof of the $O(\ln(n))$ bound

We note $\bar{\delta}(w) : \mathcal{Q}\rightarrow \mathcal{Q}$ the function that associates $q$ with $\delta(q,w)$, which we call the effect of $w$. For the sake of simplicity we identify a letter $c$ with its effect $\bar{\delta}(c)$. To maintain whether the contents of the window belong to the language, it suffices to maintain the effect of the window, because a word $w$ belongs to $\mathcal{L}$ iff $(\bar{\delta}(w))(q_0) \in \mathcal{F}$.

The idea here is to build a segment tree over the infinite word that allows us to query the effect of the sliding window in time $O(\ln(n))$. Note that $\bar{\delta}(w_1 w_2) = \bar{\delta}(w_2) \circ \bar{\delta}(w_1)$ therefore the effect of a word can, indeed, be computed with such a tree.

As the stream is unbounded, we cannot use a segment tree directly, as both the memory will increase linearly and the depth of the tree will grow logarithmically in the size of the stream that has been read.

To counter this problem we can use the following data structure. Let $k$ be such that $2^k \leq n < 2^{k+1}$. We will maintain three binary trees of depth $k$: $A, B$ and $C$. The binary tree $A$ will be rightmost full, $B$ will be either empty or full while $C$ will be leftmost full (but never full) as depicted here:

To move the sliding window we need to remove a letter and add a new one. Let us first cover the removal: if $A$ is empty then we exchange $A$ and $B$. Then we remove the leftmost leaf from $A$. Adding a new letter on $C$ is always possible ($C$ is never full). If after this $C$ becomes full, we exchange $C$ and $B$. It is easy to see that with our choice of $k$ then when we switch $A$ and $B$ because $A$ is empty, then $B$ cannot also be empty, so it must be full. Likewise, when we exchange $B$ and $C$ because $C$ is full, then $B$ cannot also be full, so it is empty.

Exchanging trees can be done in $O(1)$. Adding a letter or removing a letter at depth $k$ can be done in $O(k)$: we locate in $O(k)$ the place where the letter should be removed or inserted, we perform the change (accounting for the effect of the added or removed letter), and then we update the annotation of the effects of all parent nodes in $O(k)$ by going upwards in the tree. Therefore, we have an $O(\ln(n))$ algorithm. Note that reading the effect of the whole sliding window can be done by combining the effect of the roots of $A$, $B$ and $C$ and thus in $O(1)$.

Note that this structure does not require the sliding window to be of constant size $n$ but only that we alternate between insertion and deletion (it will be useful for the next proof).

Proof of the constant amortized bound

The infinite stream will be split into "chunks" $C_1 \dots $ of size $K=O(\ln(n))$. At each step of the computation, the sliding window will start within a chunk $C_i$ and end within a chunk $C_{j}$ ($j-i$ will be roughly equal to $n/K$). We will maintain separately (1) the effect of the part coming from the first chunk $C_i$, (2) the effect from the part of the last chunk $C_{j}$ and (3) the combined effect of all the chunks from the middle $C_{i+1} \dots C_{j-1}$ (see figure below). The overall effect will simply be the combination of the effects of (1), (2), and (3).

The effect of (1) can be maintained in the following way: each time our sliding window starts in a new chunk $C_i$ we compute for all suffixes $S$ of $C_i$ the effect of $S$. This can be done in time $O(|C_i|)$ because the effect of $aS$ (where $a$ is a letter and $S$ a word) can be computed by combining the effect of $a$ and $S$. Therefore to maintain (1) we pay a price $K$ each time we enter a new block of size $K$. Once the effects of all the suffixes have been computed we can answer in $O(1)$. In amortized complexity this gives us $O(1)$.

The effect of (2) can be maintained in non-amortized $O(1)$ as we only add letters at the end of the current chunk, or restart from an empty chunk.

The effect of (3) can be computed using a tree as seem above for the $O(\ln(n))$ bound. Clearly we only add and remove a new chunk every $K$ steps. And it takes $O(\ln(n))$ to make the insertion/deletion therefore we also have the expected amortized complexity.

Proof of the constant non-amortized bound

In the proof above, we have an algorithm that uses $O(1)$ computation at all steps plus $O(\ln(n))$ every $O(\ln(n))$ steps. The basic idea here is to use a small amount of computation at each of the steps to amortize the $O(\ln(n))$ cost.

For the effect of (1), this is easy, when we are in a block $C_i$ we compute the effect of suffixes for the block $C_{i+1}$, for each new letter removed in $C_i$ we compute a new suffix of $C_{i+1}$. This is $O(1)$.

For the effect of (2), there is nothing to do as it was already $O(1)$.

For the effect of (3), it is more complex. In the algorithm that we used for the amortized complexity, each $O(\ln(n))$ steps we remove and add a chunk. When removing a chunk, we must locate in $O(\ln(n))$ where the chunk to remove is located (note that it may be in binary tree $B$ or even $C$), remove it, and update upwards the effect of the parent nodes. This modification of $O(\ln(n))$ can be performed by doing some $O(1)$ computation step each time the window is modified, resulting in $O(1)$ non-amortized time. Note that, while we perform these operations in place, the effects annotating the nodes of the affected tree $A$, $B$ or $C$ may no longer be valid (as they partly reflect the deletion), but this is not an issue: we only use the effect of the root of the tree to determine whether the current window is in $\mathcal{L}$ or not, and this annotation is modified last, when the deletion has actually taken place.

When inserting a chunk, the same reasoning work, but there is an added complication: the value of the inserted chunk, and its effect, is only known at the very end of the insertion, so we cannot do this amortization as-is. To work around this problem, we split our sliding window into four blocks. As before we will have a block (1) covering the effect of the suffixes of the first chunk and (2) for the prefixes of the last chunk but (3) will now only cover $C_{i+1}$ up to $C_{j-2}$ and thus we will have a block (4) computing the effect of $C_{j-1}$.

The effect of (4) can easily be maintained as it was already computed for (2) (the entire chunk is a suffix of itself). So this ensures that the chunk to insert in the tree, namely (4), is completely known, and we can do a similar amortization.

The last subtlety to note is that the amortization of insertions and deletions may end up updating the same tree in-place (e.g., we insert a node in tree $C$, and we remove a node in tree $C$ which will be swapped with $B$ and $A$). However, one can show that this is no problem, because the modifications performed in-place in the amortization step are performed from bottom to top, so operations will be reflected in the right order. Alternatively, we can modify the structure of trees used in the $O(\ln(n))$ bound to use 5 trees instead of 3, and this can ensure that the computations when amortizing insertions and deletions will never take place in the same tree.

Case of a variable-size window

If we allow arbitrary insertions and deletions and allow the size of the sliding window to evolve freely, then the scheme can probably be adjusted. This would require the use of more trees in the $O(\ln(n))$ algorithm, with the possibility to merge together trees or split trees when the window size changes too much (i.e., its logarithm changes). What is more, the block size in the $O(1)$ amortized algorithm would also need to change; but as these window size changes are rare, we should be able to amortize these complete recomputations of the data structure.

Answer 4

This seems to be exactly the type of question studied by Moses Ganardi and coauthors in recent years. In particular this paper and this extension prove nice trichotomies.