Partial Commutation and Traces

V. DiekerT, Y. Métivier

IBP-Litp 1996/04: Rapport de Recherche Litp / Litp research reports
81 pages - Février/February 1996 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Partial Commutation and Traces

Résumé : Les monoïdes de commutations suscitent de nombreux problèmes et de beaux résultats liés à la combinatoire des traces, aux ensembles reconnaissables ou bien encore aux automates asynchrones (automates dont la définition et le fonctionnement rendent compte de l'aspect distribué d'un système). Cette présentation a pour but de mettre en avant certains de ces résultats et des techniques propres aux monoïdes de commutation.

Abstract : The theory of partial commutation and of trace monoids has been developed both by its interpretation as a model for parallel computation and by its mathematical interest in algebra, formal languages, and combinatorics. Since the beginning in combinatorics by Cartier and Foata (1969) and the formulation of trace theory by Mazurkiewicz (1977) the theory has grown in breadth and depth. It led to significant results with interesting applications. The present contribution reflects some important topics including basic properties and infinite traces. Each section gives a short bibliographical remark and leads to further references.

Publications internes Litp 1996 / Litp research reports 1996