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 ${\bf
x}$. In this paper, we introduce the \emph{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 results on
$r_{\bf x}$ regarding its growth properties and relationship with other
complexity functions. We prove that if ${\bf x}$ is $k$-automatic, then $r_{\bf
x}$ is computably $k$-regular, and we use the software {\tt Walnut} to evaluate
the reflection complexity of automatic sequences, such as the Thue--Morse
sequence. 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 episturmian, $(s+1)$-dimensional billiard, and Rote
sequences. There are still many unanswered questions about this measure.