言語処理系で講義でクリーネの不動点定理をやった時にベルマンフォードの証明にも使えるなぁと思ったので紹介します。 クリーネの不動点定理 を完備半順序集合とし、 をその上のスコット連続写像とする。このとき、 は最小不動点を持つ。 ここで、完備半順序集合とは最小元 を持ち、任意の有向部分集合 について の上限 が存在する半順序集合とします。 が有向集合であるとは任意の についてある元 が存在して が成り立つこととします。 が 上のスコット連続写像であるとは、 の任意の有向部分集合 について が成り立つこととします。 何言ってんだコイツと思った人もブラウザバックを早まらないでください。 あとで有限半順序の場合を紹介しますが、有限の場合は簡単で、ベルマンフォードの証明に応用するのはそこだけで十分なので、意味がわからないひとは少しスクロールしてみてください。 とりあえず一般の完備半順序集合についてクリ
1リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く