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

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.

Formal Languages and Automata Theory (cs.FL); Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG)

I.2.6; F.2.2; G.2.1

arXiv:2603.26852 [cs.FL]

(or arXiv:2603.26852v2 [cs.FL] for this version)

https://doi.org/10.48550/arXiv.2603.26852 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.