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
every 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, 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 icontenant au plus quatre traces ou au plus
deux traces connexes, on peut décider si X* est reconnaissable.
@inproceedings{MR1994,
author = {Métivier, Y. and Richomme, G.},
title = {On the Star Operation and the Finite Power Property
in Free Partially Commutative Monoids},
booktitle = {STACS'94},
editor = {Enjalbert, P. and Mayr, E.W. and Wagner, K.W.},
pages = {341-352},
year = {1994},
volume = {775},
series = {Lecture Notes in Computer Science},
publisher = {Springer Verlag},
}