1
$\begingroup$

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.

$\endgroup$
  • $\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
2
$\begingroup$

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

$\endgroup$

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.