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

Vanessa Kosoy

cs.FLMar 27, 2026

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

Authors: Vanessa Kosoy

Organizations: Faculty of Mathematics, Technion – Israel Institute of Technology, Haifa, Israel 3200003. · Computational Rational Agents Laboratory (coral-research.org), 2810 N Church St PMB 49028, Wilmington, DE 19802.

Abstract

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.

Figures & tables

1	Input: base $k$ , state $\{D^{(j)},u^{(j)}\}_{j\geq 0}$ , new symbol $a\in\Sigma$
2	let $\mathrm{idx}\leftarrow$ index of $a$ in $\Sigma$
3	for $j=0,1,\dots$
4	append $\mathrm{idx}$ to $u^{(j)}$
5	if $\|u^{(j)}\|<k$
6	return
7	else

Algorithm 1 HDP update

1	Input: base $k$ , state $\{D^{(j)},u^{(j)}\}_{j\geq 0}$
2	$V\leftarrow\{(a,a)\mid a\in\Sigma\}$
3	for $j=0,1,\dots$
4	$V_{\mathrm{next}}\leftarrow\emptyset$
5	for $(q,b)\in V$
6	for $\mathrm{idx}<\|D^{(j+1)}\|$ such that $u^{(j)}q\sqsubseteq D^{(j+1)}[\mathrm{idx}]$
7	add $(\mathrm{idx},b)$ to $V_{\mathrm{next}}$

Algorithm 2 HDP predict

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Variables: history $h\leftarrow\lambda$ , complexity bound $c\leftarrow 1$ , length bound $l\leftarrow 1$ .
1	for $t=0,1,2,\dots$
2	$V\leftarrow\{u\in\Sigma^{*}\mid h\sqsubseteq u,\;C(u)\leq c,\;\|u\|\leq l\}$
3	for $a\in\Sigma$
4	$N_{a}\leftarrow\|\{u\in V\mid\|u\|>t,\;u[t]=a\}\|$
5	$\hat{x}_{t}\leftarrow\arg\max_{a\in\Sigma}N_{a}$ (ties broken by a fixed ordering of $\Sigma$ )
6	receive $x[t]$

Appendix

Algorithm 3 Plurality Algorithm

1	Input: index $i<n$ , symbol $a\in\Sigma$
2	$L\leftarrow n-i$
3	$R_{\mathrm{start}}\leftarrow\mathrm{ISA}[i]$
4	$\mathrm{left}\leftarrow R_{\mathrm{start}}$ , $\mathrm{right}\leftarrow n-1$
5	$R_{\mathrm{limit}}\leftarrow R_{\mathrm{start}}$
6	while $\mathrm{left}\leq\mathrm{right}$
7	$\mathrm{mid}\leftarrow\lfloor(\mathrm{left}+\mathrm{right})/2\rfloor$

Appendix

Algorithm 4 Pattern range search via suffix array oracle

1	Procedure $\mathrm{IPC}(i,a)$
2	$\mathrm{range}\leftarrow\mathrm{PatternRangeSearch}(i,a)$
3	if $\mathrm{range}=\bot$
4	return $0$
5	else
6	$(r_{\mathrm{start}},r_{\mathrm{end}})\leftarrow\mathrm{range}$
7	return $r_{\mathrm{end}}-r_{\mathrm{start}}+1$

Appendix

Algorithm 5 IPC and IPM queries

1	Input: LZP state list $R$ , new symbol $a\in\Sigma$
2	if $R$ is empty
3	$R.\mathrm{append}(a)$
4	return
5	$z\leftarrow R.\mathrm{len}$
6	$\mathrm{entry}\leftarrow R[z-1]$
7	if “entry” is pair $(j,k)$

Appendix

Algorithm 6 LZP update

1	Input: LZP state list $R$ , alphabet $\Sigma$
2	if $R$ is empty
3	return arbitrary symbol
4	$z\leftarrow R.\mathrm{len}$
5	$\mathrm{entry}\leftarrow R[z-1]$
6	if “entry” is pair $(j,k)$
7	$\mathrm{len}\leftarrow k$

