２－６－２．無時間検定法

■無時間検定法は再検グラフ法の欠陥を改良し，決して後戻りすることのない，しかし現実的な代替パスを得るための方法である．欲しいのはすべての可能性では無く，只ひとつの可能性があればよいのだから，再検グラフの方法において枝カウント０の点の枝をすべて確定するという操作が過剰なものであったことは認めることができる．枝カウント０の脱落点は，いずれ代替パスを求める段階で任意確定されるのだから，デッドロックマップ中ですべてを展開するというのはやり過ぎであったと言えるだろう．

■デッドロックのもうひとつの相である，隣接する複数の点の枝カウントが１となった点，つまり確定パスが分裂しようとしている点については次のことが言える．この点に接続する２つの枝カウント１の枝は，一方が確定されるとしたら，他方は除去されなくてはならないという関係にあるから，相互矛盾している．この２つの確定は相前後して起るのではなく無時間で発生しなくてはならないから，確定と除去という２つの操作しか認められないとすれば，この２つの枝は同時に除去される以外ないだろう．もし，そうであるとすれば，この確定パスの分裂点は枝カウント０となり，枝カウント１の枝によって接続する他方の点も同時に，枝カウント０の脱落点となることになる．

■どのような計算課程も，無時間で完了する計算を実現することはできないだろう．因子検定においても，時間はシーケンシャルである．つまり，任意選択局面ないしステージのシーケンシャルな列としてプロセスは線形に進行する．自動確定規則は因子検定における因果律を表示するものと言えるかもしれない．

■もし，計算プロセスを無時間で実行することが不可能であるとしたら，それをシーケンシャルな時間の中で可能な限り近似的にシミュレートする以外無いのではないだろうか？可能な再検定の方法があるとすれば，それはおそらく次のように無時間をスライスしてある単位時間の列に置き換えるというものになるであろう．

(1) 計算プロセスはステージないしステップではなく，セコンドという単位によって進行する．

(2) 継承点の枝は最初の１セコンドですべて確定される．確定に伴う枝の除去を実行する．

(3) 次の１セコンドの中で起ることは，枝カウント１となった点の枝の確定とそれに伴う枝の除去である．一旦確定された枝は除去されず，除去された枝は確定されない．つまり枝カウントはここでは未検定の枝数（確定も除去もされていない枝数）を意味する数値である．１セコンドの中では，確定→除去の１ステップを実行する前にデッドロックの発生を監視し，分裂点ないし脱落点を検出するとそのセコンドで時間を停止する．

(4) 枝カウント１の枝を複数持つ分裂点を検出すると，分裂点に接続する枝はすべて除去され，分裂点に枝カウント１で接続する点は脱落点となる．

(5) 枝カウント０の脱落点を検出すると，そのセコンドで停止する．そのセコンドの枝カウント１の枝は確定されずに残ることになる．

(6) １セコンドを単位にこれを繰り返し，枝カウント１の点が無くなると停止する．与えられた確定パスは要因枝セットであるから，枝カウント１の点が無くなって停止するという場合はあり得ない．

(7) 確定されたすべての枝からなる枝集合をデッドロックパスとする．デッドロックパスには最初の１セコンドで確定された継承点の枝と，それに伴ってデッドロック発生の前に自動確定された枝が含まれている．

(8) グラフＧの枝のうち，確定も除去もされていない枝をすべてパージして，残った枝集合の枝セクショングラフを求め再検グラフＲとする．再検グラフＲの点集合はデッドロックパス上の点と分裂点，脱落点およびデッドロックパス上の点に隣接するすべての未検定点を含んでいる．再検グラフＲは必ずしも連結ではないグラフＧの部分グラフである．

■この再検グラフＲは残された可能性を含むデッドロックマップと呼ばれる．それはこのデッドロックマップ上に，分裂点に存在する複数の可能性が（強制的に停止されたために検定されないで）そのまま温存されていることを示すものである．あらゆる可能な場合を含んだデッドロックマップの場合には，矛盾点の無制限な増殖を防ぐことはできなかったが，残された可能性を含むデッドロックマップには極小な矛盾点しか含まれていない．

