  We construct a FA-presentation $\psi: L \rightarrow \mathbb{N}$ of the
structure $(\mathbb{N};\mathrm{S})$ for which a numerical characteristic $r(n)$
defined as the maximum number $\psi(w)$ for all strings $w \in L$ of length
less than or equal to $n$ grows faster than any tower of exponents of a fixed
height. This result leads us to a more general notion of a compressibility rate
defined for FA-presentations of any FA-presentable structure. We show the
existence of FA-presentations for the configuration space of a Turing machine
and Cayley graphs of some groups for which it grows faster than any tower of
exponents of a fixed height. For FA-presentations of the Presburger arithmetic
$(\mathbb{N};+)$ we show that it is bounded from above by a linear function.
