On encoding and decoding with two-way head machines

Ziv and Lempel investigated the encoding power of finite state machines with respect to given individual sequences. Motivated by the study of various kinds of machines as recognizers of formal languages (cf. Hopcroft and Ullman, 1979, “Introduction to Automata Theory, Languages, and Computation,” Addison-Wesley, Reading, MA), we compare the encoding and decoding power of finite state sequential machines and the following extensions thereof. First, we show that, with a forward moving head, the best compression ratio achievable for a given sequence, to be decoded by a finite state decoder, is the same as the best ratio attainable for that sequence when encoded by a finite state information lossless encoder. Second, we prove that we can not gain in compression by allowing a finite state encoder to move its head back and forth on an input sequence, even if the decoder has unrestricted power. However, better compression can be achieved for specific infinite sequences using an unrestricted encoder and a two-way finite state decoder. © 1995 Academic Press, Inc.