On Some Decision Problems for Trace Codings

V. Bruyère, C. De Felice, G. Guaiana

IBP-Litp 1994/75: Rapport de Recherche Litp / Litp research reports
31 pages - Décembre/December 1994 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: On Some Decision Problems for Trace Codings

Résumé : Le problème que nous traitons ici est l'existence d'un codage entre deux monoïdes de traces. Nous introduisons une nouvelle notion de codage : le codage fort, qui associe des traces indépendantes à des lettres indépendantes. Nous prouvons que l'existence d'un codage fort entre deux monoïdes de traces est décidable, si le premier monoïde appartient à l'une des deux grandes familles de monoïdes de traces que nous décrivons. Nos conditions de décision sont basées sur des propriétés des graphes répresentant les relations de dépendance. Nous donnons aussi une réponse positive pour les codages forts à une question connexe posée par Ochmanski [Och88].

Abstract : The problem we mainly deal with is the existence of a coding between two trace monoids. We introduce a new notion of coding: the strong coding (independent letters are mapped into independent traces). We prove that the existence of a strong coding between two trace monoids is decidable when the first monoid belongs to one of two large families of trace monoids that we specify. Our decision conditions are based on graph-theoretical properties of the dependence relations. A related question of Ochmanski [Och88] is completely solved for strong codings.

Publications internes Litp 1994 / Litp research reports 1994