Skip to main content

Pattern matching and bisimulation


Thomas Given-Wilson and Daniele Gorla


University of Rome "La Sapienza"


Concurrent Pattern Calculus (CPC) is a minimal calculus whose communication mechanism is based on a powerful form of symmetric pattern unification. CPC's behavioural theory can be developed in the usual manner, by defining a barbed congruence and then capturing this via a labelled bisimulation based equivalence. However, the richness of patterns and their unification entails some flexibility in the challenge-reply game that underpins bisimulation. This leads to an ordering upon patterns that is used to define the valid replies to a given challenge. Such a theory can be smoothly adapted to accomplish other, less symmetric, forms of pattern matching (e.g. those of Linda, polyadic pi-calculus, and pi-calculus with polyadic synchronization) without compromising the coincidence of the two equivalences.

BibTeX Entry

    author           = {Given-Wilson, Thomas and Gorla, Daniele},
    month            = jun,
    year             = {2013},
    keywords         = {pattern matching, unification, bisimulation, symmetric matching},
    address          = {Firenze, Italy},
    title            = {Pattern Matching and Bisimulation},
    pages            = {15},
    booktitle        = {15th International Conference on Coordination Models and Languages},
    paperurl         = {}


Served by Apache on Linux on seL4.