<p>This is part of <em>coding theory</em> if you view <span class="math-container">$\ell$</span> as a message and <span class="math-container">$s_i$</span> as its components. As such, it is studied in bioinformatics as well, where the underlying alphabet could be <span class="math-container">$\{A,C,G,T\}$</span>.</p>

CC BY-SA 4.0
2022-05-02T18:41:14.763Z
Right. In coding theory, one also cares about the uniqueness of such a decomposition, otherwise the code would be ambiguous. See here: https://en.m.wikipedia.org/wiki/Sardinas%E2%80%93Patterson_algorithm
Hermann Gruber
CC BY-SA 4.0
2022-05-02T01:05:24.623Z
2022-05-02T01:05:24.623Z
Bjørn Kjos-Hanssen
<p>(Earlier as comment). This would be called the word problem in a (free) monoid. E.g. see the books by Lothaire (<a href="https://www-igm.univ-mlv.fr/%7Eberstel/Lothaire" rel="nofollow noreferrer">https://www-igm.univ-mlv.fr/~berstel/Lothaire</a>). For k=1 the problem is in polynomial-time using dynamic programming. For the power of a word, <span class="math-container">$\ell^k$</span> you can show that it is sufficient to check <span class="math-container">$k \leq \sum |s_i|$</span>. (If bigger <span class="math-container">$k$</span> were necessary, then there would be two different occurrences of <span class="math-container">$\ell\ell$</span> in which the boundary between the two <span class="math-container">$\ell$</span> is matched with the same <span class="math-container">$s_i$</span> in the same position, which means that <span class="math-container">$k$</span> wasn't minimal. By checking all <span class="math-container">$k$</span> then, the problem is still in polynomial time.</p>

CC BY-SA 4.0
2022-05-03T15:54:54.363Z
2022-05-03T15:54:54.363Z
user66277
<p>Given: a (long binary) string <span class="math-container">$\ell$</span>, and a set of (short) strings, <span class="math-container">$s_1, s_2, ...$</span> . Can <span class="math-container">$\ell$</span> be written as concatenation of the short strings?
I am looking for references on: the name of the problem, text or papers, algorithms or calculators.</p>
<p>Similar problems or other wordings:</p>
<p>Let <span class="math-container">$S=\{s_1,s_2, ...\}$</span>. Is there <span class="math-container">$n$</span> such that <span class="math-container">$\ell$</span> belongs to <span class="math-container">$S^n$</span>?
Are there <span class="math-container">$m,k$</span> such that <span class="math-container">$\ell^k$</span> belongs to <span class="math-container">$S^m$</span>?</p>
<p>Let <span class="math-container">$L=\{\ell_1,\ell_2, ...\}$</span>. Find smallest <span class="math-container">$k$</span> such that an element of <span class="math-container">$L^k$</span> is in an <span class="math-container">$S^m$</span>?</p>

CC BY-SA 4.0
2022-05-01T20:32:04.293Z
This would be called the word problem in a (free) monoid. E.g. see the books by Lothaire (http://www-igm.univ-mlv.fr/~berstel/Lothaire/). For $k = 1$ the problem is in polynomial-time using dynamic programming. For power of a word, $\ell^k$ you can show that it is sufficient to check $k \leq \sum |s_i|$. (If bigger $k$ were necessary, then there would be two different occurrences of $\ell\ell$ in which the boundary between the two $\ell$ is matched with the same $s_i$ in the same position, which means $k$ wasn't minimal. By checking all $k$ then, the problem is still in polynomial time.
user66277
CC BY-SA 4.0
2022-05-02T18:34:47.440Z
@user66277 maybe you want to convert your comment into an answer.
Hermann Gruber
CC BY-SA 4.0
2022-05-03T15:55:42.800Z
Sure, converted to answer.
user66277
<reference-request><co.combinatorics>
Seeking references on writing a long string $\ell$ as concatenation of shorter strings $s_1, s_2, s_3, ...$
Maesumi
# Seeking references on writing a long string $\ell$ as concatenation of shorter strings $s_1, s_2, s_3, ...$

(Asked by: username_0 on 2022-04-30)

Given: a (long binary) string $\ell$, and a set of (short) strings, $s\_1, s\_2, ...$ . Can $\ell$ be written as concatenation of the short strings?
I am looking for references on: the name of the problem, text or papers, algorithms or calculators.

Similar problems or other wordings:

Let $S=\{s\_1,s\_2, ...\}$. Is there $n$ such that $\ell$ belongs to $S^n$?
Are there $m,k$ such that $\ell^k$ belongs to $S^m$?

Let $L=\{\ell\_1,\ell\_2, ...\}$. Find smallest $k$ such that an element of $L^k$ is in an $S^m$?

**Tags:** reference-request, co.combinatorics

> **Comments:**
> **username_1**: This would be called the word problem in a (free) monoid. E.g. see the books by Lothaire (http://www-igm.univ-mlv.fr/~berstel/Lothaire/). For $k = 1$ the problem is in polynomial-time using dynamic programming. For power of a word, $\ell^k$ you can show that it is sufficient to check $k \leq \sum |s_i|$. (If bigger $k$ were necessary, then there would be two different occurrences of $\ell\ell$ in which the boundary between the two $\ell$ is matched with the same $s_i$ in the same position, which means $k$ wasn't minimal. By checking all $k$ then, the problem is still in polynomial time.  
> **username_2**: @username_1 maybe you want to convert your comment into an answer.  
> **username_1**: Sure, converted to answer.  

---

## 2 answers

### Answer by username_3 on 2022-05-02. Score: 2

This is part of *coding theory* if you view $\ell$ as a message and $s\_i$ as its components. As such, it is studied in bioinformatics as well, where the underlying alphabet could be $\{A,C,G,T\}$.

> **Comments:**
> **username_2**: Right. In coding theory, one also cares about the uniqueness of such a decomposition, otherwise the code would be ambiguous. See here: https://en.m.wikipedia.org/wiki/Sardinas%E2%80%93Patterson_algorithm  

---

### Answer by username_1 on 2022-05-03. Score: 2

(Earlier as comment). This would be called the word problem in a (free) monoid. E.g. see the books by Lothaire ([https://www-igm.univ-mlv.fr/~berstel/Lothaire](https://www-igm.univ-mlv.fr/%7Eberstel/Lothaire)). For k=1 the problem is in polynomial-time using dynamic programming. For the power of a word, $\ell^k$ you can show that it is sufficient to check $k \leq \sum |s\_i|$. (If bigger $k$ were necessary, then there would be two different occurrences of $\ell\ell$ in which the boundary between the two $\ell$ is matched with the same $s\_i$ in the same position, which means that $k$ wasn't minimal. By checking all $k$ then, the problem is still in polynomial time.


---

