  Finite-state complexity is a variant of algorithmic information theory
obtained by replacing Turing machines with finite transducers. We consider the
state-size of transducers needed for minimal descriptions of arbitrary strings
and, as our main result, we show that the state-size hierarchy with respect to
a standard encoding is infinite. We consider also hierarchies yielded by more
general computable encodings.
