通过优先性逻辑统一事件结构

《Journal of Logical and Algebraic Methods in Programming》:Unifying Event Structures via a Logic over Precedence

【字体: 大 中 小 】 时间:2026年09月24日 来源:Journal of Logical and Algebraic Methods in Programming 1.0

编辑推荐:

   **逻辑事件结构(Logical Event Structures)** 提供了一种统一的事件结构框架。**事件依赖关系**通过命题性优先条款进行规范。**因果、非对称、流、包和抑制器结构**均可从中恢复。**LES的配置**产生原语代数域。**一个余反射(coreflect

  

**逻辑事件结构(Logical Event Structures)** 提供了一种统一的事件结构框架。**事件依赖关系**通过命题性优先条款进行规范。**因果、非对称、流、包和抑制器结构**均可从中恢复。**LES的配置**产生原语代数域。**一个余反射(coreflection)**将逻辑事件结构与域联系起来。

---

**引言**

在对并发系统进行建模时,一个经典的二元选择在于"交替"与"真并发"之间的取舍。第一种方法将两个系统的并行组合描述为对其计算步骤可能交错方式的非确定性选择。第二种方法,也称为偏序方法,通过合适的相关关系来显式描述计算步骤之间的依赖关系。在此设定下,**因果事件结构(prime event structures, pess)**[3]提供了一个参考模型,它以事件的集合(解释为计算的原子步骤)以及它们之间的两种关系——因果性(建模为偏序 ≤)和冲突(建模为对称且无自反的关系 #)——来优雅地捕捉系统的动态行为。一个配置是一个无冲突且关于因果性向下封闭的事件集合,它代表了系统的一个有效执行场景。

然而,pess的简洁性限制了其表达能力。在试图保留pess所提供的清晰性、同时又自然地直接编码更复杂依赖关系(例如并发语言和Petri网中出现的那些)的过程中,人们提出了多种pess的推广形式,通过引入新的关系原语来丰富原始模型,从而形成了我们称之为"关系动物园"(relational zoo)的局面。

pess的一个局限性在于,每个事件都必须有一个唯一的、无冲突的因果过去。这严格禁止了对析取因果性的意图性表示。例如,建模一个事件c由a或b引起(其中a#b)的系统时,被迫将c复制为两个不同的事件c1和c2。这在尝试编码如通信系统演算(CCS)[4]等提供带同步的并行组合算子的形式体系时尤为突出。为解决这一问题,Boudol引入了**流事件结构(flow event structures, fess)**[5]。通过将传递的偏序替换为非传递的流关系(?),fess允许多个冲突的前驱。这使得例如可以建模事件c由冲突的a或b引起的事实,而无需任何复制。代价是需要更复杂的规则来识别配置,其中需要动态地隔离最大无冲突的因集合。

另一种表示析取因果性的方法是**包事件结构(bundle event structures, bess)**[6],由Langerak引入。与描述可能的流(从中产生析取因集合)不同,bess的解决方案是引入包关系 ?,显式地将X?e描述为事件e的一组析取因X,并带有约束条件:X必须是一组两两冲突的事件。这样做会损失一些表达能力,但换来了简洁性。

在建模资源不仅被生产和消耗,还可以被读取的系统时,所谓的**上下文依赖**或**非对称冲突**自然出现。假设事件a读取了后来由b消费的资源(但未消费它):那么a可以在b之前执行,但反之则不行。为了忠实地表示这种情况,研究人员考虑了带有非对称冲突或上下文依赖的事件结构模型(扩展包事件结构[7]、带可能事件的 事件结构[8]、非对称事件结构(aess)[9])。特别是,在[9]中,作者与Ugo Montanari一起将非对称冲突关系(↗)提升为一等原语,表明这种弱因果性的形式需要独立于标准对称冲突的基本数学处理。

关系复杂性的进一步突破点来自于对非单调行为的建模需求,例如某些Petri网模型中的**抑制器弧**[10]、[11],其中只有当库所不包含标记时,变迁才能触发。为建模这一行为,引入了**抑制器事件结构(iess)**[12],配备了三元禁用-使能关系()。该三元关系的配置语义和态射证明需要相当密集且反直觉的集合论机制。此外,与前述其他模型不同,对于给定的ies,一组事件并不能唯一确定时间优先关系,因此配置被定义为事件的偏序,而不仅仅是顺序由静态关系导出的集合。

在本文中,我们提出**逻辑事件结构(logical event structures, less)**作为统一的形式化框架。我们的提案基于一个简单的观察:前述不同的事件结构模型使用静态关系来对事件的时间优先性施加约束。逻辑事件结构将事件发生和时间依赖(分别用原子命题x和(x?y)表示)作为唯一的原始概念,并通过在这些原子上的命题理论T来定义行为。

例如,我们可以通过条款 y → (x?y) 来编码因果性 x < y,这意味着如果y在计算中发生,那么x必须先于其发生。同样,我们可以通过 x∧y → (x?y) 来编码x和y之间的非对称冲突(在[9]中记为x↗y),陈述的是:如果x和y都发生,则x必须先于y发生,而相反的顺序被禁止。二元冲突 x#y 可以通过条款 x∧y → false 来编码,意味着如果x和y都发生,则产生矛盾。该框架还容易编码n元冲突为 x1∧…∧xn → false,意味着x1,…,xn不能一起出现在计算中,但其任何真子集可以。更复杂的依赖关系可以通过更复杂的条款来编码,例如,析取因果性可以编码为 c → (a?c)∨(b?c),意味着如果c发生,则a或b必须先于其发生。我们将在第4节中进一步讨论这一点,当我们将各种事件结构编码为less时:对于每种事件结构模型,我们将在命题理论的定义中使用具有特定形状的依赖条款。这为"动物园"中的混乱状况带来了一些清晰和秩序。

LESS配备了一种配置概念。一个关键选择是考虑配置不仅仅是事件的集合,而是偏序,携带其时间优先关系的显式表示。这与[13]中正集族(families of posets)的定义相似,我们共享了一些直觉,同时也类似于[12]中的配置概念。然后我们证明,在上述文献中反复为提及的事件结构类证明的标准结果可以在这种一般设定下(在理论上的温和条件下)被恢复。具体而言,我们研究了配置偏序的序论性质,表明它们总是导致原语代数域。此外,我们引入了模拟态射(simulation morphisms)将less转化为范畴,并表明该结果可以以范畴论的余反射形式表述,即与原语代数域范畴之间的余反射。

许多作者提出了事件结构的一般化概念,以在单一统一框架内捕捉复杂的依赖关系和配置。虽然提供这些框架的详尽列表是不可能的,但一些值得注意的例子包括事件自动机[14]、因果自动机[15]以及配置结构(其中配置被正式表达为命题理论)[16]。

这些模型捕捉了上述大多数特定类型的事件结构,但这是通过使用极其一般的使能概念来实现的,可能允许非单调和非原子的使能,从而产生远超原语代数域的配置类。此外,尽管忠实地捕捉了动态行为,此类方法并不考虑所生成配置的因果结构,配置仅仅是事件集合。因此,关于时间优先性的信息丢失了。

我们的工作精神相似,但目标在某种程度上不那么宏大:LESS(可称为逻辑因果事件结构)旨在提供因果事件结构的温和推广。具体而言,它们允许更方便地表示某些本来可以在pess中捕捉的行为(尽管以事件复制为代价)。这可以从LES的配置形成原语代数域这一事实中得到见证,以及原语代数域和pess之间众所周知的余反射的存在。

本文其余部分的结构如下。在第2节中,我们引入LES的概念;在第3节中,我们研究配置偏序的序论性质,表明它们总是导致原语代数域;在第4节中,我们展示如何将上述各种事件结构类编码为合适的LESS;在第5节中,我们引入将LESS转化为范畴的模拟态射,并表明该结果可以以范畴论的余反射形式与域范畴相联系;最后,在第6节中我们总结结论并讨论未来工作。

---

**逻辑事件结构(Logical Event Structures)**

其思想在于通过命题理论在逻辑层面定义事件结构,这些理论构建在表示事件发生的原子上(以事件的名称x表示)以及事件之间的时间依赖(表示为x?x′,直观含义为x和x′都发生了且x先于x′发生)。感兴趣的理论将是形如以下形式的条款集合:

x1∧…∧xn → (z1?xi1)∨…∨(zk?xik)

其中i1,…,ik ∈ {1,…,n}。其直观含义为:如果所有事件xi……

**逻辑事件结构的域性质**

在开创性论文[17]中,作者引入了因果事件结构(pess)并证明按子集包含排序的pes配置集合构成一个原语代数域。后来在[3]中,这一对应关系在范畴层面被形式化为范畴等价,证明pess可以被视为形成原语代数域的配置类的意图性表示。在本节中,我们开始将LESS与域联系起来,表明……

**事件结构的编码**

在本节中,我们展示如何将多种事件结构模型编码为特殊的逻辑事件结构。各种事件结构概念可能在它们允许的事件间关系以及配置的定义方式上有所不同。在这里我们展示如何通过具有特定格式的依赖条款来忠实地编码各种关系类型,使得原始模型的配置定义在所得到的LESS中本质上是保留的。对于所有事件结构模型,除了……

**逻辑事件结构,从范畴论角度看**

在本节中,我们引入了LESS之上的模拟态射概念,将LESS的类转化为范畴LES。依赖于pess的范畴(最初由Winskel引入)可以被自然地看作LES的范畴的范畴这一事实,我们可以将与原语域的对应关系提升到范畴层面,证明LES与原域范畴Dom之间存在余反射。

---

**结论与未来工作**

在本文中,我们引入了逻辑事件结构作为表达力强、简洁且在数学上统一的框架,驯服了描述配置原语域的日益增长的"关系动物园"式的事件结构模型。通过将复杂的结构依赖关系归结为单一原始概念——时间依赖——并通过命题理论来管理事件交互,我们展示了如何将各种事件结构类型(如因果、非对称、流、包和抑制器……

---

**CRediT作者贡献声明**

Paolo Baldan:原始草稿撰写。Andrea Corradini:原始草稿撰写。

**利益冲突声明**

作者声明不存在已知的竞争性经济利益或个人关系可能影响本文所报告的工作。

Paolo Baldan | Andrea Corradini
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号