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

From papers

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

lenMDL(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 fi0f_i\geq 0 satisfy

0fi(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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.