7
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Questions remains about incremental time complexity for non commutative languages though so I will not accept yet your anwser. $\endgroup$ – C.P. Nov 19 at 19:42
  • $\begingroup$ @C.P. Just to be sure, in your last question you require that updating the memory is done in constant time at each step ? $\endgroup$ – Denis Nov 20 at 12:33
  • $\begingroup$ 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. $\endgroup$ – holf Nov 21 at 7:14
  • $\begingroup$ @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. $\endgroup$ – Denis Nov 21 at 9:33
  • $\begingroup$ @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. $\endgroup$ – holf Nov 21 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.