On compression with two-way head machines
Dafna Sheinwald, Abraham Lempel, J. Ziv · 2002
Motivated by the study of various kinds of machines as recognizers of formal languages, the authors compare the encoding and decoding power of finite state sequential machines and extensions thereof. They show that, with a forward moving head, the best compression 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. They cannot 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.>