Monoïde des traces

En mathématiques et en informatique, une trace est un ensemble de mots, où certaines lettres peuvent commuter, et d'autres non. Le monoïde des traces ou monoïde partiellement commutatif libre est le monoïde quotient du monoïde libre par une relation de commutation de lettres. Le monoïde des traces est donc une structure qui se situe entre le monoïde libre et le monoïde commutatif libre. L'intérêt mathématique du monoïde des traces a été mis en évidence dans l'ouvrage fondateur . Les traces apparaissent dans la modélisation en programmation concurrente, où les lettres qui peuvent commuter représentent des parties de processus qui peuvent s'exécuter de façon indépendante, alors que les lettres qui ne commutent pas représentent des verrous, leur synchronisation ou l'union de threads. Ce modèle a été proposé dans . Soit un alphabet. Une relation d'indépendance ou relation de commutation est une relation binaire sur qui est irréflexive et symétrique. Le couple est le graphe d'indépendance ou graphe de commutation. Le complément d'une relation d'indépendance est une relation de dépendance. C'est une relation réflexive et symétrique. Le couple est le graphe de dépendance. thumb|Graphe d'indépendance thumb|Graphe de dépendance Soit et . Le graphe d'indépendance et le graphe de dépendance, si l'on omet les boucles, sont décrits dans les figures ci-contre. La relation d'indépendance induit sur une relation d'équivalence notée . Deux mots et sont équivalents modulo s'il existe une suite de mots tels que , , et pour il existe des mots et des lettres tels que et et Ainsi, deux mots sont équivalents exactement quand ils peuvent être obtenus, l'un de l'autre, par une suite de transpositions de lettres indépendantes adjacentes. La relation est une congruence. Le quotient de par est donc un monoïde. C'est le monoïde partiellement commutatif libre induit par Il est noté . Les éléments de qui ont les classes d'équivalence de mots pour la relation , sont appelés des traces, et le monoïde est appelé le monoïde des traces.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (9)

Cours associés (2)

Séances de cours associées (14)

Monoïde des traces

History monoid

In mathematics and computer science, a history monoid is a way of representing the histories of concurrently running computer processes as a collection of strings, each string representing the individual history of a process. The history monoid provides a set of synchronization primitives (such as locks, mutexes or thread joins) for providing rendezvous points between a set of independently executing processes or threads.

String operations

In computer science, in the area of formal language theory, frequent use is made of a variety of string functions; however, the notation used is different from that used for computer programming, and some commonly used functions in the theoretical realm are rarely used when programming. This article defines some of these basic terms. A string is a finite sequence of characters. The empty string is denoted by . The concatenation of two string and is denoted by , or shorter by . Concatenating with the empty string makes no difference: .

This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how

We teach the fundamental aspects of analyzing and interpreting computer languages, including the techniques to build compilers. You will build a working compiler from an elegant functional language in

Langages formels : Concepts CS-320: Computer language processing

Couvre les concepts fondamentaux des langues formelles, y compris les alphabets, les mots, les langues et l'égalité des mots.

Langages formels : Concepts CS-320: Computer language processing

Couvre les bases des langues formelles, y compris les alphabets, les mots et les langues, ainsi que des opérations comme la concaténation et l'inversion.

Cryptographie Diffie-Hellman: Bases COM-401: Cryptography and security

Présente les bases de la cryptographie Diffie-Hellman, couvrant les algorithmes, les monoïdes et les protocoles d'accord clés.