Symmetrical bound for the MDL code in terms of shortest-grammar length
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.