Sur des points fixes de morphismes d’un monoïde libre.(French)Zbl 0691.68065

Logicians define natural numbers as follows: $$A_ 0=\emptyset =\{$$ $$\}$$, $$A_ 1=\{\emptyset \}=\{\{$$ $$\}$$, $$\{$$ $$\{$$ $$\}$$ $$\}$$ $$\}$$, etc. Replacing symbols $$\{$$ and $$\}$$ by a and b respectively, one can write: $$A_ 0=ab$$, $$A_ 1=aabb$$, $$A_ 2=aabaabbb,...,A_{n+1}=aA_ 0A_ 1...A_ nb,...$$. It is shwn that the “limit” of $$A_ n$$ (when n tends to $$+\infty)$$ is an infinite word A which is a fixed point of the endomorphism $$a\to aab$$, $$b\to b$$ of the monoid $$\{a,b\}^*$$. The structure of A is investigated and the methods developed for that purpose are applied to the study of several other infinite sequences. It is proved that there exists a formal series, algebraic over the field of rational fractions modulo 3, which is neither rational nor quadratic and whose sequence of partial quotients is generated by a 3-automaton (this is a partial answer to a conjecture of Mendès-France).
Reviewer: S.M.Goberstein

MSC:

 68Q70 Algebraic theory of languages and automata 20M35 Semigroups in automata theory, linguistics, etc.
Full Text:

References:

 [1] 1. J.-P. ALLOUCHE et F. DRESS, Tours de Hanoi et automates finis, à paraître dans Informatique théorique et aplications.. Zbl0701.68036 MR1060463 · Zbl 0701.68036 [2] 2. L. BAUM et M. SWEET, Continued fractions of algebraic power series in characteris 2, Ann. Math., vol. 103, 1976, p. 539-610. Zbl0312.10024 MR409372 · Zbl 0312.10024 [3] 3. N. BOURBAKI, Théorie des ensembles, chap. 3, p. 39, Hermann, 1963. MR154814 [4] 4. G. CHRISTOL, T. KAMAE, M. MENDÈS FRANCE et G. RAUZY, Suites algébriques, automates, et substitutions, Bull. Soc. Math. France, vol. 108, 1980, p. 401-419. Zbl0472.10035 MR614317 · Zbl 0472.10035 [5] 5. A. COBHAM, Uniform tag sequences, Mathem. Syst. Theory, vol. 6, 1972, p. 164-192. Zbl0253.02029 MR457011 · Zbl 0253.02029 [6] 6. C. DAVIS et D. E. KNUTH, Number représentations and dragon curves, J. Recreational Math., vol. 3, 1970, p. 61-81 et 133-149. [7] 7. W. H. MILLS et D. P. ROBBINS, Continued fractions for certain algebraic power series, J. Numb. Theory, vol. 23, n^\circ 3, 1986, p. 388-404. Zbl0591.10021 MR846968 · Zbl 0591.10021 [8] 8. G. ROZENBERG et A. LINDENMAYER, Developmental Systems with locally catenative formulas, Acta Informatica, vol. 2, 1973, p. 214-248. Note ajoutée le 26 mai 1989 : De nouveaux résultats sur la question posée au début du paragraphe II ont été donnés par le troisième auteur Zbl0304.68076 MR331883 · Zbl 0304.68076 [9] . Par ailleurs d’autres réponses à la question des Mendès France (voir paragraphe III) ont été données par le premier auteur MR974766 [10] Sur le développement en fraction continue de certaines séries formelles, C. R. Acad. Sci. Paris, t. 307, Série I, p. 631-633, 1988. Zbl0657.10035 MR967800 · Zbl 0657.10035
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.