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

<h2>Problem</h2>

<p>We fix a regular language <span class="math-container">$\mathcal{L}$</span> 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:</p>

<ul>
<li>Insert a letter at the beginning of the word</li>
<li>Insert a letter at the end of the word</li>
<li>Delete the letter at the beginning of the word</li>
<li>Delete the letter at the end of the word</li>
</ul>

<p>After each update we want to know whether the current word is in the language <span class="math-container">$\mathcal{L}$</span>. Clearly this problem is more general than the one proposed by C.P.</p>

<h2>Claim</h2>

<p>The problem above can be solved in constant (non amortized) update.</p>

<h2>Proof</h2>

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

<p>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 <a href="https://en.wikipedia.org/wiki/Circular_buffer" rel="nofollow noreferrer">circular buffer</a>).</p>

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

<p>Properties of guardians:</p>

<ul>
<li>It takes a constant time to increase by a constant number the left and right spans of a guardian.</li>
<li>If we have a guardian at some position in a word <span class="math-container">$w$</span> 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).</li>
<li>We can maintain after update a full guardian in constant time as long as its position is not deleted.</li>
</ul>

<p>Here is the sketch of our algorithm: let <span class="math-container">$N$</span> denotes the current size of the word. We will maintain a full guardian roughly at the middle of the word (between <span class="math-container">$N/4$</span> and <span class="math-container">$3N/4$</span>). As soon as the full guardian escapes the middle, we start creating a second guardian at position <span class="math-container">$N/2$</span>. 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 <span class="math-container">$3N/7$</span> and <span class="math-container">$4N/7$</span>) as long as it is not full. When the second guardian is full, we replace the first guardian with the second.</p>

<p>After each update, we have a full guardian that allows us to answer whether the word belongs to <span class="math-container">$\mathcal{L}$</span>.</p>

<h2>Extension with infix queries</h2>

<p>With a3nm we also found out that we can solve an extension of this problem (insert &amp; delete at the beginning and at the end of the word) plus queries of the form "given <span class="math-container">$(i,j)$</span>, is the factor <span class="math-container">$w[i:j]$</span> of the current word <span class="math-container">$w$</span> within <span class="math-container">$\mathcal{L}$</span>?" using Bojańczyk structure described in section 2.2 of its paper <a href="https://www.mimuw.edu.pl/~bojan/papers/forests-dlt.pdf" rel="nofollow noreferrer">Factorization Forests</a>. 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.</p>

CC BY-SA 4.0
2020-05-04T17:57:45.423Z
This can also be seen as the standard amortized O(1) algorithm to maintain a deque using two stacks (here the stacks are the prefixes and suffixes from the guardian, on which the effect can be computed incrementally), but modified to guarantee non-amortized O(1) by starting to re-pack the two stacks as soon as they become too imbalanced (= building a new guardian).
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2020-05-03T14:06:05.670Z
2020-05-06T08:15:58.567Z
2020-05-06T08:15:58.567Z
Louis
<p>It seems it would depend on your particular model, in particular what information you have access to.</p>

<p>From what I infer, you are thinking of the following model:</p>

<ul>
<li><p>you have a memory <span class="math-container">$m$</span>, for instance of size <span class="math-container">$O(\log n)$</span>.</p></li>
<li><p>at each step, you read a new letter <span class="math-container">$a\in\Sigma$</span> of your stream, and you are allowed to modify your memory <span class="math-container">$m$</span></p></li>
<li><p>you then have to say whether the word under you new sliding window shifted by <span class="math-container">$1$</span> is in <span class="math-container">$L$</span>, based solely on <span class="math-container">$m$</span>.</p></li>
</ul>

<p>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.</p>

<p><strong>Memory constraint</strong></p>

