Faster Signature Refinement for Branching Bisimilarity Minimization
摘要
We present a new algorithm to efficiently minimize state spaces with respect to branching bisimilarity. Our approach combines signature-based refinement with Hopcroft’s “process-the-smaller-half” optimization to avoid unnecessary computation. This combination results in a conceptually simpler and empirically faster algorithm for state space minimization modulo branching bisimilarity. While the theoretical worst-case complexity is slightly worse than existing algorithms, empirical evaluations on benchmarks demonstrate significantly better performance.