论文标题
快速结构的双性恋最小化
Fast Coalgebraic Bisimilarity Minimization
论文作者
论文摘要
煤层双性异性最小化将经典的自动机概括为大型自动机，其过渡结构是由函子指定的，累积了强，加权和概率的双性异性。这提供了将双次数最小化变成现成技术的诱人可能性，而无需为每种新型自动机开发新算法。不幸的是，没有现有的算法完全通用，高效且能够处理大型系统。 我们提出了一种通用算法，该算法只要对形态的作用就足够计算，可以最大程度地减少集合中任意函数的膜。函子最多使$ \ Mathcal {O}（M \ log n）$调用函数特定的操作，其中$ n $是状态数，$ m $是煤层中的过渡数量。 虽然更专业的算法可以比我们的算法更快（通常是$ \ Mathcal {o}（\ frac {m} {n}）$）的算法，但我们的算法非常适合有效地实现，并且在现有的台阶上使用了更大的时间和自动的boa，并且可以自动进行更多的时间和内存。
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 $\mathcal{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 $\mathcal{O}(\frac{m}{n})$), our algorithm is especially well suited to efficient implementation, and our tool Boa often uses much less time and memory on existing benchmarks, and can handle larger automata, despite being more generic.