■このセコンドと呼ぶスライスされた時間単位を持つ再検グラフ法の改訂版が無時間検定法である．因子検定ではデッドロックの発生する場所が決定不能となってしまう場合があるが，無時間検定ではすべての地点の時計はセコンドという世界時間によって均等に進むので，矛盾点はつねに一意に決定される．
どの地点でデッドロックが発生するかということを決定する要素は，確定点からの距離であると考えられる．自動確定の波は確定→削除→確定→削除のように進行するので，隣接した点を結ぶ路の距離を１とすれば，１セコンドごとに半径が２づつ広がる波紋のような運動と見ることができる．従って，波の発生源からの距離に依存してデッドロックの発生時刻が決定されるから，発生源からの距離のもっとも近い点で最初のデッドロックが発生し，停止する．再検グラフ上で定義されるデッドロックはこのような意味において初発的デッドロックと呼ばれる．

■まず，このデッドロックパスとデッドロックマップの持ついくつかの特徴について確認する．（以下における点および枝についての記述は，入力に関る場合と出力に関る場合とですべて独立に適用されることに注意する必要がある．）

① デッドロックパスは要因枝セットであり，デッドロックパスの枝をすべて確定するとデッドロックマップは，初発的なデッドロックが発生した状態になる．

② デッドロックが発生したために中断され確定されなかった枝カウント１の枝は，確定も除去もされなかったのだからデッドロックマップ上には存在しない．この枝は初発的デッドロックの発生したセコンドの一つ前のセコンドにおいて枝カウント１となっている．

③ デッドロックマップ上に分裂点があるとすれば，その分裂枝はデッドロック発生の一つ前のセコンドで同時に枝カウント１になったものである．

④ 分裂点および，脱落点はいずれもデッドロックパス上の内点ではない．（但し，デッドロックパス上の端点となる場合はあり得る）これは，最初の１セコンドで確定パス上のすべての点が確定され，一度確定された枝は削除されないという手順から単純に導かれる帰結である．

⑤ デッドロックマップには，未検定点と未検定点，未検定点と脱落点，脱落点と脱落点を結ぶ枝は存在しない．また，デッドロックマップの点集合に含まれない外部の点と接続する枝は含まれていない．

⑤ 未検定点は少なくとも１本の除去枝と１ないし２以上の（デッドロックマップには含まれていない）外部の枝を持っている．外部の枝を１本しか持たない未検定点とは上記②の枝カウント１の枝に関る点に限られる．

⑥ 残された可能性を含んだデッドロックマップはその名の通り，まだ展開されていない２つの可能性を残している．いずれもデッドロック発生のひとつ前のセコンドにおいて枝カウント１となった枝に始まる確定伝播路つまり自動確定の波であり，ひとつは上記②の未確定の枝から始まり，もうひとつは③の分裂点を出発点とする確定伝播路である．

⑦ 分裂点の分裂枝のうちの１本は確定されなくてはならない．また脱落点の枝のうちの１本も復活確定されなくてはならない．

⑧ 分裂点ないし脱落点の枝を確定したとき，デッドロックが発生する可能性は存在する．むしろ，このことを利用して矛盾の原因となる枝を取り除くことが可能である．分裂点と脱落点の枝がデッドロックを発生することなく確定できるとすれば，それに付随して自動的に（確定伝播の作用によって）デッドロックパス上の誤った枝は除去され，矛盾は解消する．

⑨ 未検定点に残った枝カウント１の枝は未検定のまま残されてしまったから，デッドロックマップ上の枝としては存在しない．従って，この枝が不在であることを原因とするデッドロックはデッドロックマップ上では発生しない．デッドロックマップ上に存在しない枝を対象要素に含む検定はデッドロックマップの範囲を逸脱する検定と呼ばれる．

	確定入力点	分裂入力点	脱落入力点	未検入力点
確定出力点	確定枝除去枝	除去枝	除去枝	除去枝
分裂出力点	除去枝	除去枝	分裂枝	除去枝
脱落出力点	除去枝	分裂枝	－	－
未検出力点	除去枝	除去枝	－	－

■分裂点の場合の動作を除外して考えると，自動確定の波は確定→削除→確定→削除のように進行することから，除去された枝の端点の少なくとも一方は必ずデッドロックパス上にあることが分かる．（枝リストを閉路として閉じる枝の除去の場合には除去される枝の両端点はともにデッドロックパスの上にある．）従って除去された枝をもう一方の端点によって次の４種に区分することができる．

