Questions tagged [open-problem]

Problems without an answer after substantial efforts by many users. This tag indicates the problem is of graduate research level and beyond. Do not use this tag for a homework question. Do not use this tag for a question that do not have a solution that can be proved mathematically.

1 question with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1 vote
0 answers
25 views

Determine whether we can pack $(r_1, \dots, r_k)$ copies of the variables $(A_1, \dots, A_k)$ into a string $s$, in time polynomial in $|s|$?

Let $s \in \Sigma^*$ be a finite string over alphabet $\Sigma$. Find all "compressible" substrings of $s$, that is substrings $t \leqslant s$ (notation) such that $t\alpha t \leqslant s$ ...
Daniel Donnelly's user avatar