L12) Petri Nets and Process Algebras

Modeling Concurrency in Music

In L11, we discovered process semantics: the idea that the meaning of a system lies in its interactions, not in its isolated computation. We had briefly seen CCS and CSP as tools for modeling concurrency. It’s time to go further — and encounter a formalism of remarkable visual elegance: Petri nets. Together, these tools allow us to formalize what music has always done: superimposing independent voices that synchronize.

Where does this article fit in?

This article concludes the L series by addressing concurrency models — the top floor of the formalisms map (cf. L0).

L5 introduced three semantics (operational, denotational, axiomatic)
L6–L8 explored them one by one
L9 explored mildly context-sensitive languages (MCSL), beyond Chomsky
L10 added attribute grammars — dynamic control via flags
L11 opened three new semantics, including process semantics (CCS, CSP, bisimulation)

L12 takes over from L11 on process semantics and adds Petri nets — a complementary graphical formalism. The objective is twofold: to rigorously formalize these tools, and to show that they are the natural framework for discussing polymetry.

Why is this important?

Music is a concurrent system by nature. A symphony orchestra is 80 parallel processes (the musicians) synchronizing via a communication channel (the conductor). A jazz duo is two processes interacting in real-time, each reacting to the other. Polymetry (see M5) — several superimposed meters — is the purest expression of this concurrency.

It’s no coincidence that BP3 (I2) was designed for Indian music, where polymetry is omnipresent: a tablist playing a rhythmic cycle of 7 beats (tāl rūpak) against a melodic cycle of 16 beats (tīntāl) is parallel composition with synchronization at the sam (the common strong beat). The $\{v_1, v_2\}$ mechanism of BP3 (B5) precisely formalizes this superposition of independent temporal flows.

Yet, most musical formalisms treat music sequentially: one note after another, one voice at a time. Context-free grammars (L2) produce trees — which are hierarchical structures, not parallel structures. To capture what happens when two voices play simultaneously, tools designed for concurrency are needed.

The idea in one sentence

Process algebras (CCS, CSP) and Petri nets are two complementary facets of the same problem: modeling independent entities that synchronize — exactly what voices do in a polymetric piece.

CCS: The Calculus of Communicating Systems

The basic building blocks

CCS (Calculus of Communicating Systems), created by Robin Milner in 1980, models concurrent systems with a minimal syntax:

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

Operator	Notation	Meaning
Inactive process	$\mathbf{0}$	Terminated — does nothing more
Prefix	$$a.P$$	Perform action $$a$$ , then continue as $$P$$
Choice	$$P_1 + P_2$$	Behave as $$P_1$$ or $$P_2$$
Parallel	$P_1 \mid P_2$	$$P_1$$ and $$P_2$$ simultaneously
Restriction	$P \setminus \{a\}$	Action $$a$$ is private (internal)

Deciphering:

The dot « $$.$$ » means “then” (sequencing). The bar « $\mid$ » means “at the same time” (parallelism). The « $$+$$ » means “or” (choice). With these three operators, all possible concurrent behaviors can be constructed.

Actions are of three types:

$$a$$ : an observable action (send a signal on channel $$a$$ )
$\bar{a}$ (a bar): the co-action (receive on channel $$a$$ )
$\tau$ (tau): an internal action, invisible from the outside — it results from a synchronization

The communication rule

When two parallel processes perform complementary actions ( $$a$$ and $\bar{a}$ ), they synchronize:

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

Deciphering:

This is an SOS (Structural Operational Semantics, see L6) rule. It states: if $$P$$ can send on $$a$$ and $$Q$$ can receive on $$a$$ , then the two processes synchronize, and the resulting action is $\tau$ — invisible from the outside. This is a private rendezvous between $$P$$ and $$Q$$ .

Example: two musicians

Violin  = play_c . play_d . play_e . 0
Piano   = play_f . play_g . 0
Duo     = Violin | Piano

The violin plays three notes, the piano plays two — in parallel, without synchronization. This is exactly free concurrency: each progresses at its own pace.

CSP: Synchronization by Shared Events

The difference with CCS

Hoare’s CSP (Communicating Sequential Processes) (1985) adopts a different synchronization mechanism. In CCS, synchronization is asymmetric (send $$a$$ / receive $\bar{a}$ ). In CSP, it is symmetric: two processes that propose the same event must perform it together.

P \parallel_A Q

Deciphering:

The operator $\parallel_A$ is CSP’s alphabetized parallel. The set $$A$$ contains the events on which $$P$$ and $$Q$$ must synchronize. For all events outside $$A$$ , each process progresses freely.

