On compression with two-way head machines

Abstract

Ziv and Lempel QZL78] investigated the encoding power of the class of finite state machines with respect to given individual sequences. In [I.Z86] they extended the model by adding a moving reading head, yielding a finite state model for image encoders. The power of these encoders with respect to given individual images was examined in [LZ86] and [SLZ90]. Motivated by the study of various kinds of machines as recognizers of formal languages, (cf. [HU79]), 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 achievable for a given sequence, to be decoded by a finite state decoder, is the same as the bcsl ratio attainable for that sequence when encoded by a finite state information lossless encoder. Second of prove that we can not gain in compression by allowing n finite state encoder 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.