Two of the present authors have given in 1993 a bijection Phi between words on a totally ordered alphabet and multisets of primitive necklaces. At the same time and independently, Burrows and Wheeler gave a data compression algorithm which turns out to be a particular case of the inverse of Phi. In the present article, we show that if one replaces in Phi the standard permutation of a word by the co-standard one (reading the word from right to left), then the inverse bijection is computed using the alternate lexicographic order (which is the order of real numbers given by continued fractions) on necklaces, instead of the lexicographic order as for Phi(-1). The image of the new bijection, instead of being as for Phi the set of all multisets of primitive necklaces, is a special set of multisets of necklaces (not all primitive); it turns out that this set is naturally linked to the decomposition of the enveloping algebra of the oddly generated free Lie superalgebra, induced by the Poincare-Birkhoff-Witt theorem.

Gessel, I., Restivo, A., & Reutenauer, C. (2012). A bijection between words and multisets of necklaces. EUROPEAN JOURNAL OF COMBINATORICS, 33(7), 1537-1546 [10.1016/j.ejc.2012.03.016].

A bijection between words and multisets of necklaces

RESTIVO, Antonio;
2012

Abstract

Two of the present authors have given in 1993 a bijection Phi between words on a totally ordered alphabet and multisets of primitive necklaces. At the same time and independently, Burrows and Wheeler gave a data compression algorithm which turns out to be a particular case of the inverse of Phi. In the present article, we show that if one replaces in Phi the standard permutation of a word by the co-standard one (reading the word from right to left), then the inverse bijection is computed using the alternate lexicographic order (which is the order of real numbers given by continued fractions) on necklaces, instead of the lexicographic order as for Phi(-1). The image of the new bijection, instead of being as for Phi the set of all multisets of primitive necklaces, is a special set of multisets of necklaces (not all primitive); it turns out that this set is naturally linked to the decomposition of the enveloping algebra of the oddly generated free Lie superalgebra, induced by the Poincare-Birkhoff-Witt theorem.
Settore INF/01 - Informatica
Gessel, I., Restivo, A., & Reutenauer, C. (2012). A bijection between words and multisets of necklaces. EUROPEAN JOURNAL OF COMBINATORICS, 33(7), 1537-1546 [10.1016/j.ejc.2012.03.016].
File in questo prodotto:
File Dimensione Formato  
A bijection between words and multisets of necklaces 2012.pdf

Solo gestori archvio

Descrizione: Articolo principale
Dimensione 225.98 kB
Formato Adobe PDF
225.98 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10447/73704
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 3
social impact