Generating Series of the Trace Group

  • Anne Bouillard
  • Jean Mairesse
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2710)


We prove an analog for trace groups of the Möbius inversion formula for trace monoids (Cartier-Foata, 1969). A by-product is to obtain an explicit and combinatorial formula for the growth series of a trace group. This is used to study the average height of traces.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    A. Bouillard. Rapport de DEA: Le groupe de traces. LIAFA research report 2002-13, Université Paris 7, 2002.Google Scholar
  2. 2.
    C. Campbell, E. Robertson, N. Ruškuc, and R. Thomas. Automatic semigroups. Theoret. Comput. Sci., 250(1–2):365–391, 2001.zbMATHCrossRefMathSciNetGoogle Scholar
  3. 3.
    P. Cartier and D. Foata. Problèmes combinatoires de commutation et réarrangements. Number 85 in Lecture Notes in Mathematics. Springer, 1969.Google Scholar
  4. 4.
    C. Choffrut and M. Goldwurm. Determinants and Möbius functions in trace monoids. Discrete Math., 194(1–3):239–247, 1999.zbMATHCrossRefMathSciNetGoogle Scholar
  5. 5.
    V. Diekert. Combinatorics on traces. Number 454 in LNCS. Springer Verlag, 1990.zbMATHGoogle Scholar
  6. 6.
    V. Diekert and A. Muscholl. Solvability of equations in free partially commutative groups is decidable. In ICALP’01, n. 2076 in LNCS, pages 543–554. Springer, 2001.Google Scholar
  7. 7.
    V. Diekert and G. Rozenberg, editors. The Book of Traces. World Scientific, 1995.Google Scholar
  8. 8.
    C. Droms, B. Servatius, and H. Servatius. Groups assembled from free and direct products. Discrete Math., 109:69–75, 1992.zbMATHCrossRefMathSciNetGoogle Scholar
  9. 9.
    C. Duboc. Commutations dans les monoïdes libres: un cadre théorique pour l’étude du parallélisme. PhD thesis, Univ. Rouen, 1986.Google Scholar
  10. 10.
    G. Duchamp and D. Krob. Partially commutative Magnus transformations. Internat. J. Algebra Comput., 3:15–41, 1993.zbMATHCrossRefMathSciNetGoogle Scholar
  11. 11.
    D. Epstein, J. Cannon, D. Holt, S. Levy, M. Paterson, and W. Thurston. Word processing in groups. Jones and Bartlett, Boston, 1992.zbMATHGoogle Scholar
  12. 12.
    M. Goldwurm and M. Santini. Clique polynomials have a unique root of smallest modulus. Information Processing Letters, 75(3):127–132, 2000.CrossRefMathSciNetGoogle Scholar
  13. 13.
    G. Hardy and E. Wright. An introduction to the theory of numbers. Oxford at the Clarendon Press, 1979. 5-th edition.Google Scholar
  14. 14.
    D. Krob, J. Mairesse, and I. Michos. Computing the average parallelism in trace monoids. Discrete Math., 2002. Accepted for publication. An abridged version appears in STACS’02, LNCS 2285, p. 477–488, Springer.Google Scholar
  15. 15.
    G. Lallement. Semigroups and Combinatorial Applications. Wiley, New-York, 1979.zbMATHGoogle Scholar
  16. 16.
    G.-C. Rota. On the foundations of combinatorial theory. I. Theory of Möbius functions. Z. Wahrscheinlichkeitstheor. Verw. Geb., 2:340–368, 1964.zbMATHCrossRefMathSciNetGoogle Scholar
  17. 17.
    A. Vershik, S. Nechaev, and R. Bikbov. Statistical properties of locally free groups with applications to braid groups and growth of random heaps. Commun. Math. Phys., 212(2):469–501, 2000.zbMATHCrossRefMathSciNetGoogle Scholar
  18. 18.
    G.X. Viennot. Heaps of pieces, I: Basic definitions and combinatorial lemmas. In Labelle and Leroux, editors, Combinatoire Énumérative, number 1234 in Lect. Notes in Math., pages 321–350. Springer, 1986.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Anne Bouillard
    • 1
  • Jean Mairesse
    • 1
  1. 1.Liafa, CnrsUniversité Paris 7Paris Cedex 5France

Personalised recommendations