L12) Réseaux de Petri et algèbres de processus

Modéliser la concurrence en musique

Dans L11, nous avons découvert la sémantique de processus : l’idée que le sens d’un système est dans ses interactions, pas dans son calcul isolé. Nous avions vu CCS et CSP en survol, comme outils pour modéliser la concurrence. Il est temps d’aller plus loin — et de rencontrer un formalisme d’une élégance visuelle remarquable : les réseaux de Petri. Ensemble, ces outils permettent de formaliser ce que la musique fait depuis toujours : superposer des voix indépendantes qui se synchronisent.

Où se situe cet article ?

Cet article clôt la série L en abordant les modèles de concurrence — le dernier étage de la carte des formalismes (cf. L0).

  • L5 a introduit trois sémantiques (opérationnelle, dénotationnelle, axiomatique)
  • L6–L8 les ont approfondies une par une
  • L9 a exploré les langages mildly context-sensitive (MCSL), au-delà de Chomsky
  • L10 a ajouté les grammaires d’attributs — le contrôle dynamique via les flags
  • L11 a ouvert trois nouvelles sémantiques, dont celle de processus (CCS, CSP, bisimulation)

L12 prend le relais de L11 sur la sémantique de processus et y ajoute les réseaux de Petri — un formalisme graphique complémentaire. L’objectif est double : formaliser rigoureusement ces outils, et montrer qu’ils sont le cadre naturel pour parler de polymétrie.

Pourquoi c’est important ?

La musique est un système concurrent par nature. Un orchestre symphonique, c’est 80 processus parallèles (les musiciens) qui se synchronisent via un canal de communication (le chef d’orchestre). Un duo de jazz, c’est deux processus qui interagissent en temps réel, chacun réagissant à l’autre. La polymétrie (voir M5) — plusieurs mètres superposés — est l’expression la plus pure de cette concurrence.

Ce n’est pas un hasard si BP3 (I2) a été conçu pour la musique indienne, où la polymétrie est omniprésente : un tabliste jouant un cycle rythmique de 7 temps (tāl rūpak) contre un cycle mélodique de 16 temps (tīntāl), c’est de la composition parallèle avec synchronisation au sam (le temps fort commun). Le mécanisme $\{v_1, v_2\}$ de BP3 (B5) formalise exactement cette superposition de flux temporels indépendants.

Pourtant, la plupart des formalismes musicaux traitent la musique de manière séquentielle : une note après l’autre, une voix à la fois. Les grammaires hors-contexte (L2) produisent des arbres — qui sont des structures hiérarchiques, pas des structures parallèles. Pour capturer ce qui se passe quand deux voix jouent en même temps, il faut des outils conçus pour la concurrence.

L’idée en une phrase

Les algèbres de processus (CCS, CSP) et les réseaux de Petri sont deux faces complémentaires du même problème : modéliser des entités indépendantes qui se synchronisent — exactement ce que font les voix dans une pièce polymétrique.

CCS : le calcul des systèmes communicants

Les briques de base

Le CCS (Calculus of Communicating Systems), créé par Robin Milner en 1980, modélise les systèmes concurrents avec une syntaxe minimale :

 

$P ::= \mathbf{0} \mid a.P \mid P_1 + P_2 \mid P_1 \mid P_2 \mid P \setminus \{a\}$

 

Opérateur Notation Signification
Processus inactif $\mathbf{0}$ Terminé — ne fait plus rien
Préfixe $a.P$ Faire l’action $a$, puis continuer comme $P$
Choix $P_1 + P_2$ Se comporter comme $P_1$ ou $P_2$
Parallèle $P_1 \mid P_2$ $P_1$ et $P_2$ simultanément
Restriction $P \setminus \{a\}$ L’action $a$ est privée (interne)

Décryptage :

Le point « $.$ » signifie « puis » (séquencement). La barre « $\mid$ » signifie « en même temps » (parallélisme). Le « $+$ » signifie « ou bien » (choix). Avec ces trois opérateurs, on construit tous les comportements concurrents possibles.

Les actions sont de trois types :

  • $a$ : une action observable (envoyer un signal sur le canal $a$)
  • $\bar{a}$ (a barre) : la co-action (recevoir sur le canal $a$)
  • $\tau$ (tau) : une action interne, invisible de l’extérieur — elle résulte d’une synchronisation

