Symmetrical bound for the MDL code in terms of shortest-grammar length
Let be a string, let denote the length of its shortest grammar, and let denote the MDL code for . Let . Symmetrical-bound conjecture. There is an inequality
where the functions satisfy
for some constants . 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.