Pattern spectra, substring enumeration, and automatic sequences. (English) Zbl 0753.11012

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\). P. Morton and 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\).


11B85 Automata sequences
68Q45 Formal languages and automata


Zbl 0694.10009
Full Text: DOI


[1] Allouche, J.-P., Automates finis en théorie des nombres, Expo. Math., 5, 239-266 (1987) · Zbl 0641.10041
[2] Allouche, J.-P.; Shallit, J., The ring of \(k\)-regular sequences, (Choffrut, C.; Lenguaer, T., STACS 90. STACS 90, Lecture Notes in Computer Science, Vol. 415 (1990), Springer: Springer Berlin), 12-23 · Zbl 0742.11012
[3] Christol, G.; Kamae, T.; Mendès France, M.; Rauzy, G., Suites algébriques, automates et substitutions, Bull. Soc. Math. France, 108, 401-419 (1980) · Zbl 0472.10035
[4] Cobham, A., Uniform tag sequences, Math. Systems Theory, 6, 164-192 (1972) · Zbl 0253.02029
[5] Coquet, J., A summation formula related to the binary digits, Invent. Math., 73, 107-115 (1983) · Zbl 0528.10006
[6] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[7] Morton, P.; Mourant, W., Paper folding digit patterns, and groups of arithmetic fractals, Proc. Lond. Math. Soc., 59, 253-293 (1989) · Zbl 0694.10009
[8] Newman, D. J., On the number of binary digits in a multiple of three, Proc. Amer. Math. Soc., 21, 719-721 (1969) · Zbl 0194.35004
[9] Newman, D. J.; Slater, M., Binary digit distribution over naturally defined sequences, Trans. Amer. Math. Soc., 213, 71-78 (1975) · Zbl 0324.10053
[10] Salon, O., Quelles tuiles! (Pavages apériodiques du plan et automates bidimensionnels), Séminaire de Théorie des Nombres de Bordeaux, 1, 1-25 (1989), (2ème Série) · Zbl 0726.11020
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.