If $S_1,S_2$ are set of strings, then $S_1S_2 = \{s_1s_2|s_1\in S_1, s_2\in S_2\}$. $S^0=\{\epsilon\}$, $\epsilon$ is the empty string. $S^n = S^{n-1}S$.

Two related problems about represent string as concatenation of other strings.

  1. Given a finite set $S$ of strings, how to decide if there exist a string can be written as concatenations of elements in $S$ in two different ways?

  2. Given a finite set $S$ of strings and $n$, how can one compute the smallest set of strings $T$, such that $S\subset T^n$?

(Bonus: what about infinite $S$, at least when it's regular? For the second problem when $S$ is infinite, we might ask to find a minimal $T$ under set inclusion.)

  • 2
    What can you assume on the set of strings? Are they finite, regular, decidable? – A.Schulz Oct 17 '12 at 7:40
  • They are finite. Of course it be nice to generalize to regular languages. – Chao Xu Oct 17 '12 at 15:42
  • 1
    for context free, isn't the first problem undecidable? – Chao Xu Oct 17 '12 at 15:44
  • 1
    For finite $S$, both problems have finite search space and are therefore computable. – Raphael Oct 17 '12 at 20:37
  • 1
    for (1) are you talking about concatenations of arbitrary length? if the length is unbounded, not sure the search space is finite & therefore computable as raphael asserts. on short glance sound vaguely similar to Post Correspondence Problem to me. for (2) are the strings in T of arbitrary length? it might help to start by proving search space is finite (that does not appear trivial to me).... – vzn Oct 18 '12 at 15:18
up vote 5 down vote accepted

I will try (1) and go for infinite (the bonus).

The finite case is called the code problem: finding possible decompositions is like decoding. Its classical algorithm is called Sardinas–Patterson. It is not immediately clear it is a finite search space. The lengths of the decomposition might be long. Still it is not Post Correspondence as that has additional restrictions.

The finite case has a simple regular language solution: for every pair of distinct $s,t \in S$ test whether the regular set $s S^* \cap t S^*$ is empty. (The Sardinas-Patterson tries that "in parallel".) This does not work in the infinite case as there would be infinitely many $s,t$ to test.

In the infinite (but regular) case I would build a new finite state automaton based on an automaton for $S$. It simulates in parallel the two different decompositions by keeping track of a pair of states, one for each decomposition. On a letter both pairs make a step on the same letter. In a final state each component may either restart (it has seen an element in $S$) or proceed (trying to find a longer word in $S$). Now we need one additional boolean addition to the state-pair as we need to check whether the two components made different choices in at least one point. Accept if both simulations end in a final state (and we have seen a point where the two decompositions differed). Now again there are no two different decompositions for the same string iff the language of the automaton is empty.

And indeed, for context-free the problem must be undicidable, but I do not have a reference at hand now.

  • Check if a context free language is ambiguous is undecidable. I wonder how to reduce that problem to this one... – Chao Xu Oct 21 '12 at 19:46
  • PS. For (2) there might be minimal size, but no smallest. Consider $S=\{ aaba \}$ and $n=3$. Then I have at least three solutions for minimal size $T$: $T = \{ \epsilon, aaba \}$, $T = \{ a, ba \}$, and $T = \{ a, ab \}$. – Hendrik Jan Oct 25 '12 at 23:52

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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