Abstract.
We prove that if it is decidable whether X* is recognizable
for a recognizable subset X of a free partially commutative monoid,
then it is decidable whether a recognizable subset of a free partially
commutative monoid possesses the finite power property. We prove that if
any trace of a set X is connected, we can decide whether X
possesses the Finite Power Property. Finally, it is also shown that if
X
is a finite set containing at most four traces or at most two connected
traces, it is decidable whether X * is recognizable.
Résumé.
Nous montrons que s'il est décidable, dans un monoïde libre
partiellement commutatif, de savoir si l'étoile d'un ensemble reconnaissable
est aussi reconnaissable, alors il est décidable de savoir si un
sous ensemble d'un monoïde libre partiellement commutatif possède
la propriété de puissance finie. Nous montrons également
que pour un ensemble fini X contenant au plus quatre traces ou au plus
deux traces connexes, on peut décider si X* est reconnaissable.
@article{MR1995,
author = {Métivier, Y. and Richomme, G.},
title = {New results on the Star Problem in Trace Monoids},
journal = {Information and Computation},
year = {1995},
volume = {119},
number = {2},
pages = {240-251},
}