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.

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 (e.g. using a deque).

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

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