Example: synchronization on the downbeat

Violin = downbeat → c → d → e → Violin
Piano  = downbeat → f → g → Piano
Duo    = Violin ∥ Piano     -- synchronized on {downbeat}

The two instruments play in parallel but synchronize on the downbeat (the strong beat of the measure). Between downbeats, each plays its notes independently. The violin plays 3 notes per measure, the piano 2 — this is a 3:2 polymetry, naturally modeled by CSP.

Deciphering:

In music, the downbeat is the first beat of a measure — the moment when musicians meet. This is exactly a synchronization point in the sense of CSP. Between downbeats, the voices are independent; at the downbeat, they synchronize. CSP’s alphabetized parallelism captures this behavior precisely.

CCS vs CSP: which model for music?

Aspect	CCS (Milner)	CSP (Hoare)
Synchronization	Asymmetric ( $$a$$ / $\bar{a}$ )	Symmetric (shared event)
More natural model for	Directed communication (client/server)	Mutual synchronization (musicians)
Equivalence	Bisimulation	Refinement by traces/failures
For polymetry	$V_1 \mid V_2$ with restriction	$V_1 \parallel_{\text{downbeat}} V_2$

For music, CSP is often more natural: musicians synchronize on shared events (downbeats, cadences), not by sending/receiving messages. But CCS offers bisimulation, a finer equivalence tool.

Bisimulation: when two pieces of music behave the same way

The problem

When can we say that two systems are equivalent? The naive answer — “when they produce the same sequences of events” (trace equivalence) — is insufficient.

Let’s recall the counter-example from L11:

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

Same traces ( $\{\langle a,b \rangle, \langle a,c \rangle\}$ ), but different behaviors: with $$P$$ , after $$a$$ , the choice is still open; with $$Q$$ , the choice is made before $$a$$ .

The definition

A bisimulation is a relation $$R$$ between processes such that if $(P, Q) \in R$ :

If $$P$$ can perform $\alpha$ and become $$P’$$ , then $$Q$$ can perform $\alpha$ and become $$Q’$$ , with $(P’, Q’) \in R$
And vice versa

Two processes are bisimilar ( $P \sim Q$ ) if such a relation exists. This is finer than trace equivalence: bisimulation takes into account the branching structure at each step.

Weak bisimulation ( $P \approx Q$ ) ignores internal $\tau$ actions. This is the relevant notion for music: two grammars are “musically equivalent” if they produce the same sound events, regardless of their internal derivation mechanics.

Deciphering:

Imagine two scores that look very different but produce exactly the same sound. If a listener cannot distinguish them at any point during the listening — not just at the end, but at every moment — they are bisimilar. This is exactly weak bisimulation.

Petri Nets: Concurrency Made Visible

Definition

A Petri net, introduced by Carl Adam Petri in 1962, is a bipartite graph composed of:

Places (circles $\circ$ ): contain tokens that represent the state
Transitions (rectangles $\square$ ): represent actions
Arcs: connect places and transitions, with weights

The firing rule: a transition fires (executes) when all its input places have enough tokens. Firing consumes input tokens and produces output tokens.

Example: a sequential melody

graph LR
    p1((●c)) --> t1[t₁] --> p2((d)) --> t2[t₂] --> p3((e)) --> t3[t₃] --> p4((end))

    style p1 fill:#333,color:#fff

The circles (( )) are the places, the rectangles [ ] are the transitions. The black circle ● indicates the token (the current note).

Deciphering:

The token ● represents “where we are in the melody”. Initially, it is in $$p_1$$ (we are about to play c). Transition $$t_1$$ fires: it consumes the token from $$p_1$$ (plays c) and produces one in $$p_2$$ (ready for d). Then $$t_2$$ fires: d is played, the token moves to $$p_3$$ . And so on. This is a sequential execution — no need for a Petri net for that.

Where it gets interesting: concurrency

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

Deciphering:

Here, a single starting place ( $$p_0$$ ) feeds two parallel branches. Transitions $$t_1$$ and $$t_2$$ fire simultaneously (if $$p_0$$ contains at least 2 tokens and if each arc has a weight of 1). The left branch ( $p_1 \to p_2$ ) and the right branch ( $p_3 \to p_4$ ) execute independently. They converge at place $p_{\text{sync}}$ — a synchronization point. This is exactly what happens when two voices play in parallel and meet at the downbeat.

BP3 polymetry as a Petri net

