Stringological sequence prediction I: efficient algorithms for predicting highly repetitive sequences

arXiv:2603.26852 · cs.FL, cs.DS, cs.LG · Submitted 2026-03-27 · Read on arXiv

cs.FL, cs.DS, cs.LG

Submitted: 2026-03-27

Updated: 2026-09-26

Comments: 55 pages

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

Terminology

• Suffix Array — 7× in this paper
• Lempel-Ziv Plurality — 5× in this paper
• Generalization — 3× in this paper · explained in 13 episodes
• Core — 2× in this paper · explained in 2 episodes
• Generalization Bounds — 2× in this paper · explained in 2 episodes
• Hierarchical Dictionary Plurality — 2× in this paper
• Consistency — 1× in this paper · explained in 3 episodes
• Inverse Suffix Array — 1× in this paper
• Longest Common Extension — 1× in this paper
• Random Access — 1× in this paper
• Topological Order — 1× in this paper · explained in 3 episodes
• Transformer — 1× in this paper · explained in 2 episodes

Sources

• Bayesian Context Trees: Modelling and exact inference for discrete time series
• A Family of LZ78-based Universal Sequential Probability Assignments

Related papers

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