<p>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 <span class="math-container">$u$</span> and <span class="math-container">$v$</span> of length <span class="math-container">$n$</span> that give rise to the same memory state <span class="math-container">$m$</span>.
Then, let <span class="math-container">$d$</span> be the first position where <span class="math-container">$u$</span> and <span class="math-container">$v$</span> differ, and consider that your stream continues with <span class="math-container">$0^d$</span>. After having read this suffix, you will have the same memory <span class="math-container">$m'$</span>, 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 <span class="math-container">$u$</span> and <span class="math-container">$v$</span>, your answer is wrong for one of the two.</p>

<p><strong>Time constraint</strong></p>

<p>It is possible to recognize any regular language <span class="math-container">$L$</span> with quasi-constant amortized time. The time complexity is the one from a union-find-delete (UFD) data structure.
For instance <a href="https://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/Union-Find%20with%20Constant%20Time%20Deletions.pdf" rel="noreferrer">this paper</a> shows that operations union, makeset and delete can be done in constant time, and the find operation in reverse Ackermann (so at most <span class="math-container">$5$</span> for any input value making sense in the physical word, see wikipedia on <a href="https://en.wikipedia.org/wiki/Disjoint-set_data_structure" rel="noreferrer">union-find</a>).</p>

<p>Let <span class="math-container">$A$</span> be a DFA recognizing <span class="math-container">$L$</span>, with states <span class="math-container">$Q$</span>, transition function <span class="math-container">$\delta:Q\times\Sigma\to Q$</span>, and initial state <span class="math-container">$q_0.$</span>
Let <span class="math-container">$k=|Q|$</span>, since <span class="math-container">$L$</span> is fixed <span class="math-container">$k$</span> is a constant.</p>

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

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

<p>So in order to know whether the current word is in <span class="math-container">$L$</span>, it suffices to identify the label <span class="math-container">$q$</span> of partition of the identifier <span class="math-container">$\gamma$</span> (corresponding to the word <span class="math-container">$u_0$</span>), and check whether <span class="math-container">$q$</span> is accepting.</p>

<p>When a new letter <span class="math-container">$a$</span> is read, we update the memory as follows:</p>

<ul>
<li>the identifier <span class="math-container">$\gamma$</span> is deleted from the UFD structure</li>
<li>a new identifier <span class="math-container">$\gamma$</span> is added, and joins the partition labeled <span class="math-container">$q_0$</span>. 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.</li>
<li>the current index <span class="math-container">$\gamma$</span> is updated to <span class="math-container">$\gamma'=\gamma+1\mod n$</span>.</li>
<li>all labels of partitions are updated to their <span class="math-container">$a$</span>-successors: <span class="math-container">$q'=\delta(q,a)$</span> for each label <span class="math-container">$q$</span>. Partitions that get the same label are merged.</li>
</ul>

<p>All these operations are either constant time or in quasi-constant amortized time.</p>

CC BY-SA 4.0
2019-11-19T19:42:44.137Z
Questions remains about incremental time complexity for non commutative languages though so I will not accept yet your anwser.
C.P.
CC BY-SA 4.0
2019-11-20T12:33:33.843Z
@C.P. Just to be sure, in your last question you require that updating the memory is done in constant time at each step ?
Denis
CC BY-SA 4.0
2019-11-21T07:14:47.380Z
Currently, your algorithm works in quasi-constant *amortized* time. I am wondering if we cannot implement the same idea in constant time with $|Q|$ ordered lists with a pointer at the beginning and a pointer at the end of the list (you always pop/push the smallest values of indexes). I will try to formalize.
holf
CC BY-SA 4.0
2019-11-21T09:33:24.870Z
@holf yes would be nice but I don't see how to avoid a non-constant cost, when merging the ordered lists when two states have the same successor. This is necessary if you want to keep $|Q|$ ordered lists.
Denis
CC BY-SA 4.0
2019-11-21T13:12:30.487Z
@Denis: I agree, you need a fusion operator and it is not clear how you can do better than UF. But you have more structure in the way elements are inserted/deleted so I was wondering whether one can have amortized constant time with a specific datastructure on your algo.
holf
CC BY-SA 4.0
2019-11-21T13:15:40.290Z
@holf yes that's possible, for instance we know that every inserted element will be deleted exactly n steps later. Maybe a careful analysis of the already existing structure in this context yields amortized constant time.
Denis
CC BY-SA 4.0
2019-11-19T17:01:21.057Z
2019-11-21T09:50:43.483Z
2019-11-21T09:50:43.483Z
Denis
<h2>Context</h2>