The BP3 expression {3, c d e, f g} (3 notes against 2, compressed into 3 beats) can be modeled directly:

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

    subgraph _sg0["Voice 1 — 3 notes"]
        tv1 --> c((c)) --> tp1[play] --> d((d)) --> tp2[play] --> e((e)) --> tp3[play]
    end

    subgraph _sg1["Voice 2 — 2 notes"]
        tv2 --> f((f)) --> tp4[play] --> g((g)) --> tp5[play]
    end

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

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

The left branch has 3 notes, the right branch 2 — the net executes them in parallel and synchronizes them at the downbeat. No artificial serialization, no interleaving: concurrency is structural, visible in the graph itself.

Two Formalisms, One Reality

Complementarity of Petri Nets / Process Algebras

Petri nets and process algebras (CCS, CSP) both model concurrency, but from different angles:

Aspect	Process Algebras	Petri Nets
Perspective	Behavioral (what is observable)	Structural (how it is built)
Concurrency	By interleaving	True concurrency (causality)
Strength	Formal reasoning, equivalence proofs	Visualization, structural analysis
Equivalence	Bisimulation	Graph isomorphism
Composition	Algebraic operators ( $\mid$ , $$+$$ , $$.$$ )	Merging of places/transitions

Deciphering:

Interleaving is a model where “A and B in parallel” means “all possible sequences by alternating A and B” — for example, $$a.b$$ or $$b.a$$ . True concurrency distinguishes “a and b simultaneous” from “a then b” or “b then a”. Petri nets capture true concurrency; CCS/CSP use interleaving. For music, true concurrency is more faithful: two notes played simultaneously are not “one then the other in any order”.

Nielsen, Plotkin, and Winskel (1981) showed the formal correspondence: any 1-safe Petri net (each place contains at most 1 token) can be encoded in CCS, and vice versa. The two formalisms are different windows onto the same landscape.

For BP3: two complementary views

The polymetric expression $\{A, B\}$ is expressed in both frameworks:

Formalism	Representation	Strength
CCS	$A \mid B$	Bisimulation proofs: “these two grammars sound the same”
CSP	$A \parallel_{\text{downbeat}} B$	Explicit synchronization at strong beats
Petri Net	Two parallel branches + sync place	Visualization of structure, liveness analysis

Existing Work

Research on concurrency in music is structured into three main lines:

Ross (1995): MWSCCS — a musical process algebra

Brian Ross proposed MWSCCS (Musical Weighted Synchronous CCS), an extension of SCCS (Synchronous CCS by Milner) with stochastic weights. Characteristics:

Weights determine the probability of choice between alternatives — like BP3 weights (see B1)
Musical processes emit MIDI events (I4)
Vertical composition (chords, polyphony) is a parallel composition $P_1 \mid P_2$
Horizontal composition is a sequencing $$a.P$$

This is the only work that directly applies a classical process algebra to musical composition. But it does not address polymetry or temporal ratios.

The Italian School: Music Petri Nets (1986-2018)

Camurri, Haus, and Zaccaria published the first article on Petri nets applied to music in 1986. This lineage has produced over 30 years of continuous work:

Scoresynth (Haus & Sametti, 1991): a complete score synthesis system combining Petri nets and musical algebra
Modeling Ravel’s Boléro (Haus & Rodriguez, 2011): a case study showing how instrumental layers and repetitive structure are modeled by Petri nets
Formalization of Schoenberg (Barate et al., 2018): the compositional rules from Fundamentals of Musical Composition expressed as Music Petri Nets

Interactive Scores: HTSPN (2007-2017)

Allombert, Assayag, and Desainte-Catherine used HTSPN (Hierarchical Time Stream Petri Nets) to model interactive scores — scores where the performer can modify temporal relationships between sound objects in real-time. Allen’s relations (before, meets, overlaps, during, starts, finishes, equals) constrain temporal structures.

Toro et al. (2014) built an explicit bridge between Petri nets and process algebras via the ntcc (non-deterministic timed concurrent constraint) calculus. Their key observation: “Petri nets model local temporal relationships well, but struggle to represent global constraints — which process calculi handle better.”

What’s Missing — and Why BP3 is Interesting

Despite this work, three gaps remain:

No direct application of CCS/CSP to polymetry. Ross deals with stochasticity, not temporal ratios. The Italian school uses Petri nets, not process algebras.

No formalization of BP3 as a concurrent system. The expression $\{v_1, v_2\}$ has never been formally translated into CCS/CSP parallel composition. Yet, this is exactly what it does: execute two voices in parallel with synchronization.

