Bibliographic Details
| Title: |
The reflection complexity of sequences over finite alphabets |
| Authors: |
Allouche, Jean-Paul, Campbell, John M., Li, Shuo, Shallit, Jeffrey, Stipulanti, Manon |
| Publication Year: |
2024 |
| Collection: |
Computer Science
Mathematics |
| Subject Terms: |
Mathematics - Combinatorics, Computer Science - Discrete Mathematics, Computer Science - Formal Languages and Automata Theory, 05A05, 11B85, 68R15 |
| More Details: |
In combinatorics on words, the well-studied factor complexity function $\rho_{\bf x}$ of a sequence ${\bf x}$ over a finite alphabet counts, for any nonnegative integer $n$, the number of distinct length-$n$ factors of $\mathbf{x}$. In this paper, we introduce the reflection complexity function $r_{\bf x}$ to enumerate the factors occurring in a sequence ${\bf x}$, up to reversing the order of symbols in a word. We introduce and prove general results on $r_{\bf x}$ regarding its growth properties and relationship with other complexity functions. We prove a Morse-Hedlund-type result characterizing eventually periodic sequences in terms of their reflection complexity, and we deduce a characterization of Sturmian sequences. Furthermore, we investigate the reflection complexity of quasi-Sturmian, episturmian, $(s+1)$-dimensional billiard, and complementation-symmetric Rote, and rich sequences. Furthermore, we prove that if ${\bf x}$ is $k$-automatic, then $r_{\bf x}$ is computably $k$-regular, and we use the software $\mathtt{Walnut}$ to evaluate the reflection complexity of automatic sequences, such as the Thue-Morse sequence. We note that there are still many unanswered questions about this measure. |
| Document Type: |
Working Paper |
| Access URL: |
http://arxiv.org/abs/2406.09302 |
| Accession Number: |
edsarx.2406.09302 |
| Database: |
arXiv |
