About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Information and Computation
Paper
On encoding and decoding with two-way head machines
Abstract
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.