拡張ダイクストラ法：波頭集合の作り方
波頭集合はステップベースじゃなくて、やっぱりコストベースのほうがいいみたいだ。ステップは、遷移グラフの辺を通るごとに1ステップと勘定する。コストは入力した（あるいは通過した）記号の数。無音遷移はステップ1でコスト0。
ある点からの次の波頭集合は、コスト1で行ける点の全体。ただし、コスト0で境界に行ければ、それはそれでよい。オートマトンの標準形として、長さ2以上の無音遷移パスがないようにしておけば、コスト1の波頭集合までのステップ数は1または2に限られる。オートマトンの決定性（無音遷移は非決定的だが有音遷移は決定的）から、中心＝波源から波頭までのコスト1放射線は一意に決まる。これは、球面を（ニュートン流に）粒子の散乱放出（爆発？）と考えていいことになる。各粒子の軌跡が確定的に（あるいは古典的に）決まる。
「球面波＝粒子群の炸裂」描像は局所的で、これを繋ぎ合わせ／寄せ集めると、決定性から古典軌道の束が描ける。局所的な情報から「粒子の古典軌道の束」の統計的量を作り出す操作がファインマン／クリーネ総和（有限離散的経路積分）。
具体的なアルゴリズムについても書いておく。
関係辺（模倣関係の要素）の集合を2つ考える -- 候補辺の集合Cと確定辺の集合D。オートマトンをM, Nとすると、CもDも |M|×|N| （状態の直積）の部分集合。初期値は、C={(s0, t0)}, D=空集合。候補辺のそれぞれに対してダイクストラ法を適用して、確定辺を増やし、次の候補辺の集合を求める。確定辺は、1回のアルゴリズム・ステップで1, 2 4本（のいずれか）ずつ増える。確定した候補辺はCから除外され、次の候補辺群がCに追加される。次の候補辺は、ダイクストラ波動の波頭集合（コスト1近傍の境界）から決まる。
ダイクストラ法を進めていくと、いずれは終境界まで達してしまう。終境界点での候補辺集合を記録してラウンド0を終える。ラウンドとは、ダイクストラ波動を1回走らせる試行のこと。ラウンド0の最後で得られた候補辺の集合を始境界側に移して、ラウンド1を始める。ラウンド1の開始点は、ラウンド0で到達した終境界の点を1つ選ぶ。
ラウンド0で通過した点はマークしておく。ラウンド1は、“ラウンド0で通過した点または終境界”に到着したら終了である。ラウンド2は、それまでのラウンドで到着して、まだやってない終境界の点を1つ選んで実行する。[追記]いや、この記述は間違っているな。正確には…、後で書く。[/追記]
終境界の点（始境界と考えても同じ）は有限個しかないから、ラウンドも有限回で終わる。すべてのラウンドによって得られた確定辺の蓄積が最大の模倣を与える。途中で失敗すれば、模倣不可能を意味する。ラウンドって概念は、実際には不要だと思う。今のところ、僕が考えやすいから使っている。アルゴリズムをキチンと書き下せば、ラウンドはなくなるハズだ。
遅延波の到着、あるいは同じことだが波頭が複数回の通過すること（多重掃過）をよく考えないといけない。遅延波を無視してはいけないが、有限回通過するうちに、必ず状況が完全に再現される。つまり、無限回の通過でも有限周期をもつわけだ。これはポンプの補題に対応する。
拡張ダイクストラ法の参考になったこと
妄想をたどるために使った概念や事実や定理：
- ブラーグマンクライン＆ウッド（Bruggemann-Klein - Wood）の1-非曖昧性（出発点）
- マクノートン／山田／グラシュコフの方法
- Hovlandアルゴリズム（ライバルとして）
- ホイヘンスの原理
- ダイクストラ法
- ファインマン／クリーネの総和公式
- 加法的トレースの概念（セリンガー）
- 長谷川の一様性原理
- 強・弱の双模倣、模倣の概念
- 結び目のマルコフの定理とその絡み目（タングル）版
- マルコフ・トレース
- マスロフ脱量子化
- コボルディズム圏
- 太鼓の形を聞き分ける話
ところで、長谷川真人さんの次の2つはいい読み物だ。
- 論説「再帰プログラムの意味論について」 http://www.kurims.kyoto-u.ac.jp/~hassei/papers/sugaku07.pdf
- スライド「再帰プログラムの幾何」 http://www.kurims.kyoto-u.ac.jp/~hassei/slides15sep06s.pdf
