Compute 'insertable' letters in a regular language

Let $L$ a regular language and define the subsequence closure of $L$ as

$\qquad \displaystyle S(L) = \{ w \mid \exists w' \in L.\ w \text{ subsequence of } w'\}$.

The problem I want to solve is to find for such subsequences $w \in S(L)$ which letters can be inserted into them so that the result is also in $S(L)$. Formally:

Given $w_1\dots w_n \in S(L)$, output all pairs $(i,a) \in \{0,\dots,n\} \times \Sigma$ for which $w_1 \dots w_{i} a w_{i+1} \dots w_n \in S(L)$.

Consider, for instance, the language$\{ab, abc, abcc\}$. The string $b$ is in $S(L)$ and inserting $a$ at the beginning -- corresponding to $(0,a)$ -- yields $ab \in S(L)$. On the other hand, the string $cb$ is not in $S(L)$; there is no way to convert it to a language string by insertion.

Using this language, if the input string is $b$ the possible insertions I am looking for are $(0,a)$ and $(1,c)$ at the end. If the input string is $bc$ the possible insertions are $(0,a), (1,c)$ and $(2,c)$.

The use of this algorithm is in a user interface: the user builds strings belonging to the language starting from an empty string and adding one character at a time in different positions. At each step the UI prompts the user with all the possible valid letters in all the possible insertion positions.

I have a working naive algorithm that involves a lot of back-tracking, and it is way too slow even in relatively simple cases. I was wondering if there is something better, or -- failing that -- if there are any available studies of this problem.

• @Giles: I expanded the question with more explanations, I it is clearer now. – MiMo Sep 3 '12 at 14:45
• @MiMo: Now we figured out what you want, I reformulated your question to use standard notions and notations. I hope that's fine with you, and I am looking forward to answers! – Raphael Sep 3 '12 at 19:55
• Note that $S(L)$ is the downward closure of $L$ w.r.t. the subsequence relation. – Raphael Sep 3 '12 at 19:57
• For evaluating the answers, it would be nice if you stated the algorithm(ic idea) and runtime you have. – Raphael Sep 4 '12 at 5:39

Edit: The OP changed the question. What follows works for one interpretation of the original question.

I'm assuming you are given a DFA $A = (Q,\Sigma,\delta,q_0,F)$. The method can be adapted to handle NFAs.

Let the word be $w = w_1 \ldots w_n$. For each $i \in \{0,\ldots,n\}$, calculate the state $s_i$ that the automaton reaches after reading the prefix of length $i$ of $w$. For each $i \in \{0,\ldots,n\}$ and each accepting state $q \in F$, calculate the state $t_{i,q}$ that the reverse automaton reaches when starting at $q$ and reading the reverse of the suffix of length $i$ of $w$. Let $T_i = \{ t_{i,q} : q \in Q \}$.

For each $i \in \{0,\ldots,n\}$ and each symbol $a \in \Sigma$, check whether $\delta(s_i,a) \in T_{n-i}$. If so, $a$ can be inserted at position $i$: $w_1 \ldots w_i a w_{i+1} \ldots w_n \in L(A)$.

The running time is $O(n(|\Sigma| + |Q|))$, and the method requires space $O(|Q|)$ (if implemented by going over $i = 0,\ldots,n$, in this order).

• As I understand it, that covers only some positions; those that need more insertions before a word from the language surfaces are missing. – Raphael Sep 3 '12 at 14:57
• I think this works only if the word already belong to the language - that is not my case. If you look at the example in my question and try to apply this algorithm to b you get stuck because there is no state $s_1$ – MiMo Sep 3 '12 at 15:04
• I guess that this algoritthm will work if the DFA is that of the subsequence closure of the language, instead than the one of the original language ... I wonder if there is a way to compute that DFA. – MiMo Sep 3 '12 at 21:23
• @MiMo: Sure. Add an $\varepsilon$-shortcut for every transition (and determinise). – Raphael Sep 3 '12 at 21:47
• @Raphael: apologies for my ignorance, but what is an $\epsilon$-shortcut? – MiMo Sep 3 '12 at 21:59

The solution is to compute the DFA of the subsequence closure of the original language, and then using this DFA I just used the 'trivial' algorithm: try to insert each possible symbol in each position, if the resulting word is valid for this new DFA - i.e. belongs to $S(L)$ - then the symbol can be inserted at that position.

Using the closure DFA it should be possible to use the faster algorithm suggested by Yuval Filmus in one of the other answers; I did not try because the 'trivial' algorithm already gives good enough performances: from tens of seconds with my previous solution to sub-second execution time (computing the closure DFA only once of course).

To compute the closure DFA:

1. Create a new NFA with the same start and final states of the original DFA
2. For each transition $q\stackrel{a}{\longrightarrow}q'$ in the original DFA the new NFA has two transitions: the same $q\stackrel{a}{\longrightarrow}q'$ and a null one $q\stackrel{\varepsilon}{\longrightarrow}q'$ (where $\varepsilon$ is the null transition - this is the $\varepsilon$-shortcut)
3. Generate a DFA from this NFA using the usual system - this DFA is the closure one.

(Many thanks to Raphael for the help and for suggesting the solution)

• Glad I could help. :) Note that in general, the equivalent DFA can have exponential size in the size of the NFA. So unless this cases vanishes here because of the specific modification, the preprocessing time may be huge. (What about $S(\{w\})$ for square-free $w$, for example?) – Raphael Sep 4 '12 at 21:46
• @Raphael: thanks again. The languages I am working with are defined using an XML schema - somewhat restricting the possible cases. In my tests so far with schemas we are using the DFA size was very reasonable and the pre-processing time negligible... – MiMo Sep 4 '12 at 22:22