(a) デッドロックパス上の点（確定入力点，確定出力点）を持つ枝

■これら４種類の枝のうち，(ｄ) の枝がデッドロックの現象に直接の関りを持たないことは明らかである（つまり，デッドロックの要因枝ではない）．これらの点の枝カウントは１よりも大きいので自動確定の波はそこで小休止している．グラフＧのデッドロックパス上の点と矛盾点を除く点を未検定点とすれば，上記よりデッドロックマップ上には未検定点と未検定点を接続する枝，未検定点と脱落点を接続する枝，脱落点同士を接続する枝は存在しない．つまり，デッドロックマップ上に残る未検定点は，必ず確定点（ないし分裂点）に接続する枝を持っている．また，通常の脱落点は確定点に接続する枝以外を持たない．（未検定点はデッドロックマップ上に存在しない点に隣接している可能性はあるが，脱落点はすべての枝を除去されているのだから，確定点に接続する枝以外の枝を一切持っていない．）

■分裂点の枝の場合は自動確定の波は確定→削除→確定→削除→＜削除＞のように枝の除去操作が２ステップ連続して進むことになる．この＜削除＞によって分裂点に接続する枝カウント１の枝が除去される．無時間検定では分裂点の発生によるデッドロックの起るセコンドは唯一度しか存在しないから，この＜削除＞によって発生する脱落点は少なくともその前のセコンドの枝操作によって枝カウント１の点になっていなくてはならない．従って，脱落点はこのセコンドで削除される枝つまり，分裂点に接続する枝を除くと，上記したように確定点に接続する枝以外を持たないということが言える．

■分裂点の場合は，脱落点の場合と異なり，デッドロックが発生した時点ですべての枝が削除されるので，これら除去枝の中には未検定点ないし他の分裂点に接続する枝も存在する．しかし，図17に示すように分裂点と分裂点を接続する分裂枝は原理的に存在しない．このような枝は無時間検定の終結図式である初発的デッドロックが発生した状態にあるデッドロックマップ上には現れない．

■分裂点と脱落点の枝を確定したとき，デッドロックが発生する可能性は存在する．むしろ，このことを利用して矛盾の原因となる枝を取り除くことが可能である．これらの枝は確定→削除→確定→削除のように進行する自動確定の波によって削除された．この削除された枝を同じマップの上で確定すると（一旦確定された枝も削除されるという規則のもとで）削除←確定←削除←確定のような逆方向の波が発生し，削除の原因となった枝が逆に削除される．

■削除←確定によって削除される枝はデッドロックパス上の確定枝であるから，この枝の点の枝カウントは既に１となっている．従ってこの削除は直ちに脱落点の発生によるデッドロックを引き起こすものとなる．また，このような反射的なデッドロックが発生してしまうために，この確定伝播路は１セコンドで３以上の距離を進むことは無い．

■分裂点の場合には確定→削除→＜削除＞という操作が行われるので，分裂枝を確定した場合には確定←削除←＜確定＞の反応が起るから，一般には確定伝播しないと考えてよい．もう一方の棄却された分裂枝の接続する脱落点では，脱落枝の復活確定が行われる．この操作によって確定枝の除去による反射的なデッドロックが発生する可能性はある．

■デッドロックマップ上の点を確定枝との接続関係から整理すると次の５種を区分できる．これらの点はもちろんこれらの他にそれぞれに接続する除去枝を持っている．

(b) デッドロックパス上の端点確定枝数１入力枝ないし出力枝

(d) 孤立した分裂点，脱落点確定枝数０デッドロックパス外の点

■デッドロックマップ上の点は，接続する枝の向きによって一方から見ると入力点であり，他方から見ると出力点である．従って，すべての点はこの意味で２重に定義されている．点におけるこれらの２相の組み合わせを以下の表2にまとめておく．

■たとえば，確定入力点は確定入力枝を持つ点であり，脱落出力点はその点の出力枝カウントが０となった点である．未検定入力点はその点の入力枝が未検定であること，つまり確定も除去もされていない入力枝が１ないし２本以上存在していたことを意味する．（デッドロックマップ上にはこれらの未検定枝は存在しない．）

