Graph rewriting for the π-calculus
- 1 June 2007
- journal article
- research article
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 17 (3) , 407-437
Abstract
We propose a graphical implementation for (possibly recursive) processes of the π-calculus, encoding each process into a graph. Our implementation is sound and complete with respect to the structural congruence for the calculus: two processes are equivalent if and only if they are mapped into graphs with the same normal form. Most importantly, the encoding allows the use of standard graph rewriting mechanisms for modelling the reduction semantics of the calculus.Keywords
This publication has 31 references indexed in Scilit:
- Graphical Verification of a Spatial Logic for the π-calculusElectronic Notes in Theoretical Computer Science, 2006
- Normal forms for algebras of connectionsTheoretical Computer Science, 2002
- Comparing logics for rewriting: rewriting logic, action calculi and tile logicTheoretical Computer Science, 2002
- Rewriting on cyclic structures: Equivalence between the operational and the categorical descriptionRAIRO - Theoretical Informatics and Applications, 1999
- A Bi-Categorical Axiomatisation of Concurrent Graph RewritingElectronic Notes in Theoretical Computer Science, 1999
- Graph notation for concurrent combinators1995
- An abstract machine for concurrent modular systems: CHARMTheoretical Computer Science, 1994
- Order-sorted algebra I: equational deduction for multiple inheritance, overloading, exceptions and partial operationsTheoretical Computer Science, 1992
- A general result on abstract flowchart schemes with applications to the study of accessibility, reduction and minimizationTheoretical Computer Science, 1992
- The chemical abstract machineTheoretical Computer Science, 1992