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.