The reflection complexity of sequences over finite alphabets

In combinatorics on words, the well-studied factor complexity function ${\rho }_{\text{infw}x}$ of a sequence $\text{infw}x$ over a finite alphabet counts, for every nonnegative integer $n$, the number of distinct length-$n$ factors of $\text{infw}x$. In this paper, we introduce the \emph{reflection complexity} function $r_{\text{infw}x}$ to enumerate the factors occurring in a sequence $\text{infw}x$, up to reversing the order of symbols in a word. We prove a number of results about the growth properties of $r_{\text{infw}x}$ and its relationship with other complexity functions. We also prove a Morse–Hedlund-type result characterizing eventually periodic sequences in terms of their reflection complexity, and we deduce a characterization of Sturmian sequences. We investigate the reflection complexity of quasi-Sturmian, episturmian, $(s+1)$-dimensional billiard, complementation-symmetric Rote, and rich sequences. Furthermore, we prove that if $\text{infw}x$ is $k$-automatic, then $r_{\text{infw}x}$ is computably $k$-regular, and we use the software $\mathtt{\text{Walnut}}$ to evaluate the reflection complexity of some automatic sequences, such as the Thue–Morse sequence. We note that there are still many unanswered questions about this reflection measure.