ベキ等半環の利用例

ローランド・バックハウス（ロランかもしれない；Roland Backhouse）が、加法的ベキ等半環について簡単なメモ（たぶん教材）を書いている。そのなかで例にしている半環は：

1. 言語の集合（例：正規集合の半環）
2. プログラムの二項関係モデル
3. ブール代数と可達性（Reachability）判定
4. Shortest Paths問題
5. Bottlenecks問題

Reachability、Shortest Paths、Bottlenecksはグラフ上の問題のようだが、よく知らない。

(N∪{+∞}, min, +)が狭義のtropical半環（min-plus代数）、これを実数にした(R∪{+∞}, min, +)（順序は普通と逆）はoptimization代数というのだそうだが、Shortest Paths問題に使うのだそうだ。Bottlenecks問題には、(R∪{+∞}, max, min)（順序は普通）を使うのだとか。そもそも、ボトルネックの解析ってどうやるんだ？

• →Exotic Semirings - 檜山正幸のキマイラ飼育記 メモ編