×

Łukasiewicz language and diagonals of formal series. (Langage de Łukasiewicz et diagonales de séries formelles.) (French) Zbl 0864.68058

H. Furstenberg has shown [J. Algebra 7, 271-277 (1967; Zbl 0175.03903)] that every algebraic formal power series in one variable with coefficients in a finite field is the diagonal of a two-variable rational fraction which is moreover explicitly computable. The aim of the paper under review is to give a purely combinatorial proof of this result by using the notion of Łukasiewicz language. More precisely, the author first works with noncommutative series connected with Łukasiewicz languages, then translates the obtained results to algebraic commutative series: this translation gives, for any algebraic formal power series in one variable \(\varphi\) (with coefficients in a finite field and satisfying \(\varphi(0)=0\)), the expression, originally given by Furstenberg in his proof, of a two-variable rational function whose diagonal is \(\varphi\).
Let us note that P. Deligne has shown “conversely” that every diagonal of an algebraic formal power series in several interminates with coefficients in a field of positive characteristic is algebraic [Invent. Math. 76, 129-143 (1984; Zbl 0538.13007)]. For more information on the subject, see the survey of J.-P. Allouche [Sémin. Théor. Nombres Bordx., Sér. II 1, No. 1, 163-187 (1989; Zbl 0714.12006)].

MSC:

68Q45 Formal languages and automata
13F25 Formal power series rings
11B85 Automata sequences
PDF BibTeX XML Cite
Full Text: DOI Numdam EuDML EMIS

References:

[1] Allouche, J.-P., Automates finis en théorie des nombres, Expositiones Mathematicae, 5 (1987), 239-266. · Zbl 0641.10041
[2] Allouche, J.-P., Note sur un article de Sharif et Woodcock, Séminaire de Théorie des Nombres de Bordeaux, 1 (1989) 163-187. · Zbl 0714.12006
[3] Dumas, P., Récurrences mahlériennes, suites automatiques, études asymptotiques, Thèse Bordeaux I (1983).
[4] Christol, G., Kamae, T., France, M. Mendès et Rauzy, G., Suites algébriques, automates et substitutions, Bulletin de la Société mathématique de France, 108 (1980), 401-419. · Zbl 0472.10035
[5] Deligne, P., Intégration sur un cycle évanescent, Inventiones Mathemeticae, 76 (1984), 129-143. · Zbl 0538.13007
[6] Denef, J. et Lipshitz, L.,Algebraic power séries and diagonals, Journal of Number Theory, 26 (1987), 46-67. · Zbl 0609.12020
[7] Eilenberg, S., Automata, Languages and Machines, vol. ALondon, New York, Academic Press (1974). · Zbl 0317.94045
[8] Fliess, M., Sur certaines familles de séries formelles, Thèse, Paris VII (1972).
[9] Furstenberg, H., Algebraic functions over finite fields, Journal of Algebra, 7 (1967) 271-277. · Zbl 0175.03903
[10] Harase, T., Algebraic elements in formal power series rings, Israel Journal of Mathematics, 633 (1988), 281-288. · Zbl 0675.13015
[11] Labelle, J., Langages de Dyck généralisés, Prépublication. · Zbl 0795.05004
[12] Lothaire, Combinatorics on words, Addison-Wesley Publishing Company (1983). · Zbl 0514.20045
[13] Salon, O., Suites automatiques à multi-indices, Séminaire de Théorie des Nombres de Bordeaux, exposé n°4 (1986-1987), 4.01-4.36. (Avec un appendice de J. Shallit). · Zbl 0653.10049
[14] Salon, O., Suites automatiques à multi-indices et algébricité, Comptes-Rendus de l’Académie des Sciences de Paris, t. 305, série I, p. 501-504, 1987. · Zbl 0628.10007
[15] Schützenberger, M.P., Le théorème de Lagrange selon G. N. Raney, Séminaires IRIA, Rocquencourt (1971) 199-205. · Zbl 0363.05016
[16] Sharif, H. et Woodcock, C.F., Algebraic functions over a field of positive characteristic and Hadamard products, Journal of the London Mathematical Society, (2) 37 (1988), 395-403. · Zbl 0612.12018
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.