ステージ付き遷移系

状態空間Sが、インデックス集合Iでインデックスされた部分集合族{S_i}で覆われているような状況を考える。S_iをステージと呼び、Iはステージ記号の集合と考える。被覆は分割でなくてもよい。

この用語は以前から使っていたもので、実務上必要だった。が、どうも理論的にも必要そうだ。状態遷移系上のアクションラベルの集合（アルファベット）を考えると、ステージがないと、どうもまずい。

ステージ記号の集合I上で、I×Iでインデックスされた記号集合の系を考える。i, j∈I×Iに対して、Σ(i, j)を考えるわけ。(x, a, x')が合法な遷移である条件として

• x∈X_i、x'∈X_j、a∈Σ(i, j)

を要求する。X_i達をまた状態空間と考えれば、Σ(i, i)とX_iで状態遷移系が構成できる。x≠j のときは、別な空間にジャンプする遷移。

記号0が開始状態、記号1が終了状態を表すとして、Σ(i, 1)とΓ(0, j) にだけ連接を認めてΣとΓの合成アルファベットを定義できる。とりあえず、ステージ記号の集合として {0, *, 1}だけを取り上げてもいい。それぞれ、開始状態、終了状態、その他の状態となる。

非決定性の扱いが難しそうだが、大きな状態空間の分割、集約（状態集合を点とみなす）、合成などは実務的にも重要だ。

素朴な定式化でうまくいかない事情に対して、次のことを試してみる価値がある。

1. 無音記号を考える
2. ワープ辺（入力なしで勝手に遷移する遷移辺）
3. アルファベットのコスパンの圏
4. アルファベットの写像に伴う遷移系の引き戻しと前送り