La règle de communication

Quand deux processus parallèles effectuent des actions complémentaires ($a$ et $\bar{a}$), ils se synchronisent :

 

$\frac{P \xrightarrow{a} P’ \quad Q \xrightarrow{\bar{a}} Q’}{P \mid Q \xrightarrow{\tau} P’ \mid Q’} \quad \text{(COM)}$

 

Décryptage :

C’est une règle SOS (Structural Operational Semantics, voir L6). Elle dit : si $P$ peut envoyer sur $a$ et $Q$ peut recevoir sur $a$, alors les deux processus se synchronisent, et l’action résultante est $\tau$ — invisible de l’extérieur. C’est un rendez-vous privé entre $P$ et $Q$.

Exemple : deux musiciens

 

Violon  = jouer_do . jouer_re . jouer_mi . 0
Piano   = jouer_fa . jouer_sol . 0
Duo     = Violon | Piano

 

Le violon joue trois notes, le piano en joue deux — en parallèle, sans synchronisation. C’est exactement la concurrence libre : chacun avance à son rythme.

CSP : la synchronisation par événements partagés

La différence avec CCS

Le CSP (Communicating Sequential Processes) de Hoare (1985) adopte un mécanisme de synchronisation différent. En CCS, la synchronisation est asymétrique (envoi $a$ / réception $\bar{a}$). En CSP, elle est symétrique : deux processus qui proposent le même événement doivent le réaliser ensemble.

 

$P \parallel_A Q$

 

Décryptage :

L’opérateur $\parallel_A$ est le parallélisme alphabétisé (alphabetized parallel) de CSP. L’ensemble $A$ contient les événements sur lesquels $P$ et $Q$ doivent se synchroniser. Pour tous les événements hors de $A$, chaque processus avance librement.

Exemple : synchronisation au downbeat

 

Violon = downbeat → do → re → mi → Violon
Piano  = downbeat → fa → sol → Piano
Duo    = Violon ∥ Piano     -- synchronisés sur {downbeat}

 

Les deux instruments jouent en parallèle mais se synchronisent sur le downbeat (le temps fort de la mesure). Entre les downbeats, chacun joue ses notes de manière indépendante. Le violon joue 3 notes par mesure, le piano 2 — c’est une polymétrie 3:2, modélisée naturellement par CSP.

Décryptage :

En musique, le downbeat est le premier temps d’une mesure — le moment où les musiciens se retrouvent. C’est exactement un point de synchronisation au sens de CSP. Entre les downbeats, les voix sont indépendantes ; au downbeat, elles se synchronisent. Le parallélisme alphabétisé de CSP capture ce comportement avec précision.

CCS vs CSP : quel modèle pour la musique ?

Aspect CCS (Milner) CSP (Hoare)
Synchronisation Asymétrique ($a$ / $\bar{a}$) Symétrique (événement partagé)
Modèle plus naturel pour Communication dirigée (client/serveur) Synchronisation mutuelle (musiciens)
Équivalence Bisimulation Raffinement par traces/échecs
Pour la polymétrie $V_1 \mid V_2$ avec restriction $V_1 \parallel_{\text{downbeat}} V_2$

Pour la musique, CSP est souvent plus naturel : les musiciens se synchronisent sur des événements partagés (downbeats, cadences), pas par envoi/réception de messages. Mais CCS offre la bisimulation, un outil d’équivalence plus fin.

La bisimulation : quand deux musiques se comportent pareil

Le problème

Quand peut-on dire que deux systèmes sont équivalents ? La réponse naïve — « quand ils produisent les mêmes séquences d’événements » (équivalence de traces) — est insuffisante.

Rappelons le contre-exemple de L11 :

 

$P = a.(b + c) \qquad Q = (a.b) + (a.c)$

 

Mêmes traces ($\{\langle a,b \rangle, \langle a,c \rangle\}$), mais comportements différents : avec $P$, après $a$, le choix est encore ouvert ; avec $Q$, le choix est fait avant $a$.

La définition

Une bisimulation est une relation $R$ entre processus telle que si $(P, Q) \in R$ :

  1. Si $P$ peut faire $\alpha$ et devenir $P’$, alors $Q$ peut faire $\alpha$ et devenir $Q’$, avec $(P’, Q’) \in R$
  2. Et réciproquement