■表2の赤字の部分は入力ないし出力の少なくとも一方の枝が確定している点であり，デッドロックパス上の点である．デッドロックパスの端点には脱落点や分裂点が存在する場合があることに注意する必要がある．これら以外の点はすべてデッドロックパスの外にある点であり，デッドロックパス上の点とは除去枝によって接続している．

		確定出力点	分裂出力点	脱落出力点	未検定出力点
		確定出力枝数１	確定出力枝数０	確定出力枝数０	確定出力枝数０
確定入力点	確定入力枝数１	(a)全確定点	(c)分裂端点	(c)脱落端点	(b)確定端点
分裂入力点	確定入力枝数０	(c)分裂端点	(d)全分裂点	(d)壊滅点	(d)分裂点
脱落入力点	確定入力枝数０	(c)脱落端点	(d)壊滅点	(d)全脱落点	(d)脱落点
未検定入力点	確定入力枝数０	(b)確定端点	(d)分裂点	(d)脱落点	(e)未検定点

■無時間検定は短絡グラフのデッドロックする確定パスから，デッドロックパスとデッドロックマップを生成する．デッドロックパスは初発的デッドロックを発生する要因枝セットであり，短絡グラフから引き継いだすべての継承点に接続する枝を確定枝として持つ枝集合である．デッドロックマップはこの障害に関りを持つすべての枝と点を含む対象グラフＧの部分グラフ（再検グラフＲ）である．再生変換はこの再検グラフＲ上のデッドロックパスからすべての継承点を持った矛盾しない代替パスを導出する変換であり，矛盾点の回復，確定枝の除去，救済枝の再生などからなる一連の操作として定義される．さて，再生変換によって，確定パス上の点をすべて含む矛盾しない代替パスを得られるかどうかを試みることにしよう．

■デッドロックパスとデッドロックマップが与えられるとする．デッドロックパスは無時間検定によって確定されたすべての枝からなる枝集合である．デッドロックマップの枝集合はデッドロックパスと除去されたすべての枝を含む枝集合である．デッドロックマップの点集合は，継承点（短絡グラフの確定パス上の点）を含む確定点および矛盾点（脱落点と分裂点）と確定点に隣接する未検定点を含んでいる．

(2) デッドロックマップの点の枝カウントは，その点に接続する外部の枝数も含めた数値として管理する．但し，枝操作はデッドロックマップに実際に乗っている枝のみを対象として行なわれる．

(3) 最初のセコンドを開始セッションと呼ぶ．開始セッションでは，デッドロックパス上のすべての枝を確定し，確定に伴う枝の除去を実行する．これによってデッドロックマップは無時間検定でデッドロックが発生したときの状態になる．但し，分裂点の枝はまだ除去されずに枝カウント１で残っている．

(4) 次の複数のセコンドを復活確定セッションと呼ぶ．復活確定セッションでは，一旦除去された枝を確定すること，確定された枝を除去すること，除去された枝の再生（除去枝をデッドロックマップに戻すこと）が許される．復活確定セッションではすべての分裂点，脱落点の枝を任意に復活確定する．

(5) 復活確定セッションは復活サブセッションと呼ぶ複数のセコンドから構成される．復活サブセッションは，矛盾点の回復，確定枝の除去，救済枝の再生からなる一連の操作である．まず枝カウント１の枝を複数もつ分裂点の任意の枝を確定し，それに伴う枝の除去を行なう．ついで枝カウント０のすべての点の枝を復活確定する．脱落点のすべての枝はすでに除去されているから，除去された枝（ないし再生された救済枝）の中から１本を任意に選択して復活確定する．

(6) 脱落点の枝を復活確定するとその枝に隣接する確定枝が反射的に削除される場合がある．また，この反射的確定枝の除去に伴って除去されていた枝が付随的に再生する場合がある．このように確定枝の反射的な除去によって再生される枝を救済枝と呼ぶ．

(7) 反射的確定枝の除去によって反射的なデッドロックが発生する場合がある．復活確定による確定枝の除去では反射的なデッドロックが発生するので，確定伝播は拡散することなく，直ちに停止する．反射的なデッドロックが発生した場合には，そのデッドロックによって発生した新しい矛盾点を回復するための復活サブセッションが実行される．

(8) 反射的なデッドロックが発生しなくなるまで，このサブセッションを繰り返す．

