[Linkpost] ”[Paper] Stringological sequence prediction II” by Vanessa Kosoy

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.

This paper continues my sequence on the new approach to compositional learning, started here. Curiously, the ARC complexity measure I define here seems related[1] to my control-theoretic complexity measure for polytope MDPs, even though the motivation here comes from a completely different automata-theoretic angle[2].

The original text contained 2 footnotes which were omitted from this narration.

---

First published:
July 22nd, 2026

Source:
https://www.lesswrong.com/posts/TTei7oq9ndjJFgnsT/paper-stringological-sequence-prediction-ii

Linkpost URL:
https://arxiv.org/abs/2607.17369

---

Narrated by TYPE III AUDIO.