Technical reports
Shallow linear action graphs and their embeddings
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} }