Minimized single-string grammar size approximation.

31 Views Asked by At

Let $|\Sigma_s| = m$ alphabet and $|s| = n$ be the size of our string. Consider a minimized grammar $g$ expanding to $s$, with start symbol $S \in \Sigma_g$.

Then what's the maximum length $n$ such that $s$ has no grammar-compressible ($A\to ab; S \to AAA)$ e.g.) substrings?

Can we use this to approximate the size of a minimized single-string grammar (no compressible substrings)?