<p>Let <span class="math-container">$\mathcal{L}$</span> be a fixed regular language and let (<span class="math-container">$\mathcal{Q}, \Sigma, \delta, q_0, \mathcal{F})$</span> be an automaton recognizing <span class="math-container">$\mathcal{L}$</span>.</p>

<p>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.</p>

<h2>Claim</h2>

<p>We can maintain <span class="math-container">$\mathcal{L}$</span> in constant (non-amortized) time for a window of constant size. </p>

<p>Let us first show how we can maintain in <span class="math-container">$O(\ln(n))$</span> 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.</p>

<h2>Proof of the <span class="math-container">$O(\ln(n))$</span> bound</h2>

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

<p>The idea here is to build a <a href="https://en.wikipedia.org/wiki/Segment_tree" rel="nofollow noreferrer">segment tree</a> over the infinite word that allows us to query the effect of the sliding window in time <span class="math-container">$O(\ln(n))$</span>. Note that <span class="math-container">$\bar{\delta}(w_1 w_2) = \bar{\delta}(w_2) \circ \bar{\delta}(w_1)$</span> therefore the effect of a word can, indeed, be computed with such a tree.</p>

<p>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. </p>

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

<p><a href="https://i.sstatic.net/jXteY.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/jXteY.png" alt="Trees A, B, and C"></a></p>

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

<p>Exchanging trees can be done in <span class="math-container">$O(1)$</span>. Adding a letter or removing a letter at depth <span class="math-container">$k$</span> can be done in <span class="math-container">$O(k)$</span>: we locate in <span class="math-container">$O(k)$</span> 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 <span class="math-container">$O(k)$</span> by going upwards in the tree. Therefore, we have an <span class="math-container">$O(\ln(n))$</span> algorithm. Note that reading the effect of the whole sliding window can be done by combining the effect of the roots of <span class="math-container">$A$</span>, <span class="math-container">$B$</span> and <span class="math-container">$C$</span> and thus in <span class="math-container">$O(1)$</span>.</p>

<p>Note that this structure does not require the sliding window to be of constant size <span class="math-container">$n$</span> but only that we alternate between insertion and deletion (it will be useful for the next proof). </p>

<h2>Proof of the constant amortized bound</h2>

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

<p><a href="https://i.sstatic.net/FLdgz.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/FLdgz.png" alt="Example of sliding window decomposition into (1), (2) and (3)"></a></p>

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

<p>The effect of (2) can be maintained in non-amortized <span class="math-container">$O(1)$</span> as we only add letters at the end of the current chunk, or restart from an empty chunk.</p>

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

<h2>Proof of the constant non-amortized bound</h2>

<p>In the proof above, we have an algorithm that uses <span class="math-container">$O(1)$</span> computation at all steps plus <span class="math-container">$O(\ln(n))$</span> every <span class="math-container">$O(\ln(n))$</span> steps. The basic idea here is to use a small amount of computation at each of the steps to amortize the <span class="math-container">$O(\ln(n))$</span> cost. </p>

<p>For the effect of (1), this is easy, when we are in a block <span class="math-container">$C_i$</span> we compute the effect of suffixes for the block <span class="math-container">$C_{i+1}$</span>, for each new letter removed in <span class="math-container">$C_i$</span> we compute a new suffix of <span class="math-container">$C_{i+1}$</span>. This is <span class="math-container">$O(1)$</span>.</p>

