Decomposing Monolithic Processes in a Process Algebra with Multi-actions

Maurice Laveaux
Tim A.C. Willemse

A monolithic process is a single recursive equation with data parameters, which only uses non-determinism, action prefixing, and recursion. We present a technique that decomposes such a monolithic process into multiple processes where each process defines behaviour for a subset of the parameters of the monolithic process. For this decomposition we can show that a composition of these processes is strongly bisimilar to the monolithic process under a suitable synchronisation context. Minimising the resulting processes before determining their composition can be used to derive a state space that is smaller than the one obtained by a monolithic exploration. We apply the decomposition technique to several specifications to show that this works in practice. Finally, we prove that state invariants can be used to further improve the effectiveness of this decomposition technique.

In Julien Lange, Anastasia Mavridou, Larisa Safina and Alceste Scalas: Proceedings 14th Interaction and Concurrency Experience (ICE 2021), Online, 18th June 2021, Electronic Proceedings in Theoretical Computer Science 347, pp. 57–76.
This is a peer reviewed version of https://arxiv.org/abs/2012.06468 [cs.LO]. This revision contains more examples but omits proofs.
Published: 2nd October 2021.

ArXived at: https://dx.doi.org/10.4204/EPTCS.347.4 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org