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

Vanessa Kosoy
3/27/2026
cs.FLcs.DScs.LG

No confident code implementation found for this paper.

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, Sturmian words) have low complexity and hence high predictability in this sense.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets

83% match1 repo4182015

A Brain-Inspired Sequence Learning Model based on a Logic

80% match1 repo72023

Who Needs Decoders? Efficient Estimation of Sequence-level Attributes

78% match2023

Sequence Modeling via Segmentations

78% match1 repo1772017

Auto-Regressive Next-Token Predictors are Universal Learners

78% match2 repos212023

Provable Length Generalization in Sequence Prediction via Spectral Filtering

77% match2024

Cite this paper

@article{kosoy2026stringological,
  title  = {Stringological sequence prediction I: efficient algorithms for predicting highly repetitive sequences},
  author = {Vanessa Kosoy},
  year   = {2026},
  eprint = {2603.26852},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2603.26852v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2603.26852.svg)](https://codeofpaper.com/paper/2603.26852)

Discussion