Testing whether letters can be scheduled to achieve a word in a regular language I fix a regular language $L$ on an alphabet $\Sigma$, and I consider the following problem that I call letter scheduling for $L$. Informally, the input gives me $n$ letters and an interval for each letter (i.e., a minimal and maximal position), and my goal is to place each letter in its interval such that no two letters are mapped to the same position and so that the resulting $n$-letter word is in $L$. Formally:


Input: $n$ triples $(a_i, l_i, r_i)$ where $a_i \in \Sigma$ and $1 \leq l_i \leq r_i \leq n$ are integers
Output: is there a bijection $f: \{1, \ldots, n\} \to \{1, \ldots, n\}$ such that $l_i \leq f(i) \leq r_i$ for all $i$, and $a_{f^{-1}(1)} \cdots a_{f^{-1}(n)} \in L$.


Obviously this problem is in NP, by guessing a bijection $f$ and checking membership to $L$ in PTIME. My question: Is there a regular language $L$ such that the letter scheduling problem for $L$ is NP-hard?

Some initial observations:


It seems that similar problems have been studied in scheduling: we could see the problem as scheduling unit-cost tasks on a single machine while respecting starting and finishing dates. However, this latter problem is obviously in PTIME with a greedy approach, and I don't see anything in the scheduling literature for the case where tasks are labeled and we would want to achieve a word in a target regular language.
One other way to see the problem is as a special case of a bipartite maximum matching problem (between letters and positions), but again it's hard to express the constraint that we must fall in $L$.
In the specific case where $L$ is a language of the form $u^*$ for some fixed word $u$ (e.g., $(ab)^*$), then the letter scheduling problem for $L$ is in PTIME with an easy greedy algorithm: build the word from left to right, and put at each position one of the available letters which is correct relative to $L$ and has the smallest time $r_i$. (If there are no available letters which are correct, fail.) However, this does not generalize to arbitrary regular languages $L$ because for such languages we may have the choice of which kind of letter to use.
It looks like a dynamic algorithm should work, but in fact it's not so simple: it seems that you would need to memorize which set of letters that you have taken so far. Indeed, when building a word from left to right, when you have reached a position $i$, your state depends on which letters you have consumed so far. You cannot memorize the entire set because then there would be exponentially many states. But it's not so easy to "summarize" it (e.g., by how many copies of each letter were used), because to know which copies you used, it seems that you need to remember when you have consumed them (the later you have consumed them, the more letters were available). Even with a language like $(ab|ba)^*$, there may already be complicated constraints about when you should choose to take $ab$ and when you should choose to take $ba$ depending on which letters you will need later and when the letters become available.
However, as the regular language $L$ is fixed and cannot memorize so much information, I'm having a hard time finding an NP-hard problem from which I could reduce.
The problem is NP-hard for $L = A^*$ where $A$ is the finite language containing the following words:


$x111$, $x000$,
$y100$, $y010$, $y001$,
$00c11$, $01c10$, $10c01$, and $11c00$


