2022 Developer Survey is open! Take survey.

# Tag Info

### Are there survey papers in theoretical computer science?

Yes! These survey series come to mind: Foundations and Trends in TCS (many authors put a free version on their web page) Theory of Computing Graduate Surveys SIGACT News Complexity Column (and also ...
• 35.6k

### Seeking references on writing a long string $\ell$ as concatenation of shorter strings $s_1, s_2, s_3, ...$

(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). For k=1 the problem is in polynomial-...
• 116
### Seeking references on writing a long string $\ell$ as concatenation of shorter strings $s_1, s_2, s_3, ...$
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\}$.
This answer is inspired by this question. The conjecture is false, for the following reason. Consider the alphabet $\Sigma=\{0,1\}$, and the language $A=\{0^n1(0|1)^n|n>0\}$. This language is ...