Department of Computer Science and Technology

Technical reports

Shallow linear action graphs and their embeddings

James Leifer, Robin Milner

October 2000, 16 pages

DOI: 10.48456/tr-508

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 = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-508.ps.gz},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-508},
  number = 	 {UCAM-CL-TR-508}
}