Symmetrical bound for the MDL code in terms of shortest-grammar length

About 21 years old · traced to

Let vv be a string, let Lm(v)L^m(v) denote the length of its shortest grammar, and let MDL⁡(v)\boldsymbol{\operatorname{MDL}}(v) denote the MDL code for vv. Let γ(n):=nf1(n)\gamma(n):=n f_1(n). Symmetrical-bound conjecture. There is an inequality

∣len⁡MDL⁡(v)−γ(Lm(v))∣≤f2(Lm(v)),\left|\operatorname{len}\operatorname{MDL}(v)-\gamma\bigl(L^m(v)\bigr)\right|\leq f_2\bigl(L^m(v)\bigr),

where the functions fi≥0f_i\geq 0 satisfy

0≤fi(n+1)−fi(n)≤cin0\leq f_i(n+1)-f_i(n)\leq \frac{c_i}{n}

for some constants cic_i. This proposed bound is intended to relate the MDL code length to the shortest-grammar length and is used in the paper's heuristic argument about vocabulary and excess code length; the source calls it probable rather than proving it.

References

Primary source

Łukasz Dȩbowski, “On Hilberg's Law and Its Links with Guiraud's Law”, arXiv:cs/0507022 (2005).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.