paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Fast Coalgebraic Bisimilarity Minimization

快速余代数互模拟最小化
POPL 7(POPL)2023匹配度 2/10 · 论文属于余代数、互模拟与自动机最小化的形式方法,与用户当前聚焦的 LLM/Agent 与静态分析、浮点程序分析、贝叶斯程序分析交叉方向没有直接关联;仅在形式验证与自动机理论层面有间接基础价值。引用 6 inbox
Jules Jacobs, Thorsten Wißmann
crossref: 2026-09-10

AI 速览

一句话:提出一个通用余代数互模拟最小化算法,仅需可计算的函子作用,并在基准上优于专用工具。

余代数互模拟最小化将经典自动机最小化推广到由函子指定转移结构的一大类自动机,涵盖强、加权和概率互模拟,但其通用算法长期缺失:尚无同时做到完全通用、高效并能处理大规模系统的算法。本文在集合范畴中为任意函子提出通用最小化算法,前提是函子在态射上的作用足够可计算。算法对函子特定作用的调用次数为 O(m log n),其中 n 为状态数、m 为转移数。虽然专用算法在渐近复杂度上通常可快 m/n 倍,但该算法更易高效实现;作者的工具在现有基准上常耗费更少时间和内存,并能处理更大的自动机,尽管其通用性更强。

问题
如何为一大类由函子定义的自动机(含强、加权、概率互模拟)提供完全通用且可处理大规模系统的互模拟最小化算法。
方法
在 Set 上对任意函子构造通用算法,仅要求态射作用足够可计算;通过控制对函子特定作用的调用次数(O(m log n))实现高效实现。
评估
与专用算法的复杂度及现有基准进行比较;实现工具在时间和内存上常优于现有工具,并能处理更大的自动机。
原文摘要(Abstract)

Coalgebraic bisimilarity minimization generalizes classical automaton minimization to a large class of automata whose transition structure is specified by a functor, subsuming strong, weighted, and probabilistic bisimilarity. This offers the enticing possibility of turning bisimilarity minimization into an off-the-shelf technology, without having to develop a new algorithm for each new type of automaton. Unfortunately, there is no existing algorithm that is fully general, efficient, and able to handle large systems. We present a generic algorithm that minimizes coalgebras over an arbitrary functor in the category of sets as long as the action on morphisms is sufficiently computable. The functor makes at most O ( m log n ) calls to the functor-specific action, where n is the number of states and m is the number of transitions in the coalgebra. While more specialized algorithms can be asymptotically faster than our algorithm (usually by a factor of ( m / n )), our algorithm is especially well suited to efficient implementation, and our tool often uses much less time and memory on existing benchmarks, and can handle larger automata, despite being more generic.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot2084,
  title = {Fast Coalgebraic Bisimilarity Minimization},
  author = {Jules Jacobs and Thorsten Wißmann},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {7},
  number = {POPL},
  year = {2023},
  doi = {10.1145/3571245}
}