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


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

  author =	 {Leifer, James and Milner, Robin},
  title = 	 {{Shallow linear action graphs and their embeddings}},
  year = 	 2000,
  month = 	 oct,
  url = 	 {},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-508},
  number = 	 {UCAM-CL-TR-508}