String compression in FA–presentable structures
2
Issued Date
2023-02-20
Resource Type
ISSN
03043975
Scopus ID
2-s2.0-85146847916
Journal Title
Theoretical Computer Science
Volume
947
Rights Holder(s)
SCOPUS
Bibliographic Citation
Theoretical Computer Science Vol.947 (2023)
Suggested Citation
Berdinsky D., Jain S., Khoussainov B., Stephan F. String compression in FA–presentable structures. Theoretical Computer Science Vol.947 (2023). doi:10.1016/j.tcs.2023.113705 Retrieved from: https://repository.li.mahidol.ac.th/handle/123456789/81774
Title
String compression in FA–presentable structures
Author(s)
Other Contributor(s)
Abstract
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.