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

arXiv: https://arxiv.org/abs/2603.26852 · HTML: https://mlsanity.com/paper/2603.26852/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 33 references that are in the map.
- First posted on arXiv 27 Mar 2026.

## Builds on (most cited first, 7 of 7)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [A Selective Overview of Deep Learning](https://mlsanity.com/paper/1904.05526/) (2019)
- [Bayesian Context Trees: Modelling and exact inference for discrete time series](https://mlsanity.com/paper/2007.14900/) (2020)
- [On statistical learning via the lens of compression](https://mlsanity.com/paper/1610.03592/) (2016)
- [Techniques for Inferring Context-Free Lindenmayer Systems With Genetic Algorithm](https://mlsanity.com/paper/1906.08860/) (2019)
- [On the Hardness of Learning Regular Expressions](https://mlsanity.com/paper/2510.04834/) (2025)
- [Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space](https://mlsanity.com/paper/2308.03635/) (2023)

## Built on by (most cited first, 1 of 1)

- [Stringological sequence prediction II: Right-to-left automaticity and related complexity measures](https://mlsanity.com/paper/2607.17369/) (2026)

## Abstract (arXiv)

We propose novel algorithms for sequence prediction based on ideas from stringology. These algorithms are time and space efficient and satisfy mistake bounds related to particular stringological complexity measures of the sequence. In this work (the first in a series) we focus on two such measures: (i) the size of the smallest straight-line program that produces the sequence, and (ii) the number of states in the minimal automaton that can compute any symbol in the sequence when given its position in base k as input. These measures are interesting because multiple rich classes of sequences studied in combinatorics of words (automatic sequences, morphic sequences, characteristic words) have low complexity and hence high predictability in this sense.