The reflection complexity of sequences over finite alphabets

Abstract

In combinatorics on words, the well-studied factor complexity function $ρ_{\infw{x}}$ of a sequence $\infw{x}$ over a finite alphabet counts, for every nonnegative integer $n$, the number of distinct length-$n$ factors of $\infw{x}$. In this paper, we introduce the \emph{reflection complexity} function $r_{\infw{x}}$ to enumerate the factors occurring in a sequence $\infw{x}$, up to reversing the order of symbols in a word. We prove a number of results about the growth properties of $r_{\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 $\infw{x}$ is $k$-automatic, then $r_{\infw{x}}$ is computably $k$-regular, and we use the software \texttt{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.

41 pages