Reflection on the Reflection Complexity

Abstract The factor complexity $$\mathcal {C}_{{\textbf {u}}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>C</mml:mi> <mml:mi>u</mml:mi> </mml:msub> </mml:math> of a sequence $$\textbf{u}= \varvec{u}_{0}\varvec{u}_{1}\varvec{u}_{2} \cdots $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>u</mml:mi> <mml:mo>=</mml:mo> <mml:msub> <mml:mrow> <mml:mi>u</mml:mi> </mml:mrow> <mml:mn>0</mml:mn> </mml:msub> <mml:msub> <mml:mrow> <mml:mi>u</mml:mi> </mml:mrow> <mml:mn>1</mml:mn> </mml:msub> <mml:msub> <mml:mrow> <mml:mi>u</mml:mi> </mml:mrow> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>⋯</mml:mo> </mml:mrow> </mml:math> over a finite alphabet counts the number of factors of length n occurring in $$\textbf{u}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>u</mml:mi> </mml:math> , i.e., $$\mathcal {C}_\textbf{u}{(n)} = \#{\mathcal {L}}_n(\textbf{u})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>C</mml:mi> <mml:mi>u</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mo>#</mml:mo> <mml:msub> <mml:mi>L</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>u</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , where $${\mathcal {L}}_n\varvec{(}\textbf{u}\varvec{)}= {\{}\varvec{u}_{{i}}\varvec{u}_{{i+1}}\cdots \varvec{u}_{{i+n-1}}{: i} \in \mathbb {N}{\}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>L</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> </mml:mrow> <mml:mi>u</mml:mi> <mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mo>{</mml:mo> <mml:msub> <mml:mrow> <mml:mi>u</mml:mi> </mml:mrow> <mml:mi>i</mml:mi> </mml:msub> <mml:msub> <mml:mrow> <mml:mi>u</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>i</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> <mml:mo>⋯</mml:mo> <mml:msub> <mml:mrow> <mml:mi>u</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>i</mml:mi> <mml:mo>+</mml:mo> <mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> <mml:mrow> <mml:mo>:</mml:mo> <mml:mi>i</mml:mi> </mml:mrow> <mml:mo>∈</mml:mo> <mml:mi>N</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> . Two factors of $${\mathcal {L}}_{{n}}\varvec{(}\textbf{u}\varvec{)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>L</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> </mml:mrow> <mml:mi>u</mml:mi> <mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> are said to be equivalent if they are equal or one factor is the reversal of the other one. Recently, Allouche et al. introduced the reflection complexity $${r}_\textbf{u}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>r</mml:mi> <mml:mi>u</mml:mi> </mml:msub> </mml:math> which counts the number of non-equivalent factors of $${\mathcal {L}}_{{n}}\varvec{(}\textbf{u}\varvec{)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>L</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> </mml:mrow> <mml:mi>u</mml:mi> <mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> . They formulated the following conjecture: a sequence $$\textbf{u}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>u</mml:mi> </mml:math> <