Shallow Linear Action Graphs and their Embeddings

James J. Leifer, Robin Milner

Research output: Contribution to journalArticlepeer-review


Action calculi, which generalise process calculi such as Petri nets, π-calculusand ambient calculus, have been presented in terms of action graphs. We here offer linear action graphs as a primitive basis for action calculi. This paper presents the category of embeddings of undirected linear action graphs without nesting, using a novel form of graphical reasoning which simplifies some otherwise complex manipulations in regular algebra. The results are adapted in a few lines to directed graphs. This work is part of a long-term search for a uniform behavioural theory for process calculi.
Original languageEnglish
Pages (from-to)327-340
Number of pages14
JournalFormal Aspects of Computing
Issue number3-5
Publication statusPublished - 2002


Dive into the research topics of 'Shallow Linear Action Graphs and their Embeddings'. Together they form a unique fingerprint.

Cite this