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.
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?
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$\begingroup$ What can you assume on the set of strings? Are they finite, regular, decidable? $\endgroup$A.Schulz– A.Schulz2012年10月17日 07:40:45 +00:00Commented Oct 17, 2012 at 7:40
-
$\begingroup$ They are finite. Of course it be nice to generalize to regular languages. $\endgroup$Chao Xu– Chao Xu2012年10月17日 15:42:41 +00:00Commented Oct 17, 2012 at 15:42
-
1$\begingroup$ for context free, isn't the first problem undecidable? $\endgroup$Chao Xu– Chao Xu2012年10月17日 15:44:37 +00:00Commented Oct 17, 2012 at 15:44
-
1$\begingroup$ For finite $S,ドル both problems have finite search space and are therefore computable. $\endgroup$Raphael– Raphael2012年10月17日 20:37:35 +00:00Commented Oct 17, 2012 at 20:37
-
1$\begingroup$ 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).... $\endgroup$vzn– vzn2012年10月18日 15:18:58 +00:00Commented Oct 18, 2012 at 15:18
1 Answer 1
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.
-
$\begingroup$ Check if a context free language is ambiguous is undecidable. I wonder how to reduce that problem to this one... $\endgroup$Chao Xu– Chao Xu2012年10月21日 19:46:53 +00:00Commented Oct 21, 2012 at 19:46
-
$\begingroup$ 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 \}$. $\endgroup$Hendrik Jan– Hendrik Jan2012年10月25日 23:52:16 +00:00Commented Oct 25, 2012 at 23:52
Explore related questions
See similar questions with these tags.