デッドロックを解消するための復活枝として使える枝が存在しない状態を救済不能なデッドロックと呼ぶ．救済不能なデッドロックが発生した場合には停止する．

(9) 復活確定セッションに続くセコンドを自動確定セッションと呼ぶ．自動確定セッションでは１セコンド毎に枝カウント１となった枝の確定とそれに伴う枝の除去を行なう．

(10) 入力枝および出力枝の枝カウントがともに０の脱落点ないし，枝カウント１の枝を２本持つ分裂点を検出した状態を遅発性デッドロックの発生と呼ぶ．遅発性デッドロックが発生した場合には(1)に戻る．

(11) １セコンドを単位にこれを繰り返し，枝カウント１の点が無くなると停止する．このとき確定されたすべての枝からなる枝集合を再生パスと呼ぶ．再生パスはデッドロックマップ上ですべての枝を確定したとき，デッドロックを発生しない枝集合である．この枝集合が原グラフ上でデッドロックを起こさなければ，再生パスは無時間検定が短絡グラフに返す代替パスである．再生パスが原グラフ上でデッドロックする場合には，この無時間検定はデッドロックマップの範囲を逸脱する検定になっている．この場合には得られた再生パスを無時間検定の開始図式として，無時間検定を再実行する．

■図18, 19は図15のデッドロックマップの復活確定セッションを示すものである．図18では脱落点の枝の復活確定により，新たなデッドロックが発生しているが，図19では，このときに再生された救済枝によって新しく発生した矛盾が解決されている．

■図20に図16の分裂したデッドロックマップの復活確定セッションを示す．分裂点の復活確定も脱落点の場合とほぼ同様の方法で行なうことができる．分裂点にはかならず付随して複数の脱落点が存在するから，基本的にはそれらの脱落点を復活させるだけでよい．脱落点の場合と異なるところは，このときの復活枝の１本は必ず分裂枝のうちのいずれかでなくてはならないというところだけである．

■再生変換は矛盾点の枝を復活確定することによってデッドロックパスを再生パスに変換する一連の手続きである．この方法の特徴は，復活確定セッションと呼ぶ変換手続きによって矛盾を系統的に解決しようとしている点にある．再生変換では，復活確定による確定伝播によって確定枝を除去したとき，除去された確定肢に隣接する救済枝と呼ぶ枝グループが追放解除されて再生する．この救済枝は新たなデッドロックが発生したときの解決策を提案する枝となるものである．この復活確定セッションの動作をもう少し詳細に見ることにしよう．

① 開始セッションが生成するデッドロックマップでは初発的なデッドロックが既に発生した状態にある．初発的なデッドロックは非決定的に発生するデッドロックの中で，現象として現れるもっとも出現半径の小さなデッドロックと考えられる．

② 因子検定における任意選択による確定と復活確定のもっとも大きな相違点は，再生変換ではデッドロックパス上に初発的なデッドロックを発生するのに十分な確定枝が存在するため，確定伝播がきわめてタイトな状態になっているということである．このため，矛盾点における復活確定は直ちに確定枝の反射的な除去とそれによる反射的なデッドロックを引き起こすので，確定伝播が潜伏したり，拡散する現象が起らない．

③ 分裂点の回復は脱落点の復活に還元される．つまり，分裂点の分裂枝のうちの１本は確定されなくてはならないが，その復活確定はその分裂枝の接続する脱落点の復活確定として実行される．分裂枝の確定では，確定伝播路の朔行による確定枝の除去は発生しない．分裂枝の確定は，脱落点の復活に還元されるから，分裂点は復活確定セッションの最初の復活サブセッションにしか出現しない．その後のサブセッションはすべて脱落点の復活確定のみを処理するものとなる．

④ 最初の復活サブセッションに複数の分裂点が存在する可能性はある．しかし，複数の分裂点の分裂枝が競合して，さらに分裂点を派生するという状況はあり得ない．（再検グラフの開始図式上存在しない．）

⑤ 脱落点では除去枝ないし救済枝を復活枝に用いて復活確定を行なう．このとき，

・一端が脱落点である除去枝を確定すると他方の端点にある除去枝と同じ極性の確定枝が除去されこれによるデッドロックが発生する．復活枝と反射除去された枝の両端点には新，旧の脱落点がある．

