Automatic complexity of shift register sequences. (English) Zbl 1422.94024
Summary: Let \(x\) be an \(m\)-sequence, a maximal length sequence produced by a linear feedback shift register. We show that \(x\) has maximal subword complexity function in the sense of Allouche and Shallit. We show that this implies that the nondeterministic automatic complexity \(A_N(x)\) is close to maximal: \(n/2 - A_N(x) = O(\log^2 n)\), where \(n\) is the length of \(x\). In contrast, Hyde has shown \(A_N(y) \leq n/2 + 1\) for all sequences \(y\) of length \(n\).
MSC:
| 94A55 | Shift register sequences and sequences over finite alphabets in information and communication theory |
References:
| [1] | Gammel, Berndt M.; Göttfert, Rainer, Linear filtering of nonlinear shift-register sequences, (Coding and Cryptography, Lecture Notes in Comput. Sci., vol. 3969, (2006), Springer Berlin), 354-370 · Zbl 1151.94464 |
| [2] | Golomb, Solomon W., (Welch, Lloyd R.; Goldstein, Richard M.; Hales, Alfred W., Shift Register Sequences, (1967), Holden-Day, Inc. San Francisco, Calif.-Cambridge-Amsterdam) · Zbl 0267.94022 |
| [3] | Hyde, Kayleigh; Kjos-Hanssen, Bjørn, Nondeterministic automatic complexity of overlap-free and almost square-free words, Electron. J. Combin, 22, 3, 18, (2015), Paper 3.22 · Zbl 1334.68173 |
| [4] | Lidl, Rudolf; Niederreiter, Harald, Introduction to finite fields and their applications, (1986), Cambridge University Press Cambridge · Zbl 0629.12016 |
| [5] | Massey, James L., Shift-register synthesis and \(B C H\) decoding, IEEE Trans. Inform. Theory, IT-15, 122-127, (1969) · Zbl 0167.18101 |
| [6] | New Wave Instruments. Linear feedback shift registers: Implementation, m-sequence properties, feedback tables. 2010. http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr.htm#M-Sequence |
| [7] | Shallit, Jeffrey; Wang, Ming-Wei, Automatic complexity of strings, J. Autom. Lang. Comb., 6, 4, 537-554, (2001), 2nd Workshop on Descriptional Complexity of Automata, Grammars and Related Structures (London, ON, 2000) · Zbl 1004.68077 |
| [8] | Stephen Wolfram, Solomon Golomb (1932-2015). http://blog.stephenwolfram.com/2016/05/solomon-golomb-19322016/; Stephen Wolfram, Solomon Golomb (1932-2015). http://blog.stephenwolfram.com/2016/05/solomon-golomb-19322016/ |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
