TCS Journal 1992 Journal Article
Pattern spectra, substring enumeration, and automatic sequences
- Jean-Paul Allouche
- Patrick Morton
- Jeffrey Shallit
Let {S(n)} n⩾0 be an infinite sequence on {+1, −1}. In a previous paper, Morton and Mourant (1989) showed how to expand {S(n)} n⩾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 (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.