Complexity of generalized Rudin-Shapiro sequences
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.
- Automata calculating the complexity of automatic sequences
- Enumeration of factors in the Thue-Morse word
- Generalized Rudin-Shapiro sequences
- Représentation géométrique de suites de complexité 2n+1
- Sequences with minimal block growth
- Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups
- Some Theorems on Fourier Coefficients
- Suites algébriques, automates et substitutions
- Uniform tag sequences
- On the Shyr-Yu theorem
- Factors of generalized Rudin-Shapiro sequences
- Automata calculating the complexity of automatic sequences
- Euclidean strings
- On the \(N\)th maximum order complexity and the expansion complexity of a Rudin-Shapiro-like sequence
- Complexity of Hartman sequences
- On the abelian complexity of the Rudin-Shapiro sequence
- Spectral continuity for aperiodic quantum systems: applications of a folklore theorem
- scientific article; zbMATH DE number 4071035 (Why is no real title available?)
- Shiner–Davison–Landsberg complexity revisited
- Discrete correlations of order 2 of generalized Golay-Shapiro sequences: a combinatorial approach
- On the finite factorial numbers
- If a machine did it, it is probably transcendental (even p-adically)
This page was built for publication: Complexity of generalized Rudin-Shapiro sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1320516)
