一句话:提出 connected event structures 及其对偶域,刻画非线性图重写等融合计算的并发语义。
稳定事件结构与素代数域的对偶是并发理论基石,用 configuration 偏序刻画因果性,并支撑 Petri 网、线性图重写等并发语义。但稳定性对某些形式系统过严:非线性图重写等计算步会合并状态部分(fusion),如带名字传递演算的图形编码。本文定义一类自然推广素代数域的域,用于建模带 fusion 的形式系统语义;并通过范畴等价的对偶结果,识别出对应的事件结构,称为 connected event structures。作者证明 connected event structures 恰为非线性图重写系统产生的事件结构。此外,一般 unstable event structures 的范畴余反射到该域范畴,从而刻画此类事件结构的 configuration 偏序。
Stable event structures, and their duality with prime algebraic domains (arising as partial orders of configurations), are a landmark of concurrency theory, providing a clear characterisation of causality in computations. They have been used for defining a concurrent semantics of several formalisms, from Petri nets to linear graph rewriting systems, which in turn lay at the basis of many visual frameworks. Stability however is restrictive for dealing with formalisms where a computational step can merge parts of the state, like graph rewriting systems with non-linear rules, which are needed to cover some relevant applications (such as the graphical encoding of calculi with name passing). We characterise, as a natural generalisation of prime algebraic domains, a class of domains that is well-suited to model the semantics of formalisms with fusions. We then identify a corresponding class of event structures, that we call connected event structures, via a duality result formalised as an equivalence of categories.We show that connected event structures are exactly the class of event structures that arise as the semantics of nonlinear graph rewriting systems. Interestingly, the category of general unstable event structures coreflects into our category of domains, so that our result provides a characterisation of the partial orders of configurations of such event structures.