Symmetrical bound for the MDL code in terms of shortest-grammar length
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.
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
Sign in to submit a solution.
No solutions have been posted yet.