Stringological sequence prediction III: layered ziplines and a tradeoff between efficiency and expressivity

arXiv:2609.19940 · cs.FL, cs.DS, cs.LG · Submitted 2026-09-17 · Read on arXiv

cs.FL, cs.DS, cs.LG

Submitted: 2026-09-17

Updated: 2026-09-17

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Consistency — 50× in this paper · explained in 3 episodes
• Accuracy — 7× in this paper · explained in 1 episode
• Abstention — 4× in this paper · explained in 1 episode
• Pruning — 4× in this paper · explained in 4 episodes
• Arithmetic Repetition Complexity — 3× in this paper
• Verification — 3× in this paper · explained in 2 episodes
• Generalization — 2× in this paper · explained in 13 episodes
• Generalization Bounds — 2× in this paper · explained in 2 episodes
• Plurality Branch — 2× in this paper
• Calibration — 1× in this paper · explained in 7 episodes
• Core — 1× in this paper · explained in 2 episodes
• Elias — 1× in this paper · explained in 2 episodes
• Regularization — 1× in this paper · explained in 3 episodes
• Tabular Plurality — 1× in this paper
• Topological Order — 1× in this paper · explained in 2 episodes

Sources

• Bayesian Context Trees: Modelling and exact inference for discrete time series
• Stringological sequence prediction I: efficient algorithms for predicting highly repetitive sequences
• Stringological sequence prediction II: Right-to-left automaticity and related complexity measures

Related papers

• Positive-Data Learning of Fixed-Observation Linear MCFGs from Working Binary Presentations