Cancellation, pumping and permutation in formal languages

Recent results on syntactic groups of prefix codes

International audience; We give a simplified presentation of groups in transformation monoids. We use this presentation to describe two recent results on syntactic groups of prefix codes. The first one uses Sturmian words to build finite bifix codes with a given permutation group as syntactic group. The second one describes a class of prefix codes such that all their syntactic groups are cyclic.

Some applications of a theorem of Shirshov to language theory

Some applications of a theorem of Shirshov to language theory are given: characterization of regular languages, characterization of bounded languages, and a sufficient condition for a language to be Parikh-bounded.

A bijection between words and multisets of necklaces

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, ins…

On generalized Lyndon words

Abstract A generalized lexicographical order on infinite words is defined by choosing for each position a total order on the alphabet. This allows to define generalized Lyndon words. Every word in the free monoid can be factorized in a unique way as a nonincreasing factorization of generalized Lyndon words. We give new characterizations of the first and the last factor in this factorization as well as new characterization of generalized Lyndon words. We also give more specific results on two special cases: the classical one and the one arising from the alternating lexicographical order.