Abstract.
We address in this paper the decidability of the Star Problem in trace
monoids (``Let X be a recognizable trace language, is L*
recognizable ?'') and the decidability of the Finite Power Problem (``Let
X
be a recognizable trace language, does there exist an integer
n
such that X * = U i<= n Xi?'').
We define a family F of free partially commutative monoids where
both the Star Problem and the Finite Power Problem are decidable. The family
F
contains all the already known cases of decidability of the two problems.
Résumé.
Nous nous intéressons dans ce papier à la décidabilité
du problème de l'étoile (étant donné un ensemble
X
reconnaissable de traces, est-ce que X * est reconnaissable)
dans les monoïdes libres partiellement commutatifs. Nous nous intéressons
aussi à la décidabilité du problème de la puissance
finie (soit X un ensemble reconnaissable de traces, existe-t-il
un entier k tel que X* = Ui<= nXi?'').
On définit une famille F de monoïdes libres partiellement
commutatifs dans lesquels le problème de l'étoile et le problème
de la puissance finie sont décidables. La famille F contient
tous les cas connus de décidabilité de ces deux problèmes.
@inproceedings{Ric1994,
author = {Richomme, G.},
title = {Some Trace Monoids where both the Star Problem
and the Finite Power Problem are Decidable},
booktitle = {MFCS'94},
editor = {Pr\'{i}vara, I. and Rovan, B. and Ru\v{z}i\v{c}ka},
pages = {577-586},
year = {1994},
volume = {841},
series = {Lecture Notes in Computer Science},
publisher = {Springer Verlag},
}