Pattern spectra, substring enumeration, and automatic sequences (Q1190468)

Let \(P=p_ 1\ldots p_ h\) be a binary pattern, i.e., a string of 0's and 1's such that \(p_ 1=1\) and let \(a_ P\) be the corresponding pattern sequence defined by \(a_ P(n)=(-1)^{e_ P(n)}\) where \(e_ P(n)\) counts the number of occurrences of \(P\) in the binary expansion of an integer \(n\geq 0\). \textit{P. Morton} and \textit{W. J. Mourant} [Proc. Lond. Math. Soc., III. Ser. 59, 253-293 (1989; Zbl 0694.10009)] showed that every sequence \(s\) on \(\{+1,-1\}\) can be uniquely expressed as the product \(s(n)=s(0)\prod_{P\in{\mathcal P}}a_ P(n)\) where \({\mathcal P}\) is a finite or infinite set of patterns. One of the main results of this paper (Theorem 2.1) says that the sequence \(s\) is 2-automatic if and only if \({\mathcal P}\) is a regular set of words on the alphabet \(\{0,1\}\) that is to say \({\mathcal P}\) is recognizable by a finite 2-automaton. This theorem is introduced by some interesting examples and is extended to the following purely language-theoretic result: Let \(\Sigma\) be a finite alphabet and let \(\Sigma^*\) be the set of strings drawn from \(\Sigma\). For strings \(r\) and \(w\) define \(\sigma_ r(w)\) to count the number of occurrences of \(r\) as a substring of \(w\) (for \(r\) equal to the empty string, \(\sigma_ r(w)\) counts the length of \(w\) plus 1) and for any language \(L\subset\Sigma^*\) define \(\sigma_ L:\Sigma^*\to\mathbb{N}\) by \(\sigma_ L(w)=\sum_{r\in L}\sigma_ r(w)\). Now we consider, for any integer \(k\geq 2\), the Nerode equivalence \(\sim_ k\) on \(\Sigma^*\) given by \[ w\sim_ kw'\Leftrightarrow\forall v\in\Sigma^*,\quad\sigma_ L(wv)=\sigma_ L(w'v)\bmod k. \] We shall say that \(\sim_ k\) is finite if the set of classes \({\Sigma/\sim_ k}\) is finite. Then (Theorem 4.1) the following properties are equivalent: (i) The language \(L\) is regular; (ii) The equivalent relations \(\sim_ k\) all are finite; (iii) At least one relation \(\sim_ k(k\geq 2)\) is finite (in other words, following the terminology of the authors, the map \(w\mapsto\sigma_ L(w)\bmod k\) is given by a finite \(\Sigma\)-automaton with outputs). In the definition of \(\sim_ k\), without changing the result, the map \(\sigma_ L\) can be replaced by \(\pi_ L:w\mapsto\pi_ L(w)\) where \(\pi_ L(w)\) counts the number of strings in \(L\) which occur as a prefix of \(w\).