Deux processus sont bisimilaires ($P \sim Q$) s’il existe une telle relation. C’est plus fin que l’équivalence de traces : la bisimulation prend en compte la structure de branchement à chaque étape.

La bisimulation faible ($P \approx Q$) ignore les actions internes $\tau$. C’est la notion pertinente pour la musique : deux grammaires sont « musicalement équivalentes » si elles produisent les mêmes événements sonores, quelle que soit leur mécanique interne de dérivation.

Décryptage :

Imaginez deux partitions d’apparence très différente qui produisent exactement le même son. Si un auditeur ne peut les distinguer à aucun moment de l’écoute — pas seulement à la fin, mais à chaque instant — elles sont bisimilaires. C’est exactement la bisimulation faible.

Les réseaux de Petri : la concurrence rendue visible

Définition

Un réseau de Petri (Petri Net), introduit par Carl Adam Petri en 1962, est un graphe biparti composé de :

  • Places (cercles $\circ$) : contiennent des jetons (tokens) qui représentent l’état
  • Transitions (rectangles $\square$) : représentent les actions
  • Arcs : relient places et transitions, avec des poids

La règle de tir (firing rule) : une transition tire (s’exécute) quand toutes ses places d’entrée ont suffisamment de jetons. Le tir consomme les jetons d’entrée et produit les jetons de sortie.

Exemple : une mélodie séquentielle

 

graph LR
    p1((●do)) --> t1[t₁] --> p2((ré)) --> t2[t₂] --> p3((mi)) --> t3[t₃] --> p4((fin))

    style p1 fill:#333,color:#fff

 

Les cercles (( )) sont les places, les rectangles [ ] sont les transitions. Le cercle noir ● indique le jeton (la note courante).

Décryptage :

Le jeton ● représente « où on en est dans la mélodie ». Au départ, il est dans $p_1$ (on va jouer do). La transition $t_1$ tire : elle consomme le jeton de $p_1$ (joue do) et en produit un dans $p_2$ (prêt pour ré). Puis $t_2$ tire : ré est joué, le jeton passe en $p_3$. Et ainsi de suite. C’est une exécution séquentielle — pas besoin de réseau de Petri pour ça.

Là où ça devient intéressant : la concurrence

 

graph TD
    p0((● p₀)) --> t1[t₁] & t2[t₂]
    t1 --> p1((p₁)) --> t3[t₃] --> p2((p₂)) --> t4[t₄]
    t2 --> p3((p₃)) --> t5[t₅] --> p4((p₄)) --> t6[t₆]
    t4 & t6 --> psync((p_sync))

    style p0 fill:#333,color:#fff
    style psync fill:#f96,color:#fff

 

Décryptage :

Ici, une seule place de départ ($p_0$) alimente deux branches parallèles. Les transitions $t_1$ et $t_2$ tirent simultanément (si $p_0$ contient au moins 2 jetons et si chaque arc a un poids de 1). La branche gauche ($p_1 \to p_2$) et la branche droite ($p_3 \to p_4$) s’exécutent de manière indépendante. Elles se rejoignent à la place $p_{\text{sync}}$ — un point de synchronisation. C’est exactement ce qui se passe quand deux voix jouent en parallèle et se retrouvent au downbeat.

La polymétrie BP3 comme réseau de Petri

L’expression BP3 {3, do ré mi, fa sol} (3 notes contre 2, compressées en 3 temps) se modélise directement :

 

graph TD
    start((● start)) --> tv1[voice₁] & tv2[voice₂]

    subgraph _sg0["Voix 1 — 3 notes"]
        tv1 --> do((do)) --> tp1[play] --> re((ré)) --> tp2[play] --> mi((mi)) --> tp3[play]
    end

    subgraph _sg1["Voix 2 — 2 notes"]
        tv2 --> fa((fa)) --> tp4[play] --> sol((sol)) --> tp5[play]
    end

    tp3 & tp5 --> db((⬇ downbeat))

    style start fill:#333,color:#fff
    style db fill:#f96,color:#fff

 

