# Represent string as concatenations

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

• 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
• for context free, isn't the first problem undecidable? – Chao Xu Oct 17 '12 at 15:44
• For finite $S$, both problems have finite search space and are therefore computable. – Raphael Oct 17 '12 at 20:37
• 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

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