Formal Power Series and Combinatorial Physics

- In honour of Philippe Flajolet for his 60th Birthday -

Gérard H. E. Duchamp and Christophe Tollu. ^{∗}

Abstract

0

1 Introduction

2 Generalities

Rappel ample de cela boite à outils qui a qui été construite à Bonn, langages comme supports de series.

3 Application to Combinatorial Physics

3.1 Sweedlers Duals

Reprise de Bonn, mais avec plus de motivations “Physiques” (observables, comme pour le tutorial de Prague).

3.2 Level change languages

Langages de changement de niveau pour des chemins codés par des lettres.

3.2.1 The carrier problem Reprise de l’article avec Katriel avec les fractions continues (+ crdits à Flajolet)

3.2.2 Motzkin paths and orthogonal polynomials Eclairage avec les spécialisations de langages de chemins, en donnant bien les crédits à tout le monde (Viennot, Flajolet, Bojeiko).

∗LIPN - UMR 7030 CNRS - Universit Paris 13 F-93430 Villetaneuse, France

0Version compilée le 20-03-2009 07:21

3.3 Supporting languages

Formule CBH et rationalité du support de la formule de Dynkin (peut-être annoncer le travail en cours avec Silvia).

4 Concluding remarks

References

[1] E. Abe Hopf algebras. Cambridge (1980)

[2] J. Berstel, C. Reutenauer Rational series and their languages EATCS Monographs on Theoretical Computer Science. Springer (1988).

[3] Bourbaki N., Algebra, chapter III, Springer

[4] Bourbaki N., Théories spectrales, Hermann

[5] A. Cayley, On certain results related to quaternions. Phil. Mag. 26, 141-145 (1845).

[6] Champarnaud J.-M., Duchamp G. Derivatives of rational expressions and related theorems, T.C.S. 313 31 (2004).

[7] V. Chari, A. Pressley, A guide to quantum groups. Cambridge (1994).

[8] P.M. Cohn, Free rings and their relations. Acad. Press (1985).

[9] A. Connes, Noncommutative geometry. Acad. Press (1994).

[10] G. Cauchon, Séries de Malcev-Neumann sur le groupe libre et questions de rationalité, TCS, 98, pp79-97 (1992).

[11] Duchamp G., Reutenauer C., Un critère de rationalité provenant de la géométrie noncommutative Invent. Math. 128 613-622. (1997).

[12] Gérard Duchamp, Hatem Hadj Kacem, Eric Laugerotte, Algebraic elimination of ϵ-transitions, DMTCS, Volume 7, (2005), pp. 51-70

[13] Duchamp G., Flouret M., Laugerotte É., Luque J-G., Direct and dual laws for automata with multiplicities T.C.S. 267, 105-120 (2001).

[14] S. Eilenberg, Automata, languages and machines, (Acad. Press, New-York, 1974).

[15] M. Fliess, Sur le plongement de l’algèbre des séries rationnelles non commutatives dans un corps gauche. CRAS Ser. A 271 pp 926-927 (1970).

[16] M. Fliess, Matrices de Hankel, Jour. of Pure and Appl. Math. 53, 197-222, (1994).

[17] I.M. Gelfand, V.S. Retakh, A theory of non-commutative determinants and characteristic functions of graphs, Funct. Anal. Appl. 26 (1992).

[18] I,M. Gelfand, D. Krob, A. Lascoux, B. Leclerc B, V.S. Retakh and J.- Y.Thibon, Noncommutative symmetric functions, Adv. in Math. 112, 218–348 (1995).

[19] Golan J. S., Power Algebras over Semirings: With Applications in Mathematics and Computer science. Kluwer Academic Publishers (1999).

[20] Golan J. S., Semirings and Affine Equations over Them: Theory and Applications. Kluwer Academic Publishers (2003).

[21] A. Heyting, Die Theorie der linearen Gleichungen in einer Zahlenspezies mit nichtkommutativer Multiplikation, Math. Ann., 98, 465-490 (1927).

[22] G. Jacob, Représentations et substitutions matricielles dans la théorie matricielle des semigroupes. Thèse, Univ. de Paris (1975).

[23] Katriel J., Duchamp G., Ordering relations for q-boson operators, continued fractions techniques, and the q-CBH enigma. Journal of Physics A 28 7209-7225 (1995).

[24] J. Lewin, Fields of fractions for group algebras of free groups, Trans. Amer. Math. Soc. 192, 339-346, (1974).

[25] D.S. Passman, The algebraic structure of group rings, John Wiley - Interscience (1977).

[26] A.R. Richardson Simultaneous linear equations over a division ring. Proc. Lond. Math. Soc., 28, 395-420 (1928).

[27] M.P. Schützenberger, On the definition of a family of automata, 4, Information and Control, 275-270, (1961).

[28] M.P. Schützenberger, On a theorem of R. Jungen, Proc. Amer. Math. Soc. 13, 885-889, (1962).