2025/10/20 by Neil Lutz, Lutz, Neil
Computer Science · #Computability, Logic, AI Algorithms #Algorithms and Data Compression #Cellular Automata and Applications
paper · pdf · doi:10.48550/arxiv.2510.17544
This paper develops multihead finite-state compression, a generalization of finite-state compression, complementary to the multihead finite-state dimensions of Huang, Li, Lutz, and Lutz (2025). In this model, an infinite sequence of symbols is compressed by a compressor that produces outputs according to finite-state rules, based on the symbols read by a constant number of finite-state read heads moving forward obliviously through the sequence. The main theorem of this work establishes that for every sequence and every positive integer h, the infimum of the compression ratios achieved by h-head finite-state information-lossless compressors equals the h-head finite-state predimension of the sequence. As an immediate corollary, the infimum of these ratios over all h is the multihead finite-state dimension of the sequence.