Reduction of states. Only immediate causes of atomic subprocesses are kept, i.e., events that are maximal in the ordering with respect to at least one of the subprocesses. Intuitively, we keep causes for the most recent transitions. Then states are identified up to a suitable order-preserving notion of isomorphism, and transitions are enriched with maps that keep track of the original identity of events. At each step we prove that behavioral equivalences are preserved. P→ Then we recast this construction in a categorical setting, where it becomes much more natural and simple. The key idea is to represent events as names, and the occurrence of a new event as name generation. This allows us to give a presheaf-based coalgebraic representation of causal semantics, along the lines of the Xxxxx-Xxxx approach to the semantics of nominal calculi [FT01]. In particular, we represent causal relations as a category Pm of partial orders over event names and suitable maps between them, and we equip it with an event allocation operator δ: Pm Pm that allocates new events and relates them to their causes in the partial order. Presheaves Set m express the association between causal processes and causal relations among the processes’ events. We define a category of coalgebras over presheaves SetPm where δ is employed to model event generation along transitions. This category is well-behaved, in the sense that it has a final coalgebra, whose equivalence coincides with coalgebraic bisimilarity. Here we represent the LTS of step (i) as a coalgebra on a suitable presheaf of causal processes, which we call causal coalgebra. We show that coalgebraic bisimilarity on this coalgebra is essentially Xxxxxxxxx-Xxxxxx’x strong causal bisimilarity, so the image of the causal coalgebra in the final one is indeed formed by causal trees. The state space explosion issue still exists in the causal coalgebra, because the poset of a causal process keeps growing along transitions. However, for “well-behaved” presheaves, according to [CKM10], it is always possible to recover the support of a causal process, i.e., the minimal poset on its events. This allows identifying all (equivalent) causal processes with the same support, which in many cases yields a finite state-space, and is crucial for the equivalence between coalgebras over well- behaved presheaves and History Dependent Automata [MP05, CM10], that are finite automata suitable for verification. Surprisingly, for the presheaf of causal processes, computing the su...
