Finite-state compressibility of an individual sequence

An information-lossless $s$-state encoder consists of a finite state set $S$, an initial state, an update map $g:S\times \mathcal{A}\to S$, and an output map $f:S\times \mathcal{A}\to \{0,1{\}}^{\ast }$. It is information-lossless when for each initial state the map from finite input words to (concatenated output, final state) is injective.

The encoder class is nonempty: let $t=\max (1,\lceil {\log }_2\mathrm{\mid }\mathcal{A}\mathrm{\mid }\rceil )$ and choose distinct $t$-bit labels for the finitely many source symbols. Use one state with the identity update and emit each symbol's label. The output splits into fixed-width labels and therefore uniquely determines every finite input word. Let $L_E(x_0^{n-1})$ be an encoder's concatenated output length and set ${\rho }_s(x)={\inf }_E{\mathrm{lim\hspace{0.17em}sup}}_n{L}_E(x_0^{n-1})\mathrm{/}n$, over information-lossless encoders with at most $s$ states. Define finite-state compressibility ${\rho }_{\mathrm{F}\mathrm{S}}(x)={\inf }_{s\ge 1}{\rho }_s(x)$. The infima are nonincreasing in $s$ and bounded below by zero, so the limit in the equivalent notation ${\lim }_{s\to \mathrm{\infty }}{\rho }_s(x)$ exists.