DPORに基づくモデルチェッカーのための状態空間推定

この論文は、並行プログラムのモデル検査における状態空間のサイズの推定という困難な問題に取り組み、特にMazurkiewiczトレース同値クラスの数に焦点を当てています。これは、モデル検査の実行時間を予測し、検索空間のカバレッジを理解するために重要です。この論文の重要性は、#P困難性と計数問題の近似不可能性を考慮すると、証明可能な多項式時間無偏推定量を提供することにあります。 DPORアルゴリズムとKnuthの推定量を利用したモンテカルロアプローチは、制御された分散を持つ実用的なソリューションを提供します。共有メモリベンチマークでの実装と評価は、推定量の有効性と安定性を示しています。