Journal of Numerical Analysis and Approximation Theory (Aug 2004)
Properties of the complexity function for finite words
Abstract
The subword complexity function \(p_{w}\) of a finite word \(w\) over a finite alphabet \(A\) with \(\operatorname*{card}A=q\geq1\) is defined by \(p_{w}(n)=\operatorname*{card}(F(w)\cap A^{n})\) for \(n\in\mathbb{N},\) where \(F(w)\) represents the set of all the subwords or factors of \(w\). The shape of the complexity function, especially its piecewise monotonicity, is studied in detail.The function \(h\) defined as \(h(n)=\min\left\{ q^{n},N-n+1\right\} \) for \(n\in\{0,1,\) \(...,N\}\) has values greater than or equal to those of the complexity function \(p_{w}\) for any \(w\in A^{N}\), i.e., \(p_{w}(n)\leq h(n)\) for all \(n\in\{0,1,...,N\}\). As a first result regarding \(h\), it is proved that for each \(N\in\mathbb{N}\) there exist words of length \(N\) for which the maximum of their complexity function is equal to the maximum of the function \(h\); a way to construct such words is described. This result gives rise to a further question: for a given \(N\), is there a word of length \(N\) whose complexity function coincides with \(h\) for each \(n\in\{0,1,...,N\}?\) The problem is answered in affirmative, with different constructive proofs for binary alphabets (\(q=2\)) and for those with \(q>2.\) This means that for each \(N\in\mathbb{N},\) there exist words \(w\) of length \(N\) whose complexity function is equal to the function \(h\). Such words are constructed using the de Bruijn graphs.
