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).
Accepted:
Published online:
Anne Bouillard 1; Jean Mairesse 1
@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}, }
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] 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] Problèmes combinatoires de commutation et réarrangements, Lecture Notes in Math., vol. 85, Springer, 1969
[4] 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] 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] Partially commutative Magnus transformations, Int. J. Algebra Comput., Volume 3 (1993), pp. 15-41
[9] Word Processing in Groups, Jones and Bartlett, Boston, 1992
[10] Clique polynomials have a unique root of smallest modulus, Inform. Process. Lett., Volume 75 (2000) no. 3, pp. 127-132
[11] An Introduction to the Theory of Numbers, Clarendon Press, Oxford, 1979
[12] Computing the average parallelism in trace monoids, Discrete Math., Volume 273 (2003), pp. 131-162
[13] Semigroups and Combinatorial Applications, Wiley, New York, 1979
[14] The growth function of a graph group, Commun. Algebra, Volume 17 (1989) no. 5, pp. 1187-1191
[15] On the foundations of combinatorial theory. I. Theory of Möbius functions, Z. Wahrscheinlichkeitstheor. Verw. Geb., Volume 2 (1964), pp. 340-368
[16] 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] 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