Applications of Combinatorics on Words with Symbolic Dynamics
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916793879101440 |
|---|---|
| author | Abdullah, Duaa Hamoud, Jasmem |
| author_facet | Abdullah, Duaa Hamoud, Jasmem |
| contents | In this paper, we explore applications of combinatorics on words across various domains, including data compression, error detection, cryptographic protocols, and pseudorandom number generation. The examination of the theoretical foundations enabling these applications, emphasizing important concepts of mathematical relationships and algorithms. In data compression, we discuss the Lempel-Ziv family of algorithms and Lyndon factorization, with the number of Lyndon words of length \( n \) over an alphabet of size \( k \) given by \[ L(n,k) = \frac{1}{n} \sum_{d|n} μ(d) k^{n/d}. \] We address cryptographic protocols and pseudorandom number generation, highlighting the role of pseudorandomness theory and complexity measures. Also, by explore de Bruijn sequences, topological entropy, and synchronizing words in their practical contexts, demonstrating their contributions to optimizing information storage, ensuring data integrity, and enhancing cybersecurity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_12150 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Applications of Combinatorics on Words with Symbolic Dynamics Abdullah, Duaa Hamoud, Jasmem Combinatorics 68R15, 11B39, 05A05, 68R15, 37B10 In this paper, we explore applications of combinatorics on words across various domains, including data compression, error detection, cryptographic protocols, and pseudorandom number generation. The examination of the theoretical foundations enabling these applications, emphasizing important concepts of mathematical relationships and algorithms. In data compression, we discuss the Lempel-Ziv family of algorithms and Lyndon factorization, with the number of Lyndon words of length \( n \) over an alphabet of size \( k \) given by \[ L(n,k) = \frac{1}{n} \sum_{d|n} μ(d) k^{n/d}. \] We address cryptographic protocols and pseudorandom number generation, highlighting the role of pseudorandomness theory and complexity measures. Also, by explore de Bruijn sequences, topological entropy, and synchronizing words in their practical contexts, demonstrating their contributions to optimizing information storage, ensuring data integrity, and enhancing cybersecurity. |
| title | Applications of Combinatorics on Words with Symbolic Dynamics |
| topic | Combinatorics 68R15, 11B39, 05A05, 68R15, 37B10 |
| url | https://arxiv.org/abs/2506.12150 |