On the complexity of a family of \(k\)-context-free sequences (Q764304)

The complexity function \(p_{\mathbf{a}}\left( n\right) \) of an infinite sequence \(\mathbf{a}=a_{0}a_{1}a_{2}\ldots\) over a finite alphabet is defined as the number of different factors of length \(n\) occurring in \(\mathbf{a}\). A sequence \(\mathbf{a}\) is \(k\)-context-free (\(k\geq2\)) if the language of \(k\)-ary expansions of position numbers of all those positions in \(\mathbf{a}\), where a fixed symbol \(a\) occurs, is context-free for each symbol \(a\). In the paper, \(k\)-pushdown automatic sequences are considered, forming a subclass of the class of \(k\)-context-free sequences. The symbol \(a_{n}\) of a \(k\)-pushdown automatic sequence \(\mathbf{a}\) is the result of computation of a fixed deterministic pushdown automaton on the \(k\)-ary expansion of the position number \(n\). The paper shows that the complexity function of a \(k\)-pushdown automatic sequence grows polynomially. In particular, if the size of the stack alphabet is \(m\), then \(p_{\mathbf{a}}\left( n\right) =\mathcal{O}\left( n^{1+2\log_{k}m}\right) \) for \(m\geq2\), while \(p_{\mathbf{a}}\left( n\right) =\mathcal{O}\left( n\log^{2}n\right) \) if \(m=1\), and \(p_{\mathbf{a} }\left( n\right) =\mathcal{O}\left( n\right) \) if \(m=0\).