Comptes Rendus
Computer Science
Möbius inversion formula for the trace group
Comptes Rendus. Mathématique, Volume 339 (2004) no. 12, pp. 899-904.

A trace group (monoid) is the quotient of a free group (monoid) by relations of commutation between some pairs of generators. We prove an analog for the trace group of the Möbius inversion formula for the trace monoid (Cartier and Foata, 1969).

Un groupe (monoïde) de traces est le quotient d'un groupe (monoïde) libre par des relations de commutation entre certaines paires de générateurs. On montre un analogue pour le groupe de traces de la formule d'inversion de Möbius pour le monoïde de traces (Cartier et Foata, 1969).

Received:
Accepted:
Published online:
DOI: 10.1016/j.crma.2004.10.017

Anne Bouillard 1; Jean Mairesse 1

1 LIAFA, CNRS – université Paris 7, case 7014, 2, place Jussieu, 75251 Paris cedex 05, France
@article{CRMATH_2004__339_12_899_0,
     author = {Anne Bouillard and Jean Mairesse},
     title = {M\"obius inversion formula for the trace group},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {899--904},
     publisher = {Elsevier},
     volume = {339},
     number = {12},
     year = {2004},
     doi = {10.1016/j.crma.2004.10.017},
     language = {en},
}
TY  - JOUR
AU  - Anne Bouillard
AU  - Jean Mairesse
TI  - Möbius inversion formula for the trace group
JO  - Comptes Rendus. Mathématique
PY  - 2004
SP  - 899
EP  - 904
VL  - 339
IS  - 12
PB  - Elsevier
DO  - 10.1016/j.crma.2004.10.017
LA  - en
ID  - CRMATH_2004__339_12_899_0
ER  - 
%0 Journal Article
%A Anne Bouillard
%A Jean Mairesse
%T Möbius inversion formula for the trace group
%J Comptes Rendus. Mathématique
%D 2004
%P 899-904
%V 339
%N 12
%I Elsevier
%R 10.1016/j.crma.2004.10.017
%G en
%F CRMATH_2004__339_12_899_0
Anne Bouillard; Jean Mairesse. Möbius inversion formula for the trace group. Comptes Rendus. Mathématique, Volume 339 (2004) no. 12, pp. 899-904. doi : 10.1016/j.crma.2004.10.017. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2004.10.017/

[1] A. Bouillard, Rapport de DEA : Le groupe de traces, LIAFA research report 2002-13, Université Paris 7, 2002

[2] A. Bouillard; J. Mairesse Generating series of the trace group (Z. Ésik; Z. Fülöp, eds.), Developments in Language Theory, Lecture Notes in Comput. Sci., vol. 2710, Springer-Verlag, 2003, pp. 159-170

[3] P. Cartier; D. Foata Problèmes combinatoires de commutation et réarrangements, Lecture Notes in Math., vol. 85, Springer, 1969

[4] V. Diekert Combinatorics on traces, Lecture Notes in Comput. Sci., vol. 454, Springer-Verlag, 1990

[5] The Book of Traces (V. Diekert; G. Rozenberg, eds.), World Scientific, 1995

[6] C. Droms; B. Servatius; H. Servatius Groups assembled from free and direct products, Discrete Math., Volume 109 (1992), pp. 69-75

[7] C. Duboc, Commutations dans les monoïdes libres : un cadre théorique pour l'étude du parallélisme, PhD thesis, Université de Rouen, 1986. Also LITP Report 86-25, Université Paris 7

[8] G. Duchamp; D. Krob Partially commutative Magnus transformations, Int. J. Algebra Comput., Volume 3 (1993), pp. 15-41

[9] D. Epstein; J. Cannon; D. Holt; S. Levy; M. Paterson; W. Thurston Word Processing in Groups, Jones and Bartlett, Boston, 1992

[10] M. Goldwurm; M. Santini Clique polynomials have a unique root of smallest modulus, Inform. Process. Lett., Volume 75 (2000) no. 3, pp. 127-132

[11] G. Hardy; E. Wright An Introduction to the Theory of Numbers, Clarendon Press, Oxford, 1979

[12] D. Krob; J. Mairesse; I. Michos Computing the average parallelism in trace monoids, Discrete Math., Volume 273 (2003), pp. 131-162

[13] G. Lallement Semigroups and Combinatorial Applications, Wiley, New York, 1979

[14] J. Lewin The growth function of a graph group, Commun. Algebra, Volume 17 (1989) no. 5, pp. 1187-1191

[15] G.-C. Rota On the foundations of combinatorial theory. I. Theory of Möbius functions, Z. Wahrscheinlichkeitstheor. Verw. Geb., Volume 2 (1964), pp. 340-368

[16] A. Vershik; S. Nechaev; R. Bikbov Statistical properties of locally free groups with applications to braid groups and growth of random heaps, Commun. Math. Phys., Volume 212 (2000) no. 2, pp. 469-501

[17] G.X. Viennot Heaps of pieces, I: Basic definitions and combinatorial lemmas (G. Labelle; P. Leroux, eds.), Combinatoire Énumérative, Lecture Notes in Math., vol. 1234, Springer, 1986, pp. 321-350

Cited by Sources:

Comments - Policy