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...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://repository.li.mahidol.ac.th/handle/123456789/80195 https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85146847916&origin=inward |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Mahidol University |
| id |
th-mahidol.80195 |
|---|---|
| record_format |
dspace |
| spelling |
th-mahidol.801952023-02-10T07:01:44Z String compression in FA–presentable structures Berdinsky D. Mahidol University Mathematics 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. 2023-02-10T00:01:44Z 2023-02-10T00:01:44Z 2023-02-20 Article Theoretical Computer Science Vol.947 (2023) 10.1016/j.tcs.2023.113705 03043975 2-s2.0-85146847916 https://repository.li.mahidol.ac.th/handle/123456789/80195 https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85146847916&origin=inward SCOPUS |
| institution |
Mahidol University |
| building |
Mahidol University Library |
| continent |
Asia |
| country |
Thailand Thailand |
| content_provider |
Mahidol University Library |
| collection |
Mahidol University Institutional Repository |
| topic |
Mathematics |
| spellingShingle |
Mathematics Berdinsky D. String compression in FA–presentable structures |
| description |
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. |
| author2 |
Mahidol University |
| author_facet |
Mahidol University Berdinsky D. |
| format |
Article |
| author |
Berdinsky D. |
| author_sort |
Berdinsky D. |
| title |
String compression in FA–presentable structures |
| title_short |
String compression in FA–presentable structures |
| title_full |
String compression in FA–presentable structures |
| title_fullStr |
String compression in FA–presentable structures |
| title_full_unstemmed |
String compression in FA–presentable structures |
| title_sort |
string compression in fa–presentable structures |
| publishDate |
2023 |
| url |
https://repository.li.mahidol.ac.th/handle/123456789/80195 https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85146847916&origin=inward |
| _version_ |
1763490400130039808 |