Entropy analysis of substitutive sequences revisited

A given finite sequence of letters over a finite alphabet can always be alg orithmically generated, in particular by a Turing machine. This fact is at the heart of complexity theory in the sense of Kolmogorov and Chaitin. A re levant question in this context is whether, given a statistically 'sufficie ntly long' sequence, there exists a deterministic finite automaton that gen erates it. In this paper we propose a simple criterion, based on measuring block entropies by lumping, which is satisfied by all automatic sequences. On the basis of this, one can determine that a given sequence is not automa tic and obtain interesting information when the sequence is automatic. Foll owing previous work on the Feigenbaum sequence, we give a necessary entropy -based condition valid for all automatic sequences read by lumping. Applica tions of these ideas to representative examples are discussed. In particula r, we establish new entropic decimation schemes for the Thue-Morse, the Rud in-Shapiro and the paperfolding sequences read by lumping.