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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Faster Signature Refinement for Branching Bisimilarity Minimization

  • Jan Martens,
  • Maurice Laveaux

摘要

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.