PATTERN SPECTRA, SUBSTRING ENUMERATION, AND AUTOMATIC SEQUENCES

Let {S(n))n greater-than-or-equal-to 0 be an infinite sequence on {+1, -1}. In a previous paper, Morton and Mourant (1989) showed how to expand {S(n)} n greater-than-or-equal-to 0 uniquely as a (possibly infinite) termwise product of certain special infinite sequences on {+1, -1}, called pattern sequences. Moreover, they characterized those sequences for which the expansion, or pattern spectrum, is finite. In this paper, we first give the expansion of a subsequence of the Prouhet-Thue-Morse sequence studied by Newman and Slater (1969 and 1975) and Coquet (1983). Then we characterize the sequences given by certain special infinite products. Next, we prove a general theorem characterizing the pattern spectrum when S is an automatic sequence in the sense of Cobham (1972) and Christol et al. (1980). We also show how to deduce this theorem as the consequence of a purely language-theoretic result about enumeration of substrings. Finally, we prove that no sequence can be its own pattern spectrum.