用字符串算法高效预测重复性强的序列，理论保证可预测性。
Stringological sequence prediction I: efficient algorithms for predicting highly repetitive sequences
- 基于字符串复杂度设计高效预测算法
- 错误率受最小直线程序/自动机状态数约束
- 适合研究自动序列、形态序列等低复杂度序列
我们提出基于字符串学思想的新型序列预测算法，具有时间与空间效率，并满足与序列字符串学复杂度度量相关的错误界。本文（系列第一篇）聚焦两种度量：(i) 生成该序列的最小直线程序规模；(ii) 当以基k表示位置作为输入时，能计算任意符号的最小自动机的状态数。这些度量具有重要意义，因为组合词学中多个丰富序列类（如自动序列、形态序列、Sturmian词）均具有低复杂度，因此在此意义上具有高可预测性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。