2022 Developer Survey is open! Take survey.
10 votes

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 ...
user avatar
2 votes

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-...
user avatar
  • 116
2 votes

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\}$.
user avatar
2 votes

Establishing competing memory limits for pushdown automata

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 ...
user avatar
  • 7,350

Only top scored, non community-wiki answers of a minimum length are eligible