2016/03/08 by Tim Smith, Smith, Tim
Computer Science · #Algorithms and Data Compression #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Machine Learning (cs.LG) #Machine Learning and Algorithms #cs.FL #cs.LG #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1603.02597
arxiv created 2016/03/08 · openalex publication_date 2016/03/08 · arxiv updated 2016/03/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the classic problem of sequence prediction, a predictor receives a sequence of values from an emitter and tries to guess the next value before it appears. The predictor masters the emitter if there is a point after which all of the predictor's guesses are correct. In this paper we consider the case in which the predictor is an automaton and the emitted values are drawn from a finite set; i.e., the emitted sequence is an infinite word. We examine the predictive capabilities of finite automata, pushdown automata, stack automata (a generalization of pushdown automata), and multihead finite automata. We relate our predicting automata to purely periodic words, ultimately periodic words, and multilinear words, describing novel prediction algorithms for mastering these sequences.