基于 DPOR 的模型检查器的状态空间估计

本文解决了并发程序模型检查中状态空间大小估计的难题，特别关注 Mazurkiewicz 轨迹等价类的数量。这对于预测模型检查的运行时间和理解搜索空间覆盖率至关重要。本文的意义在于提供了一个可证明的多项式时间无偏估计器，考虑到计数问题的 #P 难度和不可逼近性，这是一个重大进展。利用 DPOR 算法和 Knuth 估计器的蒙特卡罗方法提供了一个具有可控方差的实用解决方案。在共享内存基准测试中的实现和评估证明了估计器的有效性和稳定性。