Abstract.
In the last decade, research on the star problem in trace monoids (is the iteration of a recognizable language also recognizable?) has pointed out the importance of the finite power property to achieve partial solutions to this problem. We prove that the star problem is decidable in some trace monoid if and only if in the same monoid, it is decidable whether a recognizable language has the finite power property. Intermediate results allow us to give a shorter proof for the decidability of the two previous problems in every trace monoid without C4-submonoid.We also deal with some earlier ideas, conjectures, and questions which have been raised in the research on the star problem and the finite power property, e.g., we show the decidability of these problems for recognizable languages which contain at most one non-connected trace.

Résumé.
Lors des dix dernières années, la recherche sur le problème de l'étoile dans les monoïdes de traces (est-ce que l'itération d'un langage reconnaissable est aussi reconnaissable?) a montré l'importance de la propriété de puissance finie pour obtenir des solutions partielles. Nous montrons que le problème de l'étoile est décidable dans un monoïde de traces si et seulement si, dans le même monoïde, on peut décider si un langage a la propriété de puissance finie. Des résultats intermédiaires nous permettent de donner une preuve plus courte que les précédentes connues pour la décidabilité des deux problèmes dans tout monoïde de traces qui ne possède pas de C4 comme sous-monoïdes.
Nous nons intéressons aussi à d'autres idées, conjectures et questions soulevées dans les recherches sur le problème de l'etoile et la propriété de puissance finie. Par exemple, nous montrons la décidabilité de ces problèmes pour des langages contenant au plus une trace non connexe.

@article{KR2001,
  author = {Kirsten, D. and Richomme, G.},
  title = {Decidability Equivalence between the Star Problem and the Finite Power Problem in Trace Monoids},
  journal = {Theory of Computing Systems},
  year = {2001},
  volume = {34},
  pages = {193-227},
}