String compression in FA–presentable structures

We 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.

Authors

• Dmitry Berdinsky
• Sanjay Jain
• Bakhadyr Khoussainov
• Frank Stephan

Keywords

• FA–presentation
• FA–presentable structure
• Successor function
• Presburger arithmetic
• Compressibility rate