No systematic bridge between Petri Nets ↔ process algebras for music. Toro does it via ntcc, but not via classical CCS/CSP.

These gaps represent an opportunity for contribution: to formalize BP3 polymetry within both frameworks (process algebras and Petri nets), demonstrate their complementarity, and pave the way for formal analysis of the properties of polymetric grammars (liveness, equivalence, synchronization).

Key Takeaways

CCS (Milner, 1980) models concurrency with processes that communicate via complementary actions ( $$a$$ / $\bar{a}$ ). The communication rule produces an invisible synchronization ( $\tau$ ).
CSP (Hoare, 1985) synchronizes via shared events — more natural for music where musicians meet on strong beats, not by sending/receiving messages.
Bisimulation is the correct criterion for equivalence between processes: finer than traces, it captures the branching structure. Two musical grammars are “equivalent” if they are weakly bisimilar ( $P \approx Q$ ).
Petri nets (Petri, 1962) are a graphical formalism for concurrency: places (states), transitions (actions), tokens (resources), arcs (flow). Concurrency is visible in the graph’s structure.
Petri Nets and process algebras are complementary: Petri Nets show the structure (true concurrency), process algebras allow for formal reasoning (bisimulation). Nielsen, Plotkin, and Winskel (1981) proved their equivalence for 1-safe nets.
BP3 polymetry $\{v_1, v_2\}$ is a parallel composition: in CSP, it is $v_1 \parallel_{\text{downbeat}} v_2$ ; in a Petri net, it consists of two parallel branches with a synchronization place. No existing work formalizes this correspondence.
Three lines of research exist: Ross/MWSCCS (process algebra for stochastic composition), the Italian school (Music Petri Nets), and interactive scores (HTSPN). None formally address polymetry.

Glossary

Action (CCS): an observable event that a process can perform. Three types: action $$a$$ , co-action $\bar{a}$ , internal action $\tau$ .
Bisimulation: a relation $$R$$ between two processes such that at each step, any action of one can be mimicked by the other, and vice versa. Strong ( $P \sim Q$ ) or weak ( $P \approx Q$ ). Finer than trace equivalence.
CCS (Calculus of Communicating Systems): a process algebra introduced by Robin Milner (1980). Operators: prefix $$a.P$$ , choice $$P + Q$$ , parallel $P \mid Q$ , restriction $P \setminus \{a\}$ .
Parallel composition: operator $P \mid Q$ (CCS) or $P \parallel_A Q$ (CSP) that executes two processes simultaneously.
CSP (Communicating Sequential Processes): a process algebra by Tony Hoare (1985). Synchronization by shared events, with three semantic models (traces, failures, failures-divergences).
Downbeat: the first beat of a measure — the natural synchronization point between musical voices.
Interleaving: a concurrency model where “A and B in parallel” means “all possible sequences by alternating actions of A and B”. Used by CCS/CSP.
HTSPN (Hierarchical Time Stream Petri Nets): a hierarchical extension of timed Petri nets, used for interactive scores (Senac 1995, Allombert 2007).
Token: a marker in a place of a Petri net. Represents a resource, a state, or a position in the execution.
LTS (Labeled Transition System): a triplet $(S, \text{Act}, \to)$ — states, actions, transitions. The underlying model of CCS.
Marking: the distribution of tokens in the places of a Petri net. Represents the global state of the system at a given time.
Music Petri Net: an extension of Petri nets adapted for musical description (Barate, Haus, Ludovico, 2005).
MWSCCS (Musical Weighted Synchronous CCS): an extension of SCCS with stochastic weights for musical composition (Ross, 1995).
Place: a circular node in a Petri net, containing tokens. Represents a state or a condition.
Polymetry: superposition of different meters — for example, 3 notes against 2 in the same duration. In BP3, denoted $\{v_1, v_2\}$ .
Petri Net: a graphical formalism (places, transitions, arcs, tokens) for modeling concurrent systems. Invented by Carl Adam Petri (1962).
Transition: a rectangular node in a Petri net. Represents an action. Fires when all its input places have enough tokens.
True concurrency: a concurrency model that distinguishes “A and B simultaneous” from “A then B” or “B then A”. Captured by Petri nets.
$\tau$ (tau): an internal action in CCS, invisible from the outside. Results from synchronization between an action and its co-action.

Prerequisites: L5, L9, L11
Reading time: 15 min
Tags: #CCS #CSP #bisimulation #petri-nets #concurrency #polymetry #process-algebra

Previous article: L11
Series L: this article concludes the series on theoretical foundations. For application to BP3, see series B.