Title: Multihead Finite-State Compression Show Chinese title

Title: 多头有限状态压缩

Abstract: 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. Show Chinese abstract

Abstract: 本文开发了多头有限状态压缩，这是有限状态压缩的一种推广，与Huang、Li、Lutz和Lutz（2025）提出的多头有限状态维度相辅相成。 在这个模型中，一个无限符号序列通过一个压缩器进行压缩，该压缩器根据有限状态规则生成输出，这些规则基于固定数量的有限状态读头在序列中向前无记忆地读取符号。 本研究的主要定理表明，对于每个序列和每个正整数$h$，由$h$-头有限状态无损压缩器实现的压缩比的下确界等于该序列的$h$-头有限状态预维数。 作为直接推论，所有$h$的这些比值的下确界是该序列的多头有限状态维数。