La branche gauche a 3 notes, la branche droite 2 — le réseau les exécute en parallèle et les synchronise au downbeat. Pas de sérialisation artificielle, pas d’entrelacement : la concurrence est structurelle, visible dans le graphe lui-même.

Deux formalismes, une même réalité

Complémentarité RdP / algèbres de processus

Les réseaux de Petri et les algèbres de processus (CCS, CSP) modélisent tous deux la concurrence, mais sous des angles différents :

Aspect Algèbres de processus Réseaux de Petri
Point de vue Comportemental (ce qui est observable) Structurel (comment c’est construit)
Concurrence Par entrelacement (interleaving) Vraie concurrence (causalité)
Force Raisonnement formel, preuves d’équivalence Visualisation, analyse structurelle
Équivalence Bisimulation Isomorphisme de graphes
Composition Opérateurs algébriques ($\mid$, $+$, $.$) Fusion de places/transitions

Décryptage :

L’entrelacement (interleaving) est un modèle où « A et B en parallèle » signifie « toutes les séquences possibles en alternant A et B » — par exemple, $a.b$ ou $b.a$. La vraie concurrence (true concurrency) distingue « a et b simultanés » de « a puis b » ou « b puis a ». Les réseaux de Petri capturent la vraie concurrence ; CCS/CSP utilisent l’entrelacement. Pour la musique, la vraie concurrence est plus fidèle : deux notes jouées simultanément ne sont pas « l’une puis l’autre dans un ordre quelconque ».

Nielsen, Plotkin et Winskel (1981) ont montré la correspondance formelle : tout réseau de Petri 1-safe (chaque place contient au plus 1 jeton) peut être encodé en CCS, et réciproquement. Les deux formalismes sont des fenêtres différentes sur le même paysage.

Pour BP3 : deux vues complémentaires

L’expression polymétrique $\{A, B\}$ s’exprime dans les deux cadres :

Formalisme Représentation Force
CCS $A \mid B$ Preuves de bisimulation : « ces deux grammaires sonnent pareil »
CSP $A \parallel_{\text{downbeat}} B$ Synchronisation explicite aux temps forts
Réseau de Petri Deux branches parallèles + place de sync Visualisation de la structure, analyse de vivacité

Les travaux existants

La recherche sur la concurrence en musique se structure en trois lignées principales :

Ross (1995) : MWSCCS — une algèbre de processus musicale

Brian Ross a proposé MWSCCS (Musical Weighted Synchronous CCS), une extension de SCCS (Synchronous CCS de Milner) avec des poids stochastiques. Caractéristiques :

  • Les poids déterminent la probabilité de choix entre alternatives — comme les poids BP3 (voir B1)
  • Les processus musicaux émettent des événements MIDI (I4)
  • La composition verticale (accords, polyphonie) est une composition parallèle $P_1 \mid P_2$
  • La composition horizontale est un séquencement $a.P$

C’est le seul travail qui applique directement une algèbre de processus classique à la composition musicale. Mais il ne traite pas la polymétrie ni les ratios temporels.

L’école italienne : les Music Petri Nets (1986-2018)

Camurri, Haus et Zaccaria ont publié en 1986 le premier article sur les réseaux de Petri appliqués à la musique. Cette lignée a produit plus de 30 ans de travaux continus :

  • Scoresynth (Haus & Sametti, 1991) : système complet de synthèse de partitions combinant réseaux de Petri et algèbre musicale
  • Modélisation du Boléro de Ravel (Haus & Rodriguez, 2011) : étude de cas montrant comment les couches instrumentales et la structure répétitive se modélisent par des réseaux de Petri
  • Formalisation de Schoenberg (Barate et al., 2018) : les règles de composition du Fundamentals of Musical Composition exprimées comme Music Petri Nets

Partitions interactives : les HTSPN (2007-2017)

Allombert, Assayag et Desainte-Catherine ont utilisé les HTSPN (Hierarchical Time Stream Petri Nets) pour modéliser des partitions interactives — des partitions où l’interprète peut modifier les relations temporelles entre objets sonores en temps réel. Les relations d’Allen (before, meets, overlaps, during, starts, finishes, equals) contraignent les structures temporelles.

