The reflection complexity of sequences over finite alphabets
<|reference_start|>The reflection complexity of sequences over finite alphabets: 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.<|reference_end|>
@article{allouche2024the,
    title={The reflection complexity of sequences over finite alphabets},
    author={Jean-Paul Allouche, John M. Campbell, Shuo Li, Jeffrey Shallit, Manon
  Stipulanti},
    journal={arXiv preprint arXiv:2406.09302},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.09302},
    primaryClass={math.CO cs.DM cs.FL}
}