On the number of Arnoux-Rauzy words (Q2773325)

The authors study the so-called Arnoux-Rauzy sequences: these are the recurrent sequences over a \(k\)-letter alphabet that have block-complexity \((k-1)n+1\) and exactly one right- and one left-special factor of each length. These sequences were introduced for \(k=3\) by \textit{P. Arnoux} and \textit{G. Rauzy} [Bull. Soc. Math. Fr. 119, 199-215 (1991; Zbl 0789.28011)] and for \(k\geq 4\) by \textit{R. N. Risley} and \textit{L. Q. Zamboni} [Acta Arith. 95, 167-184 (2000; Zbl 0953.11007)]. They generalize the Sturmian sequences that correspond to \(k=2\). NEWLINENEWLINENEWLINEThe authors obtain a formula for the number of all subwords (factors) of all Arnoux-Rauzy sequences for a fixed \(k\). This formula involves a generalized Euler function. It boils down to the formula for all factors of Sturmian sequences for \(k=2\), originally conjecture by \textit{S. Dulucq} and \textit{D. Gouyou-Beauchamps} [Theor. Comput. Sci. 71, 381-400 (1990; Zbl 0694.68048)] and first proved by \textit{F. Mignosi} [Theor. Comput. Sci. 82, 71-84 (1991; Zbl 0728.68093)]. NEWLINENEWLINENEWLINENote that Reference [9] has appeared [\textit{N. Chekhova, P. Hubert} and \textit{A. Messaoudi}, J. Théor. Nombres Bordx. 13, 371-394 (2001; Zbl 1038.37010)].