Toro et al. (2014) ont construit un pont explicite entre réseaux de Petri et algèbres de processus via le calcul ntcc (non-deterministic timed concurrent constraint). Leur observation clé : « les réseaux de Petri modélisent bien les relations temporelles locales, mais représentent difficilement les contraintes globales — ce que les calculs de processus gèrent mieux. »

Ce qui manque — et pourquoi BP3 est intéressant

Malgré ces travaux, trois lacunes subsistent :

  1. Aucune application directe de CCS/CSP à la polymétrie. Ross traite la stochasticité, pas les ratios temporels. L’école italienne utilise les réseaux de Petri, pas les algèbres de processus.
  1. Pas de formalisation de BP3 comme système concurrent. L’expression $\{v_1, v_2\}$ n’a jamais été formellement traduite en composition parallèle CCS/CSP. Or, c’est exactement ce qu’elle fait : exécuter deux voix en parallèle avec synchronisation.
  1. Pas de pont systématique RdP ↔ algèbres de processus pour la musique. Toro le fait via ntcc, mais pas via CCS/CSP classiques.

Ces lacunes constituent une opportunité de contribution : formaliser la polymétrie BP3 dans les deux cadres (algèbres de processus et réseaux de Petri), montrer leur complémentarité, et ouvrir la voie à l’analyse formelle des propriétés des grammaires polymétriques (vivacité, équivalence, synchronisation).

Ce qu’il faut retenir

  1. CCS (Milner, 1980) modélise la concurrence avec des processus qui communiquent par actions complémentaires ($a$ / $\bar{a}$). La règle de communication produit une synchronisation invisible ($\tau$).
  2. CSP (Hoare, 1985) synchronise par événements partagés — plus naturel pour la musique où les musiciens se retrouvent sur les temps forts, pas par envoi/réception de messages.
  3. La bisimulation est le bon critère d’équivalence entre processus : plus fin que les traces, il capture la structure de branchement. Deux grammaires musicales sont « équivalentes » si elles sont faiblement bisimilaires ($P \approx Q$).
  4. Les réseaux de Petri (Petri, 1962) sont un formalisme graphique pour la concurrence : des places (états), des transitions (actions), des jetons (ressources), des arcs (flux). La concurrence est visible dans la structure du graphe.
  5. RdP et algèbres de processus sont complémentaires : les RdP montrent la structure (vraie concurrence), les algèbres de processus permettent le raisonnement formel (bisimulation). Nielsen, Plotkin et Winskel (1981) ont prouvé leur équivalence pour les réseaux 1-safe.
  6. La polymétrie BP3 $\{v_1, v_2\}$ est une composition parallèle : en CSP, c’est $v_1 \parallel_{\text{downbeat}} v_2$ ; en réseau de Petri, ce sont deux branches parallèles avec une place de synchronisation. Aucun travail existant ne formalise cette correspondance.
  7. Trois lignées de recherche existent : Ross/MWSCCS (algèbre de processus pour la composition stochastique), l’école italienne (Music Petri Nets), et les partitions interactives (HTSPN). Aucune ne traite la polymétrie formellement.

Pour aller plus loin

  • Milner, R. (1989). Communication and Concurrency. Prentice Hall. — La référence sur le CCS et la bisimulation. Le chapitre sur la composition parallèle est directement applicable à la polymétrie.
  • Hoare, C. A. R. (1985). Communicating Sequential Processes. Prentice Hall. — Le texte fondateur du CSP, disponible gratuitement en ligne. Le parallélisme alphabétisé est le bon modèle pour la synchronisation musicale.
  • Petri, C. A. (1962). Kommunikation mit Automaten. Thèse de doctorat, Université de Bonn. — L’article fondateur des réseaux de Petri. Écrit en allemand, mais les idées sont devenues universelles.
  • Murata, T. (1989). « Petri nets: Properties, analysis and applications. » Proceedings of the IEEE, 77(4). — Le survey de référence, couvrant toutes les propriétés formelles.
  • Ross, B. J. (1995). « A Process Algebra for Stochastic Music Composition. » ICMC 1995. — L’unique application directe d’une algèbre de processus à la composition musicale.
  • Barate, A., Haus, G., & Ludovico, L. A. (2005). « Music Analysis and Modeling Through Petri Nets. » LNCS 3902. — Introduction des Music Petri Nets comme formalisme dédié à la musique.
  • Allombert, A., Assayag, G., & Desainte-Catherine, M. (2007). « A System of Interactive Scores Based on Petri Nets. » SMC 2007. — Les HTSPN pour les partitions interactives.
  • Toro, M., Desainte-Catherine, M., & Rueda, C. (2014). « Formal Semantics for Interactive Music Scores. » J. Mathematics and Music, 8(2). — Le pont formel entre réseaux de Petri et calculs de processus pour la musique.
  • Nielsen, M., Plotkin, G., & Winskel, G. (1981). « Petri nets, event structures and domains, part I. » Theoretical Computer Science, 13(1). — La correspondance formelle entre réseaux de Petri et CCS.