・救済枝を確定する場合には，一端の同一極性の確定枝はすでに除去されているから，矛盾は発生しないが，他端に同一極性の確定枝がある場合には確定枝の除去が発生して，デッドロックする場合がある．

・最初の復活サブセッションでは救済枝は存在しないので，必ず脱落点の個数分のデッドロックが発生する．すべてのデッドロックは最終的には一端が未検定点であるような救済枝に至って解決する．

⑥ 対抗する枝（点を共有する同一極性の枝）を持たない枝は既定枝だから，デッドロックの原因枝とならないし，確定枝となった後除去されることもないから，復活確定によって除去される確定枝はつねに少なくとも１本の救済枝を対抗枝として持っている．従って，復活枝の不在による救済不能なデッドロックは本来発生しない．

⑦ 救済枝は復活確定セッション中にのみ現れる特殊な属性を持った枝である．前記したように，脱落点と脱落点を接続する枝，ないし脱落点と未検定点を接続する枝はデッドロックマップ上には存在しない．ところが，救済枝はまさにこのような性格を持った枝である．もし，救済枝が除去枝であるとすればこのようなことは起らないはずだが，救済枝が再生されることによってすでにこの脱落点は有効な枝を持った状態に移転しているために，脱落点というよりは未確定点と呼ばれるべき状態に遷移していると考えられる．

■再生変換には，検討すべき以下の問題点が存在する．再生変換ないし無時間検定の方法は，非ハミルトングラフであることを検出するための手段を基本的に持っていない．従って，ここでは非ハミルトングラフであることを検出して停止する問題は扱わないことにする．つまり，対象とするグラフはハミルトングラフであると仮定する．

■以下ではこれらの問題を検討し，最終的な解決策として真の無時間検定を実現する復活木を用いた再生変換を提案する．

■再生変換の開始図式（デッドロックマップ）上の枝は，確定枝であるか，除去枝であるかのいずれかである．確定枝は既定枝でないとすれば必ず対抗枝として少なくとも１本の救済枝を持っているから，この救済枝を復活枝として再使用することがつねに可能である．除去枝が発生する原因のうち，２因子規則によって除去される場合には必ずその除去枝の対抗枝としての確定枝が存在する．１閉路規則によって除去される場合には，そのような対抗枝が除去枝の両端点に１本ずつ存在する．

■除去枝が復活確定されて確定枝となり，確定枝が除去されて救済枝が再生し，この救済枝を再確定する状況を考える．もし，この救済枝のもう一方の端点が確定パス上になければその点は解決点であり，デッドロックは停止する．確定パス上にあるときにはその点に接続する確定枝の除去が発生するが，この枝が既定枝でない限りはかならずその対抗枝が存在し，その枝は救済枝として再生する．従って，このような復活枝が存在しないことを理由とする救済不能なデッドロックは発生しない．

○ 自動確定セッションは実行されず，遅発性のデッドロックは発生しない

■遅発性のデッドロックは，復活確定セッションにおける反射的デッドロックが収束した後に遅れて発生するデッドロックである．このデッドロックは復活確定セッションが終了した時点で枝カウント１の点が存在する場合にその枝を出発枝とする自動確定の波が発生することによって引き起こされる．

■まず，再生変換の開始図式（デッドロックマップ）上には枝カウント１の点は存在しないことを確認することができる．なぜなら，無時間検定によってデッドロックマップを初期生成して，初発的デッドロックが発生し無時間検定の終結図式（デッドロックマップ）が確定したときの枝カウント１の枝は，確定も除去もされなかったためにデッドロックマップからはパージされているので，再生変換の開始図式にはこの枝カウント１の枝は存在していない．

■再生変換の開始セッションの次のセコンドの開始図式では，①デッドロックパス上のすべての枝が確定されている，②それに伴う枝が除去されている，③この枝の除去により枝カウント０の脱落点が発生している，④ないし，枝カウント１の枝を複数持つ分裂点が存在している，という状況となり，結局デッドロックマップ上の枝は確定枝と除去枝および分裂枝の３種のみという状態になる．

