Maximum-order Complexity and Correlation Measures

2017/03/27 by Işık, Leyla, Winterhof, Arne
#FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.1703.09151

Abstract

We estimate the maximum-order complexity of a binary sequence in terms of its correlation measures. Roughly speaking, we show that any sequence with small correlation measure up to a sufficiently large order k cannot have very small maximum-order complexity.

Related

• Correlation, Linear Complexity, Maximum order Complexity on Families of binary Sequences
• The correlation measures of finite sequences: limiting distributions and\n minimum values
• Family complexity and cross-correlation measure for families of binary sequences
• Families of sequences with good family complexity and cross-correlation measure
• On the maximum order complexity of the Thue-Morse and Rudin-Shapiro sequence