２−６．無時間検定法

■ネイティブな短絡グラフ法は，全数検定を行なうのでシャットダウンが発生すると探索木のバックトラックが発生し，最悪の場合には，Ｏ（Ｎ！）の計算コストを要することになる．このバックトラックを抑止するために開発された方法が再検グラフ法である．再検グラフ法では短絡グラフでデッドロックした確定パスを引き継いで，それをデッドロックしない代替パスに変換する．ここで，短絡グラフの確定パス上の点を継承点とするとき，この再検グラフの返す代替パスがすべての継承点を含むものとなるようにすることができれば，再検グラフは短絡グラフのある段階から決して後戻りしない再検定を実現するものとなる．

■デッドロックに対処するためには，デッドロックのことを知る必要がある．デッドロックについては次章で詳細な分析を行いデッドロックに関する非決定性がどのような様相をもって展開されるかを見ることになるが，この章では「デッドロックの重ね合わせの原理」と呼ぶ法則が成立することを仮に承認して議論を進めることにする．

■まず，デッドロックの重ねあわせの原理を用いて，あらゆる可能な場合を含んだデッドロックパスとデッドロックマップから本来可能であった代替パスを導出するという方針のもとで再検グラフ法を構成する．この方法がコスト的に不可能であることはやがて明らかになるが，それを確認した上で，この問題を本質的に解決する方法としての無時間検定法を発案し，その定式化を試みる．無時間検定法は，残された可能性を含んだデッドロックマップからすべての継承点を含むデッドロックしない代替パスを導出する．