Sturmian Words and The Weak Permutation Property of Semigroups

J. Justin, G. Pirillo

IBP-Litp 1994/27: Rapport de Recherche Litp / Litp research reports
8 pages - Décembre/December 1994 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Sturmian Words and The Weak Permutation Property of Semigroups

Résumé : Rappelons qu'un semigroupe a la propriété Ps(*;n) si pour toute suite de n de ses éléments, il y a deux produits de ces n éléments, dans des ordres différents, qui sont égaux. Soit s un mot Sturmien infini (sur un alphabet A à deux lettres). Nous prouvons que le quotient de Rees de A* par l'ensemble des mots non facteurs de s à Ps(*;4) et que ce résultat est optimal. Nous prouvons aussi que si St est l'ensemble de tous les mots Sturmien fini, alors le quotient de Rees A*/(A*-St) a Ps(*;8) .

Abstract : Recall that a semigroup has the property Ps(*;n) if for any sequence of n of its elements, two differently permuted products of these n elements are equal. Let s be an infinite Sturmian word (on a 2-letters alphabet A). We prove that the Rees quotient of A* by the set of the non-factors of s has Ps(*;4) and that this result is the best possible. We prove also that if St is the set of all finite Sturmian words, then the Rees quotient A*/(A*-St) has Ps(*;8).

Publications internes Litp 1994 / Litp research reports 1994