I am struggling with the following problem:

Given a set of finite binary strings $S=\{s_1,\ldots,s_k\}$, we say that a string $u$ is a concatenation over $S$ if it is equal to $s_{i_{1}} s_{i_{2}} \cdots s_{i_{t}}$ for some indices $i_1,\ldots, i_t \in \{1,\ldots, k\}.$

Your friend is considering the following problem: given two sets of finite binary strings $A=\{a_1,\ldots,a_m\}$ and $B=\{b_1,\ldots , b_n \}$, does there exist any string $u$ so that $u$ is both a concatenation over $A$ and a concatenation over $B$?

Your friend announces "at least the problem is in $\mathcal{NP}$, since I would just have to exhibit such a string $u$ in order to prove the answer is yes." You point out that this an inadequate explanation. How do we know the shortest string $u$ doesn't have length exponential in the size of the input?

Prove the following: If there is a string $u$ that is a concatenation over both $A$ and $B$, then there is such a string whose length is bounded by a polynomial in the sum of the lengths of the strings in $A\cup B$.

Now, I have actually found a solution and the solution claims that the maximum length of $u$ is at most $n^2L^2$ where we assume $m \leq n$ and $L$ denotes the maximum length of any string in $A \cup B$. The solution then goes on to exhibit a proof by contradiction using the pigeonhole principle to show that if we assume $u$ has length greater than $n^2L^2$ we arrive at a contradiction.

My question is where does the bound $n^2L^2$ come from? I know that $n$ is the number of strings in set $B$ and $L$ is the max length string in $A \cup B$. But I feel as if the largest possible concatenation over both would be more like $2nL$ since we would need to include every string in both $A$ and $B$ and the longest string in either is $L$ and there are at most $n$ strings in each. What am I missing? I think I can handle the remainder of the proof once I understand where the $n^2L^2$ bound is coming from.

  • $\begingroup$ It would be easier to read and understand your post if you used Latex typeset instead of plain text. $\endgroup$
    – fade2black
    Oct 18 '17 at 21:26
  • 1
    $\begingroup$ Presumably it comes from the proof. To answer that question, you'll need to understand the proof. Have you tried understanding the proof? The proof starts by assuming $u$ has length greater than $n^2 L^2$; see where in the proof that assumption is used, and probably you'll have the answer to your question. $\endgroup$
    – D.W.
    Oct 18 '17 at 22:58

You can also prove this using automata theory. For a set $S = \{s_1,\ldots,s_k\}$ of strings over $\Sigma$, consider the following language over $\Sigma \cup \{1,\ldots,k\}$: $$ L_S = (1s_1+2s_2+\cdots+ks_k)^+. $$ This language is accepted by a DFA of size roughly $\|S\| := |s_1|+\cdots+|s_k|$. The exact size depends on the model of DFA - in our case it makes sense to ask for at most one transition out of each state with a given label (rather than exactly one transition, as is usually the case).

Now we want to do the same, but for two sets of strings $A = \{a_1,\ldots,a_m\}$, $B = \{b_1,\ldots,b_n\}$. To this end, we consider languages $L_A,L_B$ which are defined as before, but with two differences:

  • $1,\ldots,k$ are replaced with $A_1,\ldots,A_m$ for $L_A$ and $B_1,\ldots,B_n$ for $L_B$.
  • The symbols $A_1,\ldots,A_m$ are ignored in $L_B$, and the symbols $B_1,\ldots,B_n$ are ignored in $L_A$.

As an example, suppose that $A = \{a,ba\}$ and that $B = \{ab,a\}$. Then the following word will be in our language: $A_1B_1aA_2bB_2a$.

As before, we can construct DFAs for $L_A,L_B$ having roughly $\|A\|,\|B|$ states, respectively. Using the product construction, we get a DFA of size roughly $\|A\|\cdot\|B\|$ for the intersection. It is well-known (and can be proved using the pigeonhole principle) that if a DFA having $N$ states accepts any word, then it accepts some word of size less than $N$. This implies your claim.

In terms of lower bounds, it is easy to refute your conjecture that $2nL$ is enough. Consider $A = \{ 0^L \}$ and $B = \{ 0^{L-1} \}$. It is not hard to check that the minimal solution has length $L(L-1) \approx L^2$.

It's less clear what is the correct dependence on $n$.


I think the intuition is something like this (warning, not very rigorous):

We make two copies of $u$, call them $u_a$ and $u_b$, one in terms of the $a_i$ and one in terms of $b_i$. We place them side by side as shown. Then we 'break off' the last string of either $u_a$ or $u_b$ to make a endpoint, which is probably going to be unequal as shown below.

enter image description here Now, we keep breaking stuff off, until we get an endpoint that we have seen before.

How long will this take? It will be bounded by the number of different endpoints we have. How many such endpoints? We can create all endpoints by choosing some pair of $a_i$ and $b_j$, there are $n^2$ such pairs, and then we align them, there are up to $L$ different ways to align them. So total number of different endpoints is $n^2 L$.

So we know that if we keep breaking off bits, we will eventually encounter an endpoint that we have seen before. Then we can shorten the original string $u$, by cutting out the portion between the 2 occurrences of the same endpoint. We keep repeating this until $u$ is as short as possible, which would happen once $u$ has no more 'repeated endpoints'.

What is the length of $u$ now? $u$ contains all most $n^2 L$ endpoints, and each endpoint is at most $L$ characters between them (because the endpoints are separated by at most one or two blocks), that is a total length of $n^2 L^2$.

Could you also post a link to the proof so we can take a look!


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.