In this paper we recast the classical Darondeau–Degano’s causal semantics of concurrency in a coalgebraic setting, where we derive a compact model. Our construction is inspired by the one of Montanari and Pistore yielding causal automata, but we show that it is instance of an existing categorical framework for modeling the semantics of nominal calculi, whose relevance is further demonstrated. The key idea is to represent events as names, and the occurrence of a new event as name generation. We model causal semantics as a coalgebra over a presheaf, along the lines of the Fiore–Turi approach to the semantics of nominal calculi. More specifically, we take a suitable category of finite posets, representing causal relations over events, and we equip it with an endofunctor that allocates new events and relates them to their causes. Presheaves over this category express the relationship between processes and causal relations among the processes’ events. We use the allocation operator to define a category of well-behaved coalgebras: it models the occurrence of a new event along each transition. Then we turn the causal transition relation into a coalgebra in this category, where labels only exhibit maximal events with respect to the source states’ poset, and we show that its bisimilarity is essentially Darondeau–Degano’s strong causal bisimilarity. This coalgebra is still infinite-state, but we exploit the equivalence between coalgebras over a class of presheaves and History Dependent automata to derive a compact representation, where states only retain the poset of the most recent events for each atomic subprocess, and are isomorphic up to order-preserving permutations. Remarkably, this reduction of states is automatically performed along the equivalence.
|Autori interni:||BRUNI, ROBERTO|
MONTANARI, UGO GIOVANNI ERASMO
|Autori:||Bruni R.; Montanari U.; Sammartino M.|
|Titolo:||Revisiting causality, coalgebraically|
|Anno del prodotto:||2014|
|Digital Object Identifier (DOI):||10.1007/s00236-014-0207-9|
|Appare nelle tipologie:||1.1 Articolo in rivista|