Glossaire

  • Action (CCS) : événement observable qu’un processus peut effectuer. Trois types : action $a$, co-action $\bar{a}$, action interne $\tau$.
  • Bisimulation : relation $R$ entre deux processus telle qu’à chaque étape, toute action de l’un peut être imitée par l’autre, et réciproquement. Forte ($P \sim Q$) ou faible ($P \approx Q$). Plus fine que l’équivalence de traces.
  • CCS (Calculus of Communicating Systems) : algèbre de processus introduite par Robin Milner (1980). Opérateurs : préfixe $a.P$, choix $P + Q$, parallèle $P \mid Q$, restriction $P \setminus \{a\}$.
  • Composition parallèle : opérateur $P \mid Q$ (CCS) ou $P \parallel_A Q$ (CSP) qui exécute deux processus simultanément.
  • CSP (Communicating Sequential Processes) : algèbre de processus de Tony Hoare (1985). Synchronisation par événements partagés, avec trois modèles sémantiques (traces, échecs, échecs-divergences).
  • Downbeat : premier temps d’une mesure — le point de synchronisation naturel entre voix musicales.
  • Entrelacement (interleaving) : modèle de concurrence où « A et B en parallèle » signifie « toutes les séquences possibles en alternant des actions de A et B ». Utilisé par CCS/CSP.
  • HTSPN (Hierarchical Time Stream Petri Nets) : extension hiérarchique des réseaux de Petri temporisés, utilisée pour les partitions interactives (Senac 1995, Allombert 2007).
  • Jeton (token) : marqueur dans une place d’un réseau de Petri. Représente une ressource, un état, ou une position dans l’exécution.
  • LTS (Labeled Transition System) : triplet $(S, \text{Act}, \to)$ — états, actions, transitions. Le modèle sous-jacent de CCS.
  • Marquage (marking) : distribution des jetons dans les places d’un réseau de Petri. Représente l’état global du système à un instant donné.
  • Music Petri Net : extension des réseaux de Petri adaptée à la description musicale (Barate, Haus, Ludovico, 2005).
  • MWSCCS (Musical Weighted Synchronous CCS) : extension de SCCS avec poids stochastiques pour la composition musicale (Ross, 1995).
  • Place : nœud circulaire d’un réseau de Petri, contenant des jetons. Représente un état ou une condition.
  • Polymétrie : superposition de mètres différents — par exemple, 3 notes contre 2 dans la même durée. En BP3, notée $\{v_1, v_2\}$.
  • Réseau de Petri : formalisme graphique (places, transitions, arcs, jetons) pour modéliser les systèmes concurrents. Inventé par Carl Adam Petri (1962).
  • Transition : nœud rectangulaire d’un réseau de Petri. Représente une action. Tire quand toutes ses places d’entrée ont suffisamment de jetons.
  • Vraie concurrence (true concurrency) : modèle de concurrence qui distingue « A et B simultanés » de « A puis B » ou « B puis A ». Capturé par les réseaux de Petri.
  • $\tau$ (tau) : action interne en CCS, invisible de l’extérieur. Résulte de la synchronisation entre une action et sa co-action.

Prérequis : Les trois sémantiques, MCSL, Au-delà des trois sémantiques
Temps de lecture : 15 min
Tags : #CCS #CSP #bisimulation #réseaux-de-Petri #concurrence #polymétrie #algèbre-de-processus

Article précédent : L11) Au-delà des trois sémantiques
Série L : cet article clôt la série des fondements théoriques. Pour l’application à BP3, voir la série B.