<p>For the effect of (2), there is nothing to do as it was already <span class="math-container">$O(1)$</span>.</p>

<p>For the effect of (3), it is more complex. In the algorithm that we used for the amortized complexity, each <span class="math-container">$O(\ln(n))$</span> steps we remove and add a chunk. When removing a chunk, we must locate in <span class="math-container">$O(\ln(n))$</span> where the chunk to remove is located (note that it may be in binary tree <span class="math-container">$B$</span> or even  <span class="math-container">$C$</span>), remove it, and update upwards the effect of the parent nodes. This modification of <span class="math-container">$O(\ln(n))$</span> can be performed by doing some <span class="math-container">$O(1)$</span> computation step each time the window is modified, resulting in <span class="math-container">$O(1)$</span> non-amortized time. Note that, while we perform these operations in place, the effects annotating the nodes of the affected tree <span class="math-container">$A$</span>, <span class="math-container">$B$</span> or <span class="math-container">$C$</span> 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 <span class="math-container">$\mathcal{L}$</span> or not, and this annotation is modified last, when the deletion has actually taken place.</p>

<p>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 <span class="math-container">$C_{i+1}$</span> up to <span class="math-container">$C_{j-2}$</span> and thus we will have a block (4) computing the effect of <span class="math-container">$C_{j-1}$</span>. </p>

<p><a href="https://i.sstatic.net/ru0Ru.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ru0Ru.png" alt="Sliding window decomposition into (1), (2), (3) and (4)"></a></p>

<p>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.</p>

<p>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 <span class="math-container">$C$</span>, and we remove a node in tree <span class="math-container">$C$</span> which will be swapped with <span class="math-container">$B$</span> and <span class="math-container">$A$</span>). 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 <span class="math-container">$O(\ln(n))$</span> 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.</p>

<h2>Case of a variable-size window</h2>

<p>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 <span class="math-container">$O(\ln(n))$</span> 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 <span class="math-container">$O(1)$</span> 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. </p>

CC BY-SA 4.0
2020-04-29T21:29:56.163Z
2020-04-30T08:51:32.247Z
2020-04-30T08:51:32.247Z
Louis
<p>This seems to be exactly the type of question studied by Moses Ganardi and
coauthors in recent years. In particular <a href="https://dx.doi.org/10.4230/LIPIcs.STACS.2018.31" rel="nofollow noreferrer">this paper</a> and <a href="https://dx.doi.org/10.4230/LIPIcs.STACS.2019.29" rel="nofollow noreferrer">this extension</a>
prove nice trichotomies.</p>

CC BY-SA 4.0
2020-04-29T06:56:45.597Z
Nice, but from a shallow look these papers seem to be about the space complexity of the problem, not the time complexity (e.g., the $O(1)$ time with $O(n)$ space part of the question).
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2019-12-04T23:12:34.993Z
2019-12-04T23:12:34.993Z
Georg Zetzsche
<p>Let <span class="math-container">$L\subseteq \Sigma^*$</span> be a language of finite words and <span class="math-container">$n&gt;0$</span> some integer.</p>

<p>I would like to know if anything is known on the time and space complexity with respect to <span class="math-container">$n$</span> to check for membership in <span class="math-container">$L$</span> for a sliding window of size <span class="math-container">$n$</span> 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 <em>window</em> seen as a word to the language <span class="math-container">$L$</span>.</p>

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

<p>Case of interest (at least for me) includes:</p>

<ol>
<li><span class="math-container">$L$</span> is the Parity language over <span class="math-container">$\{0, 1\}$</span>, the number of <span class="math-container">$1$</span> is even, or in regexp: <span class="math-container">$(0^* + 10^*1)^*$</span> </li>
<li><span class="math-container">$L$</span> is the Majority language over <span class="math-container">$\{0,1\}$</span>, there are more <span class="math-container">$1$</span> than <span class="math-container">$0$</span>.</li>
<li><span class="math-container">$L$</span> is the language over <span class="math-container">$\{0,1,e\}$</span> such that there exists a <span class="math-container">$0$</span> before a <span class="math-container">$1$</span>. </li>
<li><span class="math-container">$L$</span> is an arbitary regular language. </li>
</ol>

