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