On the complexity of infinite sequences. (Sur la complexité des suites infinies.) (French) Zbl 0803.68094

Summary: The complexity of an infinite sequence taking its values in a finite set counts the number of factors (subwords) of given length of this sequence. We give a quick view of complexity results for different sequences or classes of sequences.


68R15 Combinatorics on words
11B85 Automata sequences
Full Text: EuDML