Coding and strong coding in trace monoids

V. Bruyère, C. de Felice

IBP-Litp 1995/09: Rapport de Recherche Litp / Litp research reports
12 pages - Février/February 1995 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Coding and strong coding in trace monoids

Résumé : Nous étudions le problème de décidabilité de l'existence d'un codage entre deux monoïdes de traces. Ce problème a reçu récemment une réponse positive, dans le cadre des codages forts (Diekert, Muscholl, Reinhardt). Nous donnons ici une réponse positive pour des codages quelconques, quand le premier monoïde est un produit direct de monoïdes libres, ou un produit libre de monoïdes commutatifs libres. Nous montrons comment les situations diffèrent selon qu'un codage ou un codage fort est utilisé.

Abstract : We compare two notions of coding on traces, called coding and strong coding, in relation with the decision problem of the existence of a coding between two given trace monoids. We positively solve this problem if the first monoid is either a direct product of free monoids, or a free product of free commutative monoids. We show how the situation differs in the case of strong codings.

Publications internes Litp 1995 / Litp research reports 1995