cs.FLJul 19, 2026

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

Authors: Vanessa Kosoy

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

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.

Explore similar work

CardsList
  1. Sequence prediction under a lying oracle

    Aug 14, 2026Puspabeethi Samanta, Nikhil Karamchandani, Jayakrishnan NairSharp Joint-Kl Oracle TheorySequential Decision Making