The reflection complexity of sequences over finite alphabets (Q6905974)

The authors introduce the \textit{reflection complexity} \(r_x(n)\) of an infinite word \(x\) as the number of factors of length \(n\) occurring in \(x\) up to reversing the order of symbols: words \(a_1a_2\cdots a_n\) and \(a_n\cdots a_2 a_1\) are considered as equal. Clearly, \(\frac{1}{2} p_x(n)\leq r_x(n) \leq p_x(n)\), where \(p_x(n)\) is the usual factor complexity of \(x\), that is, the number of its factors of length \(n\). More precisely, equalities involving the number of palindromes, unreflected and reflected factors of \(x\) are also easy to verify. Moreover, if \(x\) is uniformly recurrent, then either all factors are reflected, or there are no reflected factors starting from some length, and it is possible to rapidly classify the reflection complexity as either a half of \((p_x(n)+\text{the number of palindromes of length } n\)), or just eventually \(p_x(n)\).\N\NThe paper contains many nice results on words with different relations among the factor complexity, the reflection complexity and the number of palindromes, and several structural facts, including the proof that if \(x\) is \(k\)-automatic, then \(r_x\) is computably \(k\)-regular.