| Title | Concurrency and Probability: Removing Confusion, Compositionally |
| Publication Type | Conference Paper |
| Year of Publication | 2018 |
| Authors | Bruni, Roberto, Melgratti, Hernán, Montanari, Ugo |
| Conference Name | Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science |
| Publisher | ACM |
| Conference Location | New York, NY, USA |
| ISBN Number | 978-1-4503-5583-4 |
| Keywords | Computing Theory and Compositionality, Confusion, dynamic nets, Human Behavior, human factors, OR causality, persistent places, Petri nets, pubcrawl |
| Abstract | Assigning a satisfactory truly concurrent semantics to Petri nets with confusion and distributed decisions is a long standing problem, especially if one wants to resolve decisions by drawing from some probability distribution. Here we propose a general solution based on a recursive, static decomposition of (occurrence) nets in loci of decision, called structural branching cells (s-cells). Each s-cell exposes a set of alternatives, called transactions. Our solution transforms a given Petri net into another net whose transitions are the transactions of the s-cells and whose places are those of the original net, with some auxiliary structure for bookkeeping. The resulting net is confusion-free, and thus conflicting alternatives can be equipped with probabilistic choices, while nonintersecting alternatives are purely concurrent and their probability distributions are independent. The validity of the construction is witnessed by a tight correspondence with the recursively stopped configurations of Abbes and Benveniste. Some advantages of our approach are that: i) s-cells are defined statically and locally in a compositional way; ii) our resulting nets faithfully account for concurrency. |
| URL | http://doi.acm.org/10.1145/3209108.3209202 |
| DOI | 10.1145/3209108.3209202 |
| Citation Key | bruni_concurrency_2018 |
Concurrency and Probability: Removing Confusion, Compositionally