A generalization of automatic sequences. (English) Zbl 0662.68052

The paper deals with sequences of strings from a word semigroup \(A^*\) and gives a connection between the following ideas: (1) generalized systems of enumeration, (2) locally catenative formulas, (3) automata with generalized digits as inputs and (4) fixed points of (certain) morphisms. There has been considerable interest in the cases (1)-(4) in the theory of combinatorics on words and in the theory of automata. The author unifies this problem area in the present work.
Reviewer: T.J.Harju


68Q45 Formal languages and automata
11B83 Special sequences and polynomials
Full Text: DOI


[1] Allouche, J.-P., Automates finis et théorie des nombres, Exposition. Math., 5, 239-266 (1987) · Zbl 0641.10041
[2] Bombieri, E.; Taylor, J. E., Which distributions of matter diffract? An initial investigation, J. Physique, 47, 19-28 (1986) · Zbl 0693.52002
[3] de Bruijn, N. G., Sequences of zeros and ones generated by special production rules, Kon. Nederl. Akad. Wetensch. Proc. Ser. A, 84, 27-37 (1981), ( Indag. Math.43) · Zbl 0471.10007
[4] 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
[5] Cobham, A., Uniform tag sequences, Math. Systems Theory, 6, 164-192 (1972) · Zbl 0253.02029
[6] Dekking, M.; Mendès France, M.; van der Poorten, A., FOLDS!, Math. Intell., 4, 173-195 (1982) · Zbl 0493.10002
[7] Eilenberg, S., Automata, Languages, and Machines, Volume A (1974), Academic Press: Academic Press New York · Zbl 0317.94045
[8] Fraenkel, A. S., Systems of numeration, Amer. Math. Monthly, 92, 105-114 (1985) · Zbl 0568.10005
[9] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[10] Pansiot, J.-J., Hiérarchie et fermeture de certaines classes de tag-systèmes, Acta Inform., 20, 179-196 (1983) · Zbl 0507.68046
[11] Rauzy, G., Nombres algébriques et substitutions, Bull. Soc. Math. France, 110, 147-178 (1982) · Zbl 0522.10032
[12] Rozenberg, G.; Lindenmayer, A., Developmental systems with locally catenative formulas, Acta Inform., 2, 214-248 (1973) · Zbl 0304.68076
[13] Stolarsky, K. B., Beatty sequences, continued fractions, and certain shift operators, Canad. Math. Bull., 19, 473-482 (1976) · Zbl 0359.10028
[14] Venkov, B. A., Elementary Number Theory (1970), Wolters-Noordhoff: Wolters-Noordhoff Groningen · Zbl 0204.37101
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.