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},
}