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

Abstract: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.

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:2607.17369 [cs.FL]

(or arXiv:2607.17369v1 [cs.FL] for this version)

https://doi.org/10.48550/arXiv.2607.17369 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

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.