The reduction is from the problem Graph Orientation, which is known to be NP-hard (see https://link.springer.com/article/10.1007/s00454-017-9884-9). In this problem, we are given a 3-regular undirected graph in which every vertex is labeled either "$\{1\}$" or "$\{0,3\}$". The goal is to direct the edges of the graph so that the outdegree of every vertex is in the set labeling that vertex.

The reduction needs to take as input a Graph Orientation instance and produce a list of triples as output. In this reduction, the triples we output will always satisfy certain constraints. These constraints are listed below, and we will refer to a list of triples as valid if and only if they satisfy these constraints:


The characters $x$, $y$, and $c$ are only given intervals containing exactly one index. In other words, whenever these characters are placed, they are placed in specific locations. 
For every triple $(i, l, r)$ present in the instance with $i \in \{0,1\}$, the triple $(1-i, l, r)$ is also present.
If $(\alpha, l, r)$ and $(\alpha',l',r')$ are both triples present in the instance then either $l &lt; l' \le r' &lt; r$, or $l' &lt; l \le r &lt; r'$, or $\{\alpha,\alpha'\} = \{0,1\}$ with $l = l' &lt; r = r'$.
If $(\alpha, l, r)$ is a triple then the number of triples $(\alpha', l', r')$ with $l \le l' \le r' \le r$ is exactly $r-l+1$.


Note the following lemma, proved at the end of this post.

Lemma: for a valid list of triples, the characters $x$, $y$, and $c$ must be placed exactly as indicated by the triples, and for any pair of triples $(0, l, r)$ and $(1, l, r)$, the two characters for that triple must be placed at indices $l$ and $r$.

Then the idea of the reduction is the following. 

We use pairs of triples $(0, l, r)$, and $(1, l, r)$ to represent edges. The edge goes between endpoints at index $l$ and at index $r$. Assuming we produce a valid list of triples, the characters from these two triples must be placed at $l$ and $r$, so we can treat the order in which they are placed as indicating the direction of the edge. Here $1$ is the "head" of the edge and $0$ is the "tail". In other words, if the $1$ is placed at $r$ then the edge points from $l$ to $r$ and if the $1$ is placed at $l$ then the edge points from $r$ to $l$. 

To represent vertices, we place an $x$ or $y$ character at an index and use the next three characters as the endpoints of the three edges which touch the vertex. Note that if we place an $x$, all three edges at the vertex must point in the same direction (all into the vertex or all out of the vertex) simply due to the strings that are in finite language $A$. Such vertices have outdegree $0$ or $3$, so we place an $x$ exactly for the vertices labeled $\{0,3\}$. If we place a $y$, exactly one of the three edges at the vertex must point in the same direction due to the strings in $A$. Such vertices have outdegree $1$, so we place a $y$ exactly for the vertices labeled $\{1\}$. 

In some sense, we are done. In particular, the correspondence between solving this instance and solving the Graph Orientation instance should be clear. Unfortunately, the list of triples we produce may not be valid, and so the "edges" described may not work as intended. In particular, the list of triples might not be valid because the condition that the intervals from the triples must always contain each other might not hold: the intervals from two edges may overlap without one containing the other. 

To combat this, we add some more infrastructure. In particular, we add "crossover vertices". A crossover vertex is a vertex of degree $4$ whose edges are paired such that within each pair one edge must point into the crossover vertex and one out. In other words, a crossover vertex will behave the same as just two "crossing" edges. We represent a crossover vertex by placing the character $c$ at some index $i$. Then note that the language $A$ constrains the characters at $i-1$ and $i+2$ to be opposite (one $0$ and one $1$) and the characters at $i-2$ and $i+1$ to be opposite. Thus, if we use these indices as the endpoints for the four edges at the crossover vertex, the behavior is exactly as described: the four edges are in pairs and among every pair one points in and one points out.

How do we actually place these crossovers? Well suppose we have two intervals $(l, r)$ and $(l', r')$ which overlap. WLOG, $l &lt; l' &lt; r &lt; r'$. We add the crossover character into the middle (between $l'$ and $r$). (Let's say that all along we spaced everything out so far that there's always enough space, and at the end we will remove any unused space.) Let the index of the crossover character be $i$. Then we replace the four triples $(0, l, r)$, $(1, l, r)$, $(0, l', r')$, and $(1, l', r')$ with eight triples with two each (one with character $0$ and one with character $1$) for the following four intervals $(l, i-1)$, $(i+2, r)$, $(l', i-2)$, $(i+1, r')$. Notice that the intervals don't overlap in the bad way anymore! (After this change, if two intervals overlap, one is strictly inside the other.) Furthermore, the edge from $l$ to $r$ is replaced by an edge from $l$ to the crossover vertex followed by the edge from there to $r$; these two edges are paired at the crossover vertex in such a way that one is pointed in and one is pointed out; in other words, the two edges together behave just like the one edge they are replacing.

In some sense, putting in this crossover vertex "uncrossed" two edges (whose intervals were overlapping). It is easy to see that adding the crossover vertex can't cause any additional edges to become crossed. Thus, we can uncross every pair of crossing edges by inserting enough crossover vertices. The end result still corresponds to the Graph Orientation instance, but now the list of triples is valid (the properties are all easy to verify now that we have "uncrossed" any crossing edges), so the lemma applies, the edges must behave as described, and the correspondence is actually an equivalence. In other words, this reduction is correct.



proof of lemma

Lemma: for a valid list of triples, the characters $x$, $y$, and $c$ must be placed exactly as indicated by the triples, and for any pair of triples $(0, l, r)$ and $(1, l, r)$, the two characters for that triple must be placed at indices $l$ and $r$.

proof: 

We proceed by induction on the triples by interval length. In particular, our statement is the following: for any $k$ if some triple has interval length $k$ then the character in that triple must be placed as described in the lemma.

Base case: for $k = 0$, the triple must be placing a character $x$, $y$, or $c$ at the single index inside the interval. This is exactly as described in the lemma.

Inductive case: assume the statement holds for any $k$ less than some $k'$. Now consider some triple with interval length $k'$. Then that triple must be of the form $(i, l, r)$ with $r = l+k'-1$ and $i \in \{0,1\}$. The triple $(1-i, l, r)$ must also be present. The number of triples $(\alpha',l',r')$ with $l \le l'\le r' \le r$ is exactly $r-l+1 = k'$. These triples include triples $(0, l, r)$ and $(1, l, r)$ but also $k'-2$ other triples of the form $(\alpha',l',r')$ with $l &lt; l' \le r' &lt; r$. These other triples all have interval length smaller than $k'$, so they all must place their characters as specified in the lemma. The only way for this to occur is if these triples place characters in every index starting at index $l+1$ and ending at index $r+1$. Thus, our two triples $(0, l, r)$ and $(1, l, r)$ must place their characters at indices $l$ and $r$, as described in the lemma, concluding the inductive case.

By induction, the lemma is correct.