<p>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 <span class="math-container">$\mathcal{O}(n)$</span>, can we reply in time <span class="math-container">$\mathcal{O}(1)$</span>? </p>

<automata-theory><complexity><streaming-algorithms><sliding-window>
Constraints on sliding windows
C.P.
# Constraints on sliding windows

(Asked by: username_0 on 2019-11-19)

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)$?

**Tags:** automata-theory, complexity, streaming-algorithms, sliding-window

---

## 4 answers

### Answer by username_1 on 2020-05-03. Score: 6 | Accepted answer

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](https://en.wikipedia.org/wiki/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](https://www.mimuw.edu.pl/~bojan/papers/forests-dlt.pdf). 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.

> **Comments:**
> **username_2**: This can also be seen as the standard amortized O(1) algorithm to maintain a deque using two stacks (here the stacks are the prefixes and suffixes from the guardian, on which the effect can be computed incrementally), but modified to guarantee non-amortized O(1) by starting to re-pack the two stacks as soon as they become too imbalanced (= building a new guardian).  

---

### Answer by username_3 on 2019-11-19. Score: 8

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](https://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/Union-Find%20with%20Constant%20Time%20Deletions.pdf) 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](https://en.wikipedia.org/wiki/Disjoint-set_data_structure)).

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.

> **Comments:**
> **username_0**: Questions remains about incremental time complexity for non commutative languages though so I will not accept yet your anwser.  
> **username_3**: @C.P. Just to be sure, in your last question you require that updating the memory is done in constant time at each step ?  
> **username_4**: Currently, your algorithm works in quasi-constant *amortized* time. I am wondering if we cannot implement the same idea in constant time with $|Q|$ ordered lists with a pointer at the beginning and a pointer at the end of the list (you always pop/push the smallest values of indexes). I will try to formalize.  
> **username_3**: @holf yes would be nice but I don't see how to avoid a non-constant cost, when merging the ordered lists when two states have the same successor. This is necessary if you want to keep $|Q|$ ordered lists.  
> **username_4**: @Denis: I agree, you need a fusion operator and it is not clear how you can do better than UF. But you have more structure in the way elements are inserted/deleted so I was wondering whether one can have amortized constant time with a specific datastructure on your algo.  
> **username_3**: @holf yes that's possible, for instance we know that every inserted element will be deleted exactly n steps later. Maybe a careful analysis of the already existing structure in this context yields amortized constant time.  

---

### Answer by username_1 on 2020-04-29. Score: 6

## 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](https://en.wikipedia.org/wiki/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:

[![Trees A, B, and C](https://i.sstatic.net/jXteY.png)](https://i.sstatic.net/jXteY.png)

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).

[![Example of sliding window decomposition into (1), (2) and (3)](https://i.sstatic.net/FLdgz.png)](https://i.sstatic.net/FLdgz.png)

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}$.

[![Sliding window decomposition into (1), (2), (3) and (4)](https://i.sstatic.net/ru0Ru.png)](https://i.sstatic.net/ru0Ru.png)

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 by username_5 on 2019-12-04. Score: 4

This seems to be exactly the type of question studied by Moses Ganardi and
coauthors in recent years. In particular [this paper](https://dx.doi.org/10.4230/LIPIcs.STACS.2018.31) and [this extension](https://dx.doi.org/10.4230/LIPIcs.STACS.2019.29)
prove nice trichotomies.

> **Comments:**
> **username_2**: Nice, but from a shallow look these papers seem to be about the space complexity of the problem, not the time complexity (e.g., the $O(1)$ time with $O(n)$ space part of the question).  

---

