Complexity of generalized Rudin-Shapiro sequences (Q1320516)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Complexity of generalized Rudin-Shapiro sequences |
scientific article |
Statements
Complexity of generalized Rudin-Shapiro sequences (English)
0 references
8 August 1995
0 references
This is a useful paper for meeting and understanding the principles governing our understanding of the class of sequences on a finite alphabet termed automatic sequences. Let \((u_ n)\) be an infinite sequence. Then any word \(u_ n u_{n1} \cdots u_{nk-1}\) is called a factor of length \(k\). If \(P_ u (k)\) denotes the number of different factors of length \(k\) appearing in the sequence \(u\) then the map \(P_ u\) is called the complexity of the sequence. For example, the sequence is ultimately periodic if \(P_ u (n)\leq n\) for some \(n\). The present paper studies the generalized Rudin- Shapiro sequence \((u_{d,n} )= (u_ n)\) counting the number mod 2 of occurrences of a factor \(1*\cdots *1\), in the binary representation of \(n\), where \(*\cdots *\) is an arbitrary word of length \(d-1\). The authors show that asymptotically \(P_ u (n)\) is linear.
0 references
finite alphabet
0 references
automatic sequences
0 references
complexity
0 references
generalized Rudin- Shapiro sequence
0 references