Computing the closure of sets of words under partial commutations
avec Y. MÉTIVIER ET P.A. WACRENIER
In Z. Fulöp and F. Gécseg, editors, ICALP'95, volume 974 of Lecture Notes in Computer Science, pages 75-86. Springer Verlag, 1995. 

 Abstract.
The aim of this paper is the study of a procedure S given by Y. Métivier (1987, 1991). We prove that this procedure can compute the closure of the star of a closed recognizable set of words if and only if this closure is also recognizable. This necessary and sufficient condition gives a semi algorithm for the Star Problem. As intermediary results, using S, we give new proofs of some known results. 
In the last part, we compare the power of S with the rank notion introduced by Hashigushi (1991). Finally, we characterize the recognizability of the closure of a recognizable set of words using this rank notion.

Résumé.
Le but de ce papier est l'étude d'une procédure S donnée dans [Met87,MR91]. Nous montrons que cette procédure peut calculer la clôture de l'étoile d'un ensemble reconnaissable si et seulement si cette clôture est aussi reconnaissable. Cette condition nécessaire et suffisante fournit un semi-algorithme pour lrésoudre le problème de l'étoile. Nous donnons également de nouvelles preuves (utilisant la procédure S) de résultats connus.
Dans la dernière partie, nous comparons la puissance d'expression de S avec la notion de ce rang introduite par Hashigushi [Has91]. Finalement, nous caractérisons la reconnaissabilité de la clôture d'un ensemble reconnaissable de mots en utilisant cette notion de rang.

@inproceedings{MRW1995,
  author = {Métivier, Y. and Richomme, G. and Wacrenier, P. A.},
  title = {Computing the Closure of Sets of Words under Partial Commutations},
  booktitle = {ICALP'95},
  editor = {Ful\"op, Z. and G\'ecseg, F.},
  pages = {75-86},
  year = {1995},
  volume = {974},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer Verlag},
}