Appendix

Algorithm 7 LZP predict

		Tuples looked up				Buffers after the update
$t$	$x[t]$	$D^{(1)}$	$D^{(2)}$	$D^{(3)}$	$D^{(4)}$	$u^{(0)}$	$u^{(1)}$	$u^{(2)}$	$u^{(3)}$	$u^{(4)}$
0	$a$					$a$
1	$b$	$(a,b)\mapsto 0^{\ast}$					$0$
2	$b$					$b$	$0$
3	$a$	$(b,a)\mapsto 1^{\ast}$	$(0,1)\mapsto 0^{\ast}$					$0$
4	$b$					$b$		$0$

Appendix

Table 1: The updates of HDP on the word

x

of Example H.1 . In round

t

, the column

D^{(j)}

shows the tuple that is formed from the full buffer

u^{(j-1)}

(line 8 of Algorithm 1 ) and looked up in

D^{(j)}

, followed by the index that it receives (line 11 or line 14). An asterisk marks a tuple that is not found in

D^{(j)}

and is therefore appended to it (line 13). The remaining columns show the buffers after the update, where an empty cell stands for the empty buffer

\lambda

level $4$	$0$
level $3$	$0$								$1$
level $2$	$0$				$1$				$1$				$0$
level $1$	$0$		$1$		$1$		$0$		$1$		$0$		$0$		$1$
level $0$	$a$	$b$	$b$	$a$	$b$	$a$	$a$	$b$	$b$	$a$	$a$	$b$	$a$	$b$	$b$	$a$
$t$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$	$13$	$14$	$15$

Appendix

Figure 1: The aligned blocks of the word

x

of Example H.1 , labeled by their indices in the dictionaries of HDP. The bottom row shows the positions

t

. For

1\leq j\leq 4

, the row of level

j

is divided into the aligned blocks of size

2^{j}

, and every block is labeled by the index

q

s.t.

D^{(j)}[q]

represents it. This is the index that Algorithm 1 appends to

u^{(j)}

when the block is completed. The entry

D^{(j)}[q]

itself is the pair of labels of the two halves of the block, in the row of level

j-1

(where the indices of

D^{(0)}

are the symbols). For example, the block

x[4:8]=baab

is labeled by

1

at level

2

, and its halves are labeled by

1

and

0

at level

1

. Accordingly,

D^{(2)}[1]=(1,0)

$t$	$V_{1}$	$V_{2}$	$V_{3}$	$J_{t}$	Votes ( $a:b$ )	$\hat{x}_{t}$	$x[t]$
0				0	$1:1$	$a$	$a$
1				0	$1:1$	$a$	$b$	$\times$
2	$\{(0,a)\}$			1	$1:0$	$a$	$b$	$\times$
3				0	$1:1$	$a$	$a$
4	$\{(0,a),(1,b)\}$	$\{(0,a)\}$		2	$1:0$	$a$	$b$	$\times$
5	$\{(1,a)\}$			1	$1:0$	$a$	$a$

Appendix

Table 2: The predictions of HDP in the first

16

rounds on the word

x

of Example H.1 . For

j\in\{1,2,3\}

, the column

V_{j}

shows the set

V

at the beginning of iteration

j

of the loop in Algorithm 2 , where an empty cell means that the loop does not reach iteration

j

. (At the beginning of iteration

0

V=\{(a,a),(b,b)\}

in every round.) The algorithm returns in iteration

J_{t}

, and the column “Votes” shows how many of the versions in

V

vote for

a

and for

b

in this iteration. Wrong predictions are marked by

\times

Panel of Figure 2 — Figure 2: The SLP $P$ of Example I.1 as a directed acyclic graph. There is an edge for every position in every rule, labeled by this position. For example, the two edges from $q_{0}$ to $q_{1}$ correspond to the positions $0$ and $4$ of $\delta(q_{0})=q_{1}\,c\,a\,d\,q_{1}$ , and the two edges from $q_{1}$ to $a$ correspond to the positions $0$ and $3$ of $\delta(q_{1})=abra$ .