■このとき，分裂点に関る脱落点を含めた脱落点の個数をδとすれば，復活確定セッションの最初のサブセッションでは分裂枝のうちの１本が確定され他の枝は除去されるから，デッドロックマップ上の枝は確定枝と（再生された救済枝を含む）除去枝のみになると考えられる．矛盾点の復活確定により，δ個のデッドロックが発生した状況にはなるけれどもこれらの矛盾点はすべて枝カウント０の脱落点であり，このとき（すべての枝は確定枝かないし除去枝に区分されるから）枝カウント１の点（つまり未確定の枝を持つ点）は存在していない．

■従って，反射的に発生するデッドロックが収束した後のセッションにも，未確定の枝は存在せず，従って自動確定セッションそのものが実行されないということがわかる．よって遅発性のデッドロックは当然発生しないから，復活確定セッションが収束したときにはすでに再生変換は終結図式に到達している.

○ デッドロックマップの範囲を逸脱した再検パスから無時間検定を再実行する
再生変換の与える再生パスは主に次のような理由から，グラフＧ上でデッドロックする場合があり得る．無時間検定が生成する再検グラフＲはグラフＧの部分グラフであるからグラフＧのハミルトンタイの枝集合のすべてを含んでいないことは当然であるが，特にデッドロックマップの未検定点については，

ａ．未検定点同士を接続する枝を持っていない
ｂ．未検定点と外部の点を接続する枝を持っていない

という限定条件が存在する．未検定点に接続する枝は開始図式においてすべて除去枝の状態にあるが，これらの枝が最終的に除去される限り特に問題は発生しない．再生変換ではこれらの枝を復活確定する場合があり得るので，それに付随してデッドロックマップの外部の枝が（潜在的に）除去されるということも当然発生する．このことは，潜在的に外部の（別の）枝が確定伝播によって確定される可能性があるということを意味している．]

■除去枝の復活確定を含む再生パスがデッドロックマップの範囲を逸脱するという現象は，このような確定伝播路の外部への漏出とそれに起因する外部枝の潜在的な確定を原因とするものである．このような潜在的な確定伝播はデッドロックマップという限定された領域内の閉じた枝操作のみによって構成される再生パスには当然伝達されないから，再生パスを原グラフに戻したときに始めてデッドロックが発生するということになる．

■デッドロックマップの範囲を逸脱した再生パスを開始図式として無時間検定を再実行する方法の正当性は次のことから言える．①短絡グラフから引き継いだ継承点の集合を継承点集合とする．②無時間検定の方法により，グラフＧのデッドロックする要因枝集合から開始図式となるＧの部分グラフである再検グラフを生成し，その再検グラフの中でデッドロックしない確定枝集合を得ることができる．③このとき，この確定枝集合の接続点集合は継承点集合を部分集合として含んでいる．これが再生変換が返す再生パスである．④再生パスが原グラフでデッドロックする場合には，再生パスを②の要因枝集合としてこのプロセスを反復することができる．⑤新たに得られた再生パスの枝の接続点集合は継承点集合を部分集合として含んでいる．

■復活サブセッションでは，脱落点→復活枝の確定→確定枝の除去→新たな脱落点→救済枝の再生のようにプロセスが進行する．脱落点，復活枝，確定枝，新たな脱落点，救済枝は確定伝播路の上でこの順に出現するから，この復活確定によって脱落点は枝２本分つまり距離２だけ確定伝播路上を移動する．ある脱落点における矛盾は１本の確定伝播路に沿った復活確定の枝操作によって解決されると考えることができる．

■ある脱落点を救済するための確定伝播路を復活経路と呼ぶとすれば，ある脱落点の救済に関る枝はすべてその脱落点の復活経路上に現れ，また脱落点は復活経路を２ずつ移動し，未検定点に到達することによって矛盾は解決される．復活経路は有向路であり，入力点と出力点は独立の点とみなされるから，通常の意味での初等的な路ではない．脱落点はつねにデッドロックパス上にあり，復活径路に沿って２ずつ移動して解決点に至ることでデッドロックパスの外に出る．（つまり，デッドロックの発生が止まる．）

■図23は図15のデッドロックマップ上の復活経路を図示するものである．①から始まり④に至る復活経路１は，点Ｐを最初は入力点として通過し，新脱落点③を経由して２回目には出力点として通過している．

■復活経路とは再検グラフＲ上の次のような有向路である．

① デッドロックマップの開始図式における脱落点を出発点とする単純な有向路である．

③ 枝の向き（極性）が交互に反転する．従って，入力点，出力点を交互に通過する．

