On the \(N\)th linear complexity of automatic sequences (Q1747239): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2962853512 / rank | |||
Normal rank |
Revision as of 23:53, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the \(N\)th linear complexity of automatic sequences |
scientific article |
Statements
On the \(N\)th linear complexity of automatic sequences (English)
0 references
4 May 2018
0 references
For a prime power \(q\), a \(q\)-automatic sequence \((u_n)\) over the alphabet \(\mathbb{F}_q\) is the output of a finite automaton whose input is the \(q\)-ary digital expansion of \(n\). By a result of Christol, \((u_n)\) is \(q\)-automatic over \(\mathbb{F}_q\) if and only if the generating function \(G(t)=\sum_{n=0}^\infty u_nt^n\) is algebraic over \(\mathbb{F}_q[t]\). The \(N\)-th linear complexity \(L(u_n, N)\) of \((u_n)\) over \(\mathbb{F}_q\) is the length \(L\) of a shortest linear recurrence over \(\mathbb{F}_q\) satisfied by the first \(N\) elements of \((u_n)\). The linear complexity of \((u_n)\) is \(L(u_n)=\sup_{N\geq 1} L(u_n,N)\). Ultimately periodic sequences are automatic and correspond to rational generating functions. They have finite linear complexity. The authors show, using properties of the the algebraic generating function, that if \((u_n)\) is automatic but not ultimately periodic then the \(N\)-th linear complexity is of order \(N\), the largest possible order of magnitude. They derive explicit values for the linear complexity of a number of examples of automatic sequences and find a connection between the linear complexity profile of a binary sequence and the continued fraction expansion of its generating function. Since automatic sequences are highly predictable, the results confirm that a large linear complexity does not guarantee unpredictability.
0 references
automatic sequence
0 references
Shapiro sequence
0 references
Rudin--Shapiro sequence
0 references
pattern sequence
0 references
sum-of-digits sequence
0 references
Baum--Sweet sequence
0 references
paper-folding sequence
0 references
linear complexity, expansion complexity
0 references
lattice profile
0 references
continued fraction
0 references