Constraints on sliding windows Let $L\subseteq \Sigma^*$ be a language of finite words and $n&gt;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:


$L$ is the Parity language over $\{0, 1\}$, the number of $1$ is even, or in regexp: $(0^* + 10^*1)^*$ 
$L$ is the Majority language over $\{0,1\}$, there are more $1$ than $0$.
$L$ is the language over $\{0,1,e\}$ such that there exists a $0$ before a $1$. 
$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)$?
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.