<p>With an idea by <a href="http://louis.jachiet.com/" rel="nofollow noreferrer">Louis Jachiet</a>, we managed to design a PTIME algorithm for this task. Long story short, it's a dynamic programming algorithm where you sort the <span class="math-container">$b$</span>'s by decreasing "ending time" (i.e., by increasing <span class="math-container">$q_i$</span> above), consider the <span class="math-container">$b$</span>'s by intervals of "starting time" (the <span class="math-container">$p_i$</span> above), and restrict the search to greedy schedulings that follow the idea for <span class="math-container">$(ab)^*$</span> given in the question. Somewhat surprisingly, the problem is in PTIME even if the target regular language is also given as part of the input (i.e., not fixed). Also, the algorithm would also work if, instead of copies of the letter <span class="math-container">$a$</span>, we had a fixed word on some alphabet; however all the <span class="math-container">$b$</span>'s should be the same symbol.</p>

<p>I'll rephrase the problem of my question to a problem where each <span class="math-container">$b$</span> comes with a pair <span class="math-container">$(s_i, e_i)$</span> saying that this <span class="math-container">$b$</span> must be inserted with at least <span class="math-container">$s_i$</span> <span class="math-container">$a$</span>'s to the left, and strictly less than <span class="math-container">$e_i$</span> <span class="math-container">$a$</span>'s to the left. This is equivalent to the original problem phrasing in the question (take <span class="math-container">$s_i := p_i$</span> and <span class="math-container">$e_i := m + 1 - q_i$</span>  where <span class="math-container">$m$</span> is the number of <span class="math-container">$a$</span>'s), but it is a bit easier to reason with: we can now see the constraints as defining an <em>interval</em> <span class="math-container">$[s_i, e_i[$</span> of positions where the insertion can take place. By a <em>position</em> <span class="math-container">$p$</span>, I mean a position in the word of <span class="math-container">$a$</span>, i.e., <span class="math-container">$0 \leq p \leq m$</span>; when we insert multiple <span class="math-container">$b$</span>'s then they do not change positions of other <span class="math-container">$b$</span>'s in the word of <span class="math-container">$a$</span>'s. Besides, since all <span class="math-container">$b$</span>'s are the same symbol, it suffices to know the position where we insert them; we don't care about the relative positions of the <span class="math-container">$b$</span>'s that are all inserted at the same position in the word of <span class="math-container">$a$</span>'s.</p>

<p>I will need to talk about <strong>state pair sets</strong> of the automaton, which are just sets <span class="math-container">$S$</span> containing pairs <span class="math-container">$(q, q')$</span> of states. Given a word <span class="math-container">$w$</span> over <span class="math-container">$\{a, b\}$</span>, I will write <span class="math-container">$\phi(w)$</span> for the state pair set that it achieves, i.e., all <span class="math-container">$(q, q')$</span> such that there is a path from <span class="math-container">$q$</span> to <span class="math-container">$q'$</span> labeled by <span class="math-container">$w$</span>, which can clearly be computed in PTIME from <span class="math-container">$w$</span> and an automaton representation of the word. Given two state pair sets <span class="math-container">$S$</span> and <span class="math-container">$S'$</span>, I define <span class="math-container">$S \odot S'$</span> to be the set of all state pairs <span class="math-container">$(q, q'')$</span> that can be obtained by combining a pair of <span class="math-container">$S$</span> and of <span class="math-container">$S'$</span>, formally <span class="math-container">$S \odot S' = {(q, q'') \mid \exists q', (q, q') \in S \land (q', q'') \in S'}$</span>. Notice that we have <span class="math-container">$\phi(w w') = (\phi(w)) \odot (\phi(w'))$</span> for any words <span class="math-container">$w$</span> and <span class="math-container">$w'$</span>. What is more, the question of whether a word is accepted or not boils down to checking whether <span class="math-container">$\phi(w)$</span> contains a pair <span class="math-container">$(q_0, q_f)$</span> for a final state <span class="math-container">$q_f$</span>. (What I'm redefining here is basically the transition monoid of the automaton, for those familiar with it.)</p>

<p>I will consider the <span class="math-container">$b$</span>'s by decreasing ending time <span class="math-container">$e_i$</span>, and break ties in some arbitrary but consistent way, so when I talk about the <span class="math-container">$i$</span>-th <span class="math-container">$b$</span>, with constraints <span class="math-container">$(s_i, e_i)$</span>, then it is the <span class="math-container">$i$</span>-th <span class="math-container">$b$</span> according to this order that I fixed.</p>

<p>Let me now claim that, if we can achieve a word <span class="math-container">$w$</span> by insertions of <span class="math-container">$b$</span>'s into the <span class="math-container">$a$</span>'s, then we can achieve the same word <span class="math-container">$w$</span> by doing insertions following a <strong>greedy strategy</strong>: when I insert the <span class="math-container">$i$</span>-th <span class="math-container">$b$</span> at a position <span class="math-container">$p$</span> in the word of <span class="math-container">$a$</span>'s, then all subsequent <span class="math-container">$b$</span>'s that could also go at that position (i.e., <span class="math-container">$s_j \leq p &lt; e_j$</span> for some <span class="math-container">$j$</span>) are inserted to the left of that position, i.e., their position is <span class="math-container">$p'$</span> with <span class="math-container">$p' \leq p$</span>. Let's see why we can always restrict to greedy strategies without loss of generality. Consider a stategy to do insertions to achieve <span class="math-container">$w$</span>, and let's see that we can change it into a greedy strategy that achieves the same word. Consider a violation in the current strategy where we insert the <span class="math-container">$i$</span>-th <span class="math-container">$b$</span> at position <span class="math-container">$p$</span> (so <span class="math-container">$p_i \leq p &lt; e_i$</span>) and the <span class="math-container">$j$</span>-th <span class="math-container">$b$</span> (with <span class="math-container">$j &gt; i$</span>) could also go at that position (so <span class="math-container">$p_j \leq p &lt; e_j$</span>) but it was inserted to the right, i.e., <span class="math-container">$p' &gt; p$</span>. Let's see why the <span class="math-container">$i$</span>-th <span class="math-container">$b$</span> can also be inserted at <span class="math-container">$p'$</span>, which justifies that we can fix that violation by swapping the two insertions, and thus iteratively repair any strategy to a greedy strategy.  By definition of the order, we have <span class="math-container">$e_j \leq e_i$</span>, so as <span class="math-container">$p' &lt; e_j$</span> we have <span class="math-container">$p' &lt; e_i$</span>. Now, as <span class="math-container">$p_i \leq p$</span> and <span class="math-container">$p &lt; p'$</span>, we have <span class="math-container">$p_i \leq p'$</span>. So indeed <span class="math-container">$p \in [p_i, e_i[$</span> and we can indeed fix the violation by inserting the <span class="math-container">$i$</span>-th <span class="math-container">$b$</span> at <span class="math-container">$p'$</span> and the <span class="math-container">$j$</span>-th <span class="math-container">$b$</span> at <span class="math-container">$p$</span>.</p>

<p>Now I can explain the dynamic algorithm. We will compute, for all <span class="math-container">$0 \leq i \leq j \leq m$</span>, for all <span class="math-container">$0 \leq s \leq s' \leq m$</span>, for all <span class="math-container">$0 \leq k \leq n$</span> (with <span class="math-container">$n$</span> the number of intervals), the set <span class="math-container">$S(i, j, s, s', k)$</span> which is the union of the state pair sets over all words that can be obtained by taking the subword of <span class="math-container">$a$</span>'s from the <span class="math-container">$i$</span>-th <span class="math-container">$a$</span> (included) to the <span class="math-container">$j$</span>-th <span class="math-container">$a$</span> (excluded), performing insertions of <span class="math-container">$b$</span>'s using exactly the <span class="math-container">$b$</span>'s with position <span class="math-container">$i \geq k$</span> in the order (numbering them from <span class="math-container">$0$</span> to <span class="math-container">$n-1$</span>) and with starting time <span class="math-container">$s \leq s_i &lt; s'$</span>, and considering the word obtained in this fashion (containing <span class="math-container">$j - i$</span> <span class="math-container">$a$</span>'s and some <span class="math-container">$b$</span>'s inserted before, after, or between them).</p>

<p>The quantity that we wish to compute to solve our problem is <span class="math-container">$S(0, m, 0, m, 0)$</span>, telling us what can be achieved by inserting all intervals in the whole word of <span class="math-container">$m$</span> <span class="math-container">$a$</span>'s; we then simply check if there is a pair of the form <span class="math-container">$(q_0, q_f)$</span> in the result, with <span class="math-container">$q_0$</span> the initial state and <span class="math-container">$q_f$</span> a final state.</p>

<p>The base case is the <span class="math-container">$S(i, j, s, s', n)$</span>, where we ask what can be achieved without any insertions: this is simply the effect of the <span class="math-container">$a$</span>'s on their own, formally, it is <span class="math-container">$\phi(a^{j-i})$</span>.</p>

<p>Now, for the inductive step, consider <span class="math-container">$S(i, j, s, s', k)$</span> with <span class="math-container">$k &lt; n$</span>. Consider the <span class="math-container">$k$</span>-th copy of <span class="math-container">$b$</span> and its interval <span class="math-container">$[s_k, e_k[$</span>. If we don't have <span class="math-container">$s \leq s_k &lt; s'$</span>, then we are not considering this <span class="math-container">$b$</span>, so we simply have <span class="math-container">$S(i, j, s, s', k) = S(i, j, s, s', k+1)$</span>. Otherwise, we are considering the <span class="math-container">$k$</span>-th <span class="math-container">$b$</span>, and we claim that:</p>

<p><span class="math-container">$$S(i, j, s, s', k) = \hspace{-1cm} \bigcup_{\max(i, s_k) \leq p \leq \min(j, e_k-1)}\hspace{-1cm} S(i, p+1, s, p+1, k+1) \odot \phi(b) \odot S(p+1, j, p+1, s', k+1).$$</span></p>

<p>In particular, if the interval for the <span class="math-container">$k$</span>-th <span class="math-container">$b$</span> does not overlap with <span class="math-container">$[i, j[$</span>, then <span class="math-container">$S(i, j, s, s', k) = \emptyset$</span> (meaning that we cannot perform the insertions).</p>

<p>To see why this formula holds, observe that we must insert the <span class="math-container">$k$</span>-th <span class="math-container">$b$</span> as we are considering it, and this insertion must be at a position <span class="math-container">$p$</span> such that <span class="math-container">$s_k \leq p &lt; e_k$</span>, so <span class="math-container">$s_k \leq p \leq e_k-1$</span>, and also we are considering insertions in the subword from the <span class="math-container">$i$</span>-th <span class="math-container">$a$</span> (included) and the <span class="math-container">$j$</span>-th <span class="math-container">$a$</span> (excluded) so <span class="math-container">$i \leq p \leq j$</span> (we can insert immediately after the end of this subword of <span class="math-container">$a$</span>). Now, all remaining <span class="math-container">$b$</span>'s (strictly after <span class="math-container">$k$</span>) with starting position in <span class="math-container">$[s, s'[$</span> are partitioned between those with starting position in <span class="math-container">$[s, p+1[$</span> and those with starting position in <span class="math-container">$[p+1, s'[$</span>. Let's argue that these <span class="math-container">$b$</span>'s must be inserted as we claim, i.e., the first ones in the subword of <span class="math-container">$a$</span> between <span class="math-container">$i$</span> included and <span class="math-container">$p+1$</span> excluded (so at or before <span class="math-container">$p$</span>) and the second ones between <span class="math-container">$p+1$</span> included and <span class="math-container">$j$</span> excluded (so strictly after <span class="math-container">$p$</span>). For the second ones, this is clear, as their starting position is <span class="math-container">$\geq p+1$</span> so they must be inserted at position <span class="math-container">$p+1$</span> or later. For the first <span class="math-container">$b$</span>'s, either their ending time is <span class="math-container">$\leq p+1$</span>, in which case they must necessarily be inserted strictly before position <span class="math-container">$p+1$</span>; or their ending time is <span class="math-container">$&gt; p+1$</span>, but in this case, as their starting position is <span class="math-container">$&lt; p+1$</span>, this means that they could legally be inserted at position <span class="math-container">$p$</span> where we inserted the <span class="math-container">$k$</span>-th copy of <span class="math-container">$b$</span>; now by definition of a greedy strategy, since they come after this <span class="math-container">$k$</span>-th <span class="math-container">$b$</span> in the order which we inserted at a position <span class="math-container">$p$</span>, then they must be inserted at a position <span class="math-container">$\leq p$</span>.</p>

<p>Formally, correctness can be shown by showing inductively that the <span class="math-container">$S(i, j, s, s', k)$</span> contains the right state pair set: one direction is because what we compute really corresponds to a way to perform the insertions; the other is because any way to perform the insertions is equivalent to a greedy strategy, and all greedy strategies are represented by the above reasoning.</p>

<p>This algorithm clearly establishes that the problem is in PTIME, with complexity like <span class="math-container">$O(n \times n^4 \times m \times \mathrm{Poly}(A))$</span> where <span class="math-container">$A$</span> is the automaton. We're not claiming that this is optimal. :)</p>

CC BY-SA 4.0
2019-10-20T22:09:28.980Z
2019-10-21T18:57:07.870Z
2019-10-21T18:57:07.870Z
Antoine Amarilli 'a3nm'
<p>Fix a regular language <span class="math-container">$L$</span> on the alphabet <span class="math-container">$\{a, b\}$</span>, and consider the following problem. I am given as input:</p>

<ul>
<li>some number <span class="math-container">$m \in \mathbb{N}$</span> of copies of the letter <span class="math-container">$a$</span>, and</li>
<li>some number <span class="math-container">$n \in \mathbb{N}$</span> of copies of the letter <span class="math-container">$b$</span> but each copy <span class="math-container">$1 \leq i \leq n$</span> comes with a constraint expressed as a pair of integers <span class="math-container">$(p_i, q_i)$</span> which means: "there must be at least <span class="math-container">$p_i$</span> <span class="math-container">$a$</span>'s to the left of this <span class="math-container">$b$</span> and at least <span class="math-container">$q_i$</span> <span class="math-container">$a$</span>'s to the right of this <span class="math-container">$b$</span>".</li>
</ul>

<p>My goal is to decide if I can construct a word of length <span class="math-container">$m + n$</span> with <span class="math-container">$m$</span> letters <span class="math-container">$a$</span> and <span class="math-container">$n$</span> letters <span class="math-container">$b$</span> that falls in the language <span class="math-container">$L$</span> and where every copy of <span class="math-container">$b$</span> was put at a position that satisfies its constraints. (Formally: there is an injective function <span class="math-container">$f$</span> from <span class="math-container">$\{1, \ldots, n\}$</span> to <span class="math-container">$\{1, \ldots, n+m\}$</span> such that, letting <span class="math-container">$A$</span> be the elements of <span class="math-container">$\{1, \ldots, n+m\}$</span> that are not in the image of <span class="math-container">$f$</span>, for each <span class="math-container">$1 \leq i \leq n$</span>, the set <span class="math-container">$A$</span> contains at least <span class="math-container">$p_i$</span> integers that are <span class="math-container">$&lt; f(i)$</span> and at least <span class="math-container">$q_i$</span> integers that are <span class="math-container">$&gt; f(i)$</span>.) Note that the <span class="math-container">$b$</span>'s can be put in any order (as long as their constraints are satisfied), they needn't be put in the order in which they are in the input. In other words, <span class="math-container">$f$</span> need not be an increasing function.</p>

<p><strong>Is this problem in polynomial time for every regular language <span class="math-container">$L$</span>, or is there a language <span class="math-container">$L$</span> for which the problem is NP-hard?</strong></p>

<p>I have a PTIME greedy algorithm that works if <span class="math-container">$L$</span> has only one word of every length, e.g., it is something like <span class="math-container">$(ab)^*$</span>. In this case, you should go over the even positions (where <span class="math-container">$b$</span>'s must go) and at each position put a copy of <span class="math-container">$b$</span> which is available and which is as constrained as possible, i.e., the constraint <span class="math-container">$p_i$</span> is satisfied, and the constraint <span class="math-container">$q_i$</span> is as large as possible. It is clear that this algorithm respects the constraints if it succeeds, and that this is always the best way to place the <span class="math-container">$b$</span>'s. However when <span class="math-container">$L$</span> contains multiple words of length <span class="math-container">$m+n$</span> then this no longer works and I can't see a dynamic algorithm to solve the problem.</p>

<p>(This question relates to <a href="https://cstheory.stackexchange.com/questions/40304/testing-whether-letters-can-be-scheduled-to-achieve-a-word-in-a-regular-language">this earlier question of mine</a> but the main difference that the alphabet is now restricted to be <span class="math-container">$\{a, b\}$</span> so the previous proof does not work. The problem can also be equivalently phrased in terms of topological sorts in which case it is a rephrasing of a problem in <a href="https://www.paperman.name/#open.dag_page/index" rel="noreferrer">this list</a>.)</p>

<cc.complexity-theory><ds.algorithms><fl.formal-languages><regular-language>
Arranging letters to make a word in a regular language
Antoine Amarilli 'a3nm'
# Arranging letters to make a word in a regular language

(Asked by: username_0 on 2019-03-26)

Fix a regular language $L$ on the alphabet $\{a, b\}$, and consider the following problem. I am given as input:

* some number $m \in \mathbb{N}$ of copies of the letter $a$, and
* some number $n \in \mathbb{N}$ of copies of the letter $b$ but each copy $1 \leq i \leq n$ comes with a constraint expressed as a pair of integers $(p\_i, q\_i)$ which means: "there must be at least $p\_i$ $a$'s to the left of this $b$ and at least $q\_i$ $a$'s to the right of this $b$".

My goal is to decide if I can construct a word of length $m + n$ with $m$ letters $a$ and $n$ letters $b$ that falls in the language $L$ and where every copy of $b$ was put at a position that satisfies its constraints. (Formally: there is an injective function $f$ from $\{1, \ldots, n\}$ to $\{1, \ldots, n+m\}$ such that, letting $A$ be the elements of $\{1, \ldots, n+m\}$ that are not in the image of $f$, for each $1 \leq i \leq n$, the set $A$ contains at least $p\_i$ integers that are $< f(i)$ and at least $q\_i$ integers that are $> f(i)$.) Note that the $b$'s can be put in any order (as long as their constraints are satisfied), they needn't be put in the order in which they are in the input. In other words, $f$ need not be an increasing function.

**Is this problem in polynomial time for every regular language $L$, or is there a language $L$ for which the problem is NP-hard?**

I have a PTIME greedy algorithm that works if $L$ has only one word of every length, e.g., it is something like $(ab)^\*$. In this case, you should go over the even positions (where $b$'s must go) and at each position put a copy of $b$ which is available and which is as constrained as possible, i.e., the constraint $p\_i$ is satisfied, and the constraint $q\_i$ is as large as possible. It is clear that this algorithm respects the constraints if it succeeds, and that this is always the best way to place the $b$'s. However when $L$ contains multiple words of length $m+n$ then this no longer works and I can't see a dynamic algorithm to solve the problem.

(This question relates to [this earlier question of mine](https://cstheory.stackexchange.com/questions/40304/testing-whether-letters-can-be-scheduled-to-achieve-a-word-in-a-regular-language) but the main difference that the alphabet is now restricted to be $\{a, b\}$ so the previous proof does not work. The problem can also be equivalently phrased in terms of topological sorts in which case it is a rephrasing of a problem in [this list](https://www.paperman.name/#open.dag_page/index).)

**Tags:** cc.complexity-theory, ds.algorithms, fl.formal-languages, regular-language


---

## 1 answers

### Answer by username_0 on 2019-10-20. Score: 4

With an idea by [Louis Jachiet](http://louis.jachiet.com/), we managed to design a PTIME algorithm for this task. Long story short, it's a dynamic programming algorithm where you sort the $b$'s by decreasing "ending time" (i.e., by increasing $q\_i$ above), consider the $b$'s by intervals of "starting time" (the $p\_i$ above), and restrict the search to greedy schedulings that follow the idea for $(ab)^\*$ given in the question. Somewhat surprisingly, the problem is in PTIME even if the target regular language is also given as part of the input (i.e., not fixed). Also, the algorithm would also work if, instead of copies of the letter $a$, we had a fixed word on some alphabet; however all the $b$'s should be the same symbol.

I'll rephrase the problem of my question to a problem where each $b$ comes with a pair $(s\_i, e\_i)$ saying that this $b$ must be inserted with at least $s\_i$ $a$'s to the left, and strictly less than $e\_i$ $a$'s to the left. This is equivalent to the original problem phrasing in the question (take $s\_i := p\_i$ and $e\_i := m + 1 - q\_i$ where $m$ is the number of $a$'s), but it is a bit easier to reason with: we can now see the constraints as defining an *interval* $[s\_i, e\_i[$ of positions where the insertion can take place. By a *position* $p$, I mean a position in the word of $a$, i.e., $0 \leq p \leq m$; when we insert multiple $b$'s then they do not change positions of other $b$'s in the word of $a$'s. Besides, since all $b$'s are the same symbol, it suffices to know the position where we insert them; we don't care about the relative positions of the $b$'s that are all inserted at the same position in the word of $a$'s.

I will need to talk about **state pair sets** of the automaton, which are just sets $S$ containing pairs $(q, q')$ of states. Given a word $w$ over $\{a, b\}$, I will write $\phi(w)$ for the state pair set that it achieves, i.e., all $(q, q')$ such that there is a path from $q$ to $q'$ labeled by $w$, which can clearly be computed in PTIME from $w$ and an automaton representation of the word. Given two state pair sets $S$ and $S'$, I define $S \odot S'$ to be the set of all state pairs $(q, q'')$ that can be obtained by combining a pair of $S$ and of $S'$, formally $S \odot S' = {(q, q'') \mid \exists q', (q, q') \in S \land (q', q'') \in S'}$. Notice that we have $\phi(w w') = (\phi(w)) \odot (\phi(w'))$ for any words $w$ and $w'$. What is more, the question of whether a word is accepted or not boils down to checking whether $\phi(w)$ contains a pair $(q\_0, q\_f)$ for a final state $q\_f$. (What I'm redefining here is basically the transition monoid of the automaton, for those familiar with it.)

I will consider the $b$'s by decreasing ending time $e\_i$, and break ties in some arbitrary but consistent way, so when I talk about the $i$-th $b$, with constraints $(s\_i, e\_i)$, then it is the $i$-th $b$ according to this order that I fixed.

Let me now claim that, if we can achieve a word $w$ by insertions of $b$'s into the $a$'s, then we can achieve the same word $w$ by doing insertions following a **greedy strategy**: when I insert the $i$-th $b$ at a position $p$ in the word of $a$'s, then all subsequent $b$'s that could also go at that position (i.e., $s\_j \leq p < e\_j$ for some $j$) are inserted to the left of that position, i.e., their position is $p'$ with $p' \leq p$. Let's see why we can always restrict to greedy strategies without loss of generality. Consider a stategy to do insertions to achieve $w$, and let's see that we can change it into a greedy strategy that achieves the same word. Consider a violation in the current strategy where we insert the $i$-th $b$ at position $p$ (so $p\_i \leq p < e\_i$) and the $j$-th $b$ (with $j > i$) could also go at that position (so $p\_j \leq p < e\_j$) but it was inserted to the right, i.e., $p' > p$. Let's see why the $i$-th $b$ can also be inserted at $p'$, which justifies that we can fix that violation by swapping the two insertions, and thus iteratively repair any strategy to a greedy strategy. By definition of the order, we have $e\_j \leq e\_i$, so as $p' < e\_j$ we have $p' < e\_i$. Now, as $p\_i \leq p$ and $p < p'$, we have $p\_i \leq p'$. So indeed $p \in [p\_i, e\_i[$ and we can indeed fix the violation by inserting the $i$-th $b$ at $p'$ and the $j$-th $b$ at $p$.

Now I can explain the dynamic algorithm. We will compute, for all $0 \leq i \leq j \leq m$, for all $0 \leq s \leq s' \leq m$, for all $0 \leq k \leq n$ (with $n$ the number of intervals), the set $S(i, j, s, s', k)$ which is the union of the state pair sets over all words that can be obtained by taking the subword of $a$'s from the $i$-th $a$ (included) to the $j$-th $a$ (excluded), performing insertions of $b$'s using exactly the $b$'s with position $i \geq k$ in the order (numbering them from $0$ to $n-1$) and with starting time $s \leq s\_i < s'$, and considering the word obtained in this fashion (containing $j - i$ $a$'s and some $b$'s inserted before, after, or between them).

The quantity that we wish to compute to solve our problem is $S(0, m, 0, m, 0)$, telling us what can be achieved by inserting all intervals in the whole word of $m$ $a$'s; we then simply check if there is a pair of the form $(q\_0, q\_f)$ in the result, with $q\_0$ the initial state and $q\_f$ a final state.

The base case is the $S(i, j, s, s', n)$, where we ask what can be achieved without any insertions: this is simply the effect of the $a$'s on their own, formally, it is $\phi(a^{j-i})$.

Now, for the inductive step, consider $S(i, j, s, s', k)$ with $k < n$. Consider the $k$-th copy of $b$ and its interval $[s\_k, e\_k[$. If we don't have $s \leq s\_k < s'$, then we are not considering this $b$, so we simply have $S(i, j, s, s', k) = S(i, j, s, s', k+1)$. Otherwise, we are considering the $k$-th $b$, and we claim that:

$$S(i, j, s, s', k) = \hspace{-1cm} \bigcup\_{\max(i, s\_k) \leq p \leq \min(j, e\_k-1)}\hspace{-1cm} S(i, p+1, s, p+1, k+1) \odot \phi(b) \odot S(p+1, j, p+1, s', k+1).$$

In particular, if the interval for the $k$-th $b$ does not overlap with $[i, j[$, then $S(i, j, s, s', k) = \emptyset$ (meaning that we cannot perform the insertions).

To see why this formula holds, observe that we must insert the $k$-th $b$ as we are considering it, and this insertion must be at a position $p$ such that $s\_k \leq p < e\_k$, so $s\_k \leq p \leq e\_k-1$, and also we are considering insertions in the subword from the $i$-th $a$ (included) and the $j$-th $a$ (excluded) so $i \leq p \leq j$ (we can insert immediately after the end of this subword of $a$). Now, all remaining $b$'s (strictly after $k$) with starting position in $[s, s'[$ are partitioned between those with starting position in $[s, p+1[$ and those with starting position in $[p+1, s'[$. Let's argue that these $b$'s must be inserted as we claim, i.e., the first ones in the subword of $a$ between $i$ included and $p+1$ excluded (so at or before $p$) and the second ones between $p+1$ included and $j$ excluded (so strictly after $p$). For the second ones, this is clear, as their starting position is $\geq p+1$ so they must be inserted at position $p+1$ or later. For the first $b$'s, either their ending time is $\leq p+1$, in which case they must necessarily be inserted strictly before position $p+1$; or their ending time is $> p+1$, but in this case, as their starting position is $< p+1$, this means that they could legally be inserted at position $p$ where we inserted the $k$-th copy of $b$; now by definition of a greedy strategy, since they come after this $k$-th $b$ in the order which we inserted at a position $p$, then they must be inserted at a position $\leq p$.

Formally, correctness can be shown by showing inductively that the $S(i, j, s, s', k)$ contains the right state pair set: one direction is because what we compute really corresponds to a way to perform the insertions; the other is because any way to perform the insertions is equivalent to a greedy strategy, and all greedy strategies are represented by the above reasoning.

This algorithm clearly establishes that the problem is in PTIME, with complexity like $O(n \times n^4 \times m \times \mathrm{Poly}(A))$ where $A$ is the automaton. We're not claiming that this is optimal. :)


---

