Colored Petri Nets

Colored Petri Nets (CPNs) are an extension of ordinary Petri nets in which tokens carry data values — called colors or token colors — allowing a single net to model systems with typed, structured data. Developed by Kurt Jensen at Aarhus University starting in the late 1970s, colored Petri nets combine the concurrency semantics of Petri nets with the data-manipulation capabilities of functional programming languages (typically Standard ML). In a CPN, a place is typed with a color set, and a token in that place is a value of that type. Arc expressions and guard conditions on transitions can inspect and manipulate these values, making CPNs expressive enough to model communication protocols, distributed algorithms, and embedded systems at a level of detail that plain Petri nets cannot achieve. CPNs are supported by industrial-strength tools like CPN Tools and have been standardized in ISO/IEC 15909.

_The addition of data to Petri nets was both necessary and dangerous. Necessary, because real systems manipulate data and no formalism that ignores data can be used for engineering. Dangerous, because the introduction of colored tokens and arc expressions reintroduces the very complexity that Petri nets were designed to tame. A CPN with sufficiently rich color sets and arc expressions is Turing-complete — it can simulate any Turing machine — and therefore loses the decidability properties that make ordinary Petri nets attractive for verification. The color is a Trojan horse: it brings expressiveness, but it smuggles in undecidability. The engineer who treats a CPN as 'just a Petri net with data' has forgotten that data is never just data. It is computation in disguise._