Portal de Periódicos da CAPES

On regular trace languages

1987; Elsevier BV; Volume: 52; Issue: 1-2 Linguagem: Francês

10.1016/0304-3975(87)90080-6

1879-2294

Jacques Sakarovitch,

Logic, Reasoning, and Knowledge

We characterize here the free partially commutative monoids the regular sets of which form a Boolean algebra or are all unambiguous: these are, in both cases, the free products of free commutative monoids. This result has been established independently by other authors but the method used here is original. It is based on the properties of generalized automata on free products of monoids. Nous caractérisons ici les monoïdes de commutation dont les parties rationnelles forment une algèbre de Boole et ceux dont les parties rationnelles sont toutes non ambiguës: ce sont, dans les deux cas, les produits libres de monoïdes commutatifs libres. Ce résultat a été établi, indépendamment, par d'autres auteurs mais la méthode employée ici, qui utilise les propriétés des automatesz généralisés sur des produits libres de monoïdes, est originale.