Sequence Prediction

See all 31 papers

Jul 19, 2026

Stringological sequence prediction II: Right-to-left automaticity and related complexity measures

In a previous paper, we began the study of sequence prediction algorithms adapted to stringological word complexity measures. One measure we considered was left-to-right (most-significant-digit-first) automaticity. Here, we show a statistically and computationally efficient algorithm adapted to the

dual'' right-to-left (least-significant-digit-first) automaticity, which turns out to be substantially different for our purpose. We also demonstrate a prediction algorithm for a more expressive measure that we call

arithmetic repetition complexity''. In particular, the latter can be used for predicting the so-called mix-automatic sequences.

Vanessa Kosoy

Faculty of Mathematics, Technion, Haifa, Israel · Computational Rational Agents Laboratory, Delaware, USA

Sequence Prediction Sequence Modeling

Ask PDF

Sep 17, 2026

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

In previous papers, we began the study of sequence prediction algorithms adapted to stringological word complexity measures. In particular, we defined a complexity measure called Arithmetic Repetition Complexity (ARC) which admits a polynomial-time prediction algorithm with a mistake bound quasilinear in the complexity. Here, we show a weaker complexity measure related to ARC that admits an especially efficient prediction algorithm: an algorithm that runs in quasilinear time and polylog space for appropriate highly-structured sequences. The complexity measure is defined via a restricted class of "zipline programs" (a variant of straight-line programs), which we call layered. We thus get a less expressive measure with a more efficient algorithm (compared to our results for ARC), demonstrating a possible tradeoff.

Vanessa Kosoy

Faculty of Mathematics, Technion, Haifa, Israel · Computational Rational Agents Laboratory, Delaware, USA

Sequence Modeling Sequence Prediction

Ask PDF

Sep 24, 2026

The Cost of Long Memory: State, Context, and Stability Complexity in Sequence Models

Long-range temporal dependence poses a resource question for sequence models: for a specified predictive-memory law, how much state, context, or dynamical criticality is required in order to forecast accurately? We study this question directly in forecasting risk. For algebraically decaying predictive memory, we prove matching upper and lower approximation bounds for exponential and finite-state modes. The best

r

-mode forecast error decays as

e^{-Θ(\sqrt r)}

, so reaching forecast error

τ

needs

r=Θ(\log^2(1/τ))

states or modes. Earlier curse-of-memory results establish broad limitations of stable recurrent models under different approximation notions; here both sides match for one canonical predictive target in forecast risk, which fixes the optimal resource exponent for that target. We then show that genuine fractional long memory changes the geometry itself. In particular, forecast error is measured after fractional integration, prediction from a finite context of length

L

has an exact

1/L

leading order, and a fixed fractional strength

d

keeps the square-log state-complexity law. Near the short-memory boundary, we identify the relevant

d^2

and

d^4

scales and give a uniform constructive law in the intermediate regime. For nonlinear contextual recurrences with uniformly contractive state dynamics, we derive an exponential first-chaos envelope and an explicit necessary condition that relates forecast accuracy to the contraction margin. Vanishing forecasting error on an algebraic target forces the recurrence quantitatively toward criticality, a condition that is necessary and not by itself sufficient. Finite-sample Kullback--Leibler calculations further connect the predictive geometry to statistical information. Theorem-matched experiments with contractive state-space, gated recurrent, and attention models reproduce the state and stability predictions.

Yuheng Song

School of Management, Huazhong University of Science and Technology

Sequence Prediction Time Series Forecasting Recurrent Neural Networks State Space Models

Ask PDF

Abstract

Sequence Prediction

Explore similar work

Stringological sequence prediction II: Right-to-left automaticity and related complexity measures

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

The Cost of Long Memory: State, Context, and Stability Complexity in Sequence Models