半環係数行列とその応用

グラフの頂点数と同じサイズの正方行列を計算する。頂点付値、辺付値がある。

1. {0, 1}半環 可達性
2. min-plus代数 コストの最小化（例：距離、運送費用）
3. max-plus代数 ゲインの最大化（例：金貨拾い問題）
4. max-times代数 乗法係数の最大化 （例：氷運搬問題）
5. 言語半環 オートマトン

頂点付値はある種のポテンシャルで、頂点付値の全体はアフィン空間かベクトル空間（のようなもの）になる。辺付値が時間発展の生成子行列で、頂点付値の空間にendomorphismとして働く作用素になる。

辺付値の空間がアフィンまたはベクトル空間で、付随するベクトル空間になにか内積のようなものがあれば、初期状態がxで観測子がyであるような時間発展における観測量の推移は

• φ(t) = <E(A, t)x|y>

と表現できる。Eがクリーネ指数関数（I + A + AA + ...）なら、φは単調増加する。