⑤ 復活経路の終点はデッドロックマップの開始図式における未検定点である．

■有向グラフの枝の向きが交互に反転するような路を交代路( alternating path )と呼ぶ．復活径路は再検グラフＲの交代路である．確定パス（デッドロックパス）は定向路（向きの同じ枝のみからなる路）であるから，確定パス上には連続した交代路は存在しない．つまり復活径路はつねに確定枝と除去枝を交互に選択して進む路となる．

■すべての脱落点が解決点に至る復活経路を持つことができれば，復活確定セッションは必ず停止する．上述した救済不能なデッドロックが発生しないということは，すべての脱落点が最終的にデッドロックを解消することのできる復活経路を持つということを意味している．この復活経路は閉路を構成しないから，無限ループに陥ることなく必ず開始図式における未検定点であった解決点に至ることができる．

■また，もしこのような復活経路が存在しないとすればこのグラフは非ハミルトングラフであると考えてよいであろう．ここでは対象グラフはハミルトングラフであることを仮定しているので，すべての脱落点は必ず解決点に至る復活経路を持っているとしてよい．従って，この路を正しくたどることさえできれば，復活確定セッションは必ず停止する．

■有向グラフの点は接続する枝の向きによって同一の点がある場合には入力点となり，他の場合には出力点とみなされる．つまり，ひとつの点は同時に入力点ともなり出力点ともなる．復活径路は交代路であるからこの路の上にはつねに入力点と出力点が交代に現れるので，復活径路上には入力点であって同時に出力点であるような点は存在しない．従って，復活径路上では，ひとつの点Ｐを入力点と出力点というまったく独立した２点に分割して操作することが可能である．再検グラフＲのすべての点をこのように２相に分割してグラフの点数を×２したようなグラフＲ' を考えると，復活径路はグラフＲ' の単純な路である．

■復活径路がグラフＲ' の単純な路であるとすれば，ある脱落点を出発点とするすべての復活径路からグラフＲ' の部分木を構成することができる．この木はデッドロックを解消するための解決木となる木であるから，これを復活木と呼ぶことにしよう．再生変換は擬似的な世界時計によって無時間をシミュレートする方法であった．復活木は再検グラフから完全に静的解析によって構成可能であるから，これは真に無時間で完了する再検定プロセスがついに獲得されたことを意味するものである．

■上記したように，復活確定セッションは必ず停止する上に，自動確定セッションはそもそも存在しないということが明らかになったのだから，当然，再生変換は復活確定セッションの終結とともに必ず停止する．

■復活経路は一種の確定伝播路である．というより，確定伝播路の一部である．因子検定においては任意選択によって発生する自動確定の波＝確定伝播路の存在が非決定的なデッドロックの発生する原因となっていた．確定伝播のメカニズムによって検定を進めるという意味では再生変換のプロセスは因子検定ないし短絡グラフ法における自動確定と異なるものではない．ただ，時間を完全に凍結した状態でそれを行っているという違いがあるのみである．

○ 逸脱した再生パスの再検定を含む無時間検定は必ず停止する30

■デッドロックマップの範囲を逸脱するという現象は，上記したように再生パスの中にそれまでの未検定点が確定点となって繰り込まれることを意味しているから，無時間検定を繰り返すことによって再生パスの枝が接続する点集合には必ず少なくとも１個の未検定点が追加されるので，最後には再検グラフＲはグラフＧのすべての点を含むものとなる31．このとき，グラフＲはグラフＧに等しく，その上でデッドロックしない再生パスは当然グラフＧの中でもデッドロックしないから，このプロセスは必ず停止する．よって逸脱した再生パスの再検定を含む無時間検定は必ず停止する．

■このようにして，逸脱した再生パスの再検定を含む無時間検定によって，短絡グラフの確定パスのすべての継承点を含む拡大された再生パスをつねに得ることができる．

30 無時間検定は必ず停止するが，再生変換でロックアウトする場合についてはまだ未解明のところがある．

31 この記述はやや正確を欠いたものである．後述するように解決点となるべき未検定点を使用することなく矛盾を解決できる場合はあるが，一般にはデッドロック点と等しい個数の未検定点が必要であると考えられる．この意味では再検グラフのサイズが増大して，残り点数が少なくなってきたときの動作についてはやや，あいまいである．