4
$\begingroup$

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 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.)

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.