论文标题
通过分区细化进行分配的较低范围
Lowerbounds for Bisimulation by Partition Refinement
论文作者
论文摘要
我们为使用分区细化的标记的过渡系统确定分配的顺序和并行算法提供时间下限。对于顺序算法，这是$ω（（（m \ mkern1mu {+} \ mkern1mu n）\ mkern-1mu \ log \ log \ mkern-1mu n）$，对于并行算法，这是$ω（n）$，其中$ n是$ n $ n $ n $ n $是$ m $ $ $ $ $ $ $ $ $转换。通过分析确定性过渡系统的家族，最终在顺序的情况下采取了两种动作，而对平行算法进行了一种动作，从而获得了较低的障碍。对于具有一项动作的确定性过渡系统，可以按根本不同的技术依次确定双性异性。特别是，Paige，Tarjan和Bonic在这种特定情况下给出了线性算法。我们表明，利用甲骨文的概念，这种方法无助于开发更快的通用算法来决定双性恋。对于并行算法，也可以应用这些技术的类似情况。
We provide time lower bounds for sequential and parallel algorithms deciding bisimulation on labeled transition systems that use partition refinement. For sequential algorithms this is $Ω((m \mkern1mu {+} \mkern1mu n ) \mkern-1mu \log \mkern-1mu n)$ and for parallel algorithms this is $Ω(n)$, where $n$ is the number of states and $m$ is the number of transitions. The lowerbounds are obtained by analysing families of deterministic transition systems, ultimately with two actions in the sequential case, and one action for parallel algorithms. For deterministic transition systems with one action, bisimilarity can be decided sequentially with fundamentally different techniques than partition refinement. In particular, Paige, Tarjan, and Bonic give a linear algorithm for this specific situation. We show, exploiting the concept of an oracle, that this approach is not of help to develop a faster generic algorithm for deciding bisimilarity. For parallel algorithms there is a similar situation where these techniques may be applied, too.
