The reflection complexity of sequences over finite alphabets

In combinatorics on words, the well-studied factor complexity function ρₓ of a sequence x over a finite alphabet counts, for any nonnegative integer n, the number of distinct length-n factors of x. In this paper, we introduce the reflection complexity function rₓ to enumerate the factors occurring in a sequence x, up to reversing the order of symbols in a word. We introduce and prove results on rₓ regarding its growth properties and relationship with other complexity functions. We prove that if x is k-automatic, then rₓ is computably k-regular, and we use the software { 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.