On Brlek-Reutenauer conjecture (Q719304)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On Brlek-Reutenauer conjecture |
scientific article |
Statements
On Brlek-Reutenauer conjecture (English)
0 references
10 October 2011
0 references
The defect of a finite word \(w\), denoted as \(D(w)\), is the difference between \(|w|+1\) (the maximum possible) and the actual number of distinct palindromic factors of \(w\). The defect \(D(\mathbf{u})\) of a one-way infinite word \(\mathbf{u}\) is the supremum of the defects of all its factors. Let \(\mathcal{C}_{\mathbf{u}}(n)\) and \(\mathcal{P}_{\mathbf{u} }(n)\) denote the number of all factors and the number of palindromic factors of \(\mathbf{u}\) of length \(n\), respectively. If \(\mathbf{u}\) is periodic, \(\mathcal{P}_{\mathbf{u}}(n)+\mathcal{P}_{\mathbf{u}}(n+1)=2\). An important characteristics of \(\mathbf{u}\) seems to be the quantity \(T_{\mathbf{u}}(n)=\mathcal{C}_{\mathbf{u}}(n+1)-\mathcal{C}_{\mathbf{u}}(n)+2-\mathcal{P}_{\mathbf{u}}(n+1)-\mathcal{P} _{\mathbf{u}}(n)\). If the set of factors \(\mathcal{L}(\mathbf{u})\) of \(\mathbf{u}\) is closed under reversal, then \(T_{\mathbf{u}}(n)\geq0\) for all \(n\geq0\). Brlek and Reutenauer conjectured that if \(\mathcal{L}(\mathbf{u})\) is closed under reversal, then \(2D(\mathbf{u})=\sum_{n=0}^\infty T_{\mathbf{u}}(n)\). They proved the conjecture in the case when \(\mathbf{u}\) is periodic. The present paper extends the validity of the conjecture to uniformly recurrent words, i.e., infinite words \(\mathbf{u}\) where each factor occurs in \(\mathbf{u}\) infinitely many times but has only finitely many return words. A return word of \(w\) is a word \(q\) such that \(qw\) is a factor of \(\mathbf{u}\), \(w\) is a prefix of \(qw\), and \(w\) occurs in \(qw\) exactly twice.
0 references
palindromic factor
0 references
palindromic complexity
0 references
defect
0 references
infinite word
0 references
recurrent word
0 references