A quantity called the {\em finite-state} complexity is assigned to every infinite sequence of
elements drawn from a finite sot. This quantity characterizes the largest compression ratio
that can be achieved in accurate transmission of the sequence by any finite-state encoder
(and decoder). Coding theorems and converses are derived for an individual sequence
without any probabilistic characterization, and universal data compression algorithms are
introduced that are asymptotically optimal for all sequences over a given alphabet. The finite …