Berdinsky D.Jain S.Khoussainov B.Stephan F.Mahidol University2023-05-192023-05-192023-02-20Theoretical Computer Science Vol.947 (2023)03043975https://repository.li.mahidol.ac.th/handle/20.500.14594/81774We construct a FA–presentation ψ:L→N of the structure (N;S) for which a numerical characteristic r(n) defined as the maximum number ψ(w) for all strings w∈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 (N;+) we show that it is bounded from above by a linear function.Computer ScienceArticleSCOPUS10.1016/j.tcs.2023.1137052-s2.0-85146847916