Technical reports

# Shallow linear action graphs and their embeddings

**James Leifer, Robin Milner**

October 2000, 16 pages

## Abstract

In previous work, action calculus has been presented in terms of action graphs. Many calculi, or at least their salient features, can be expressed as specific action calculi; examples are Petri nets, λ-calculus, π-calculus, fusion calculus, ambient calculus and spi calculus.

We here offer linear action graphs as a primitive basis for action calculi. Linear action graphs have a simpler theory than the non-linear variety. This paper presents the category of embeddings of shallow linear action graphs (those without nesting), using a novel form of graphical reasoning which simplifies some otherwise complex manipulations in regular algebra. The work is done for undirected graphs, and adapted in a few lines to directed graphs.

The graphical reasoning used here will be applied in future work to develop behavioural congruences for action calculi.

## Full text

PS (0.1 MB)

## BibTeX record

@TechReport{UCAM-CL-TR-508, author = {Leifer, James and Milner, Robin}, title = {{Shallow linear action graphs and their embeddings}}, year = 2000, month = oct, url = {http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-508.ps.gz}, institution = {University of Cambridge, Computer Laboratory}, number = {UCAM-CL-TR-508} }