半環
semiring。rig
More sophisticatedly, we can say that, just as a ring is a monoid object in abelian groups, so a rig is a monoid object in abelian monoids and a semiring is a monoid object in abelian semigroups, where abelian groups, abelian monoids and abelian semigroups have suitable monoidal structures (they are not the cartesian ones).
Equivalently, a semiring is the hom-set of a category with a single object that is enriched in the category of abelian semigroups.
半環は可換半群 (結合律 + 可換律) で豐饒化されたただ一つの對象を持つ圈の Hom である a semigroup is (the hom-set of) a semicategory with a single object;
半群 (結合律) はただ一つの對象を持つ半圈の Hom である a semiring is (the hom-set of) a semicategory enriched in Ab with a single object.
半環は Abelian 群 (結合律 + 單位律 + 可逆律 + 可換律) で豐饒化されたただ一つの對象を持つ半圈の Hom である 加法$ (R,+)が可換 monoid (結合律 + 單位律 + 可換律) である。單位を$ 0と呼ぶ 乘法$ (R,\cdot)が monoid (結合律 + 單位律) である。單位を$ 1と呼ぶ 分配律
左$ a\cdot(b+c)=(a\cdot b)+(a\cdot c)
右$ (a+b)\cdot c=(a\cdot c)+(b\cdot c)
加法$ +の單位 0 が乘法$ \cdotの吸收元である。$ 0\cdot a=a\cdot 0=0
例
環から加法$ +の可逆律を除けば半環となる。環の乘法$ \cdotは可逆でないから半環は逆元を考へない $ ({\rm max},+)代數の$ \rm maxを加法 (單位は$ -\infty)、$ +を乘法 (單位は$ 0) として$ \R\cup-\inftyを tropical 半環 (熱帶半環) と定義できる
$ \R\cup\inftyを$ ({\rm min},+)代數としても tropical 半環を定義できる
動的計劃法 (dynamic programming ; DP)
dynamorphism
recursion schemes
可換半環 (commutative semiring) とは乘法$ \cdotも可換な半環 乘法の單位$ 1が加法でも吸收的$ 1+a=a+1=1な可換半環は束である 冪等半環 (idempotent semiring。dioid) とは、加法が冪等$ a+a=aな半環 半順序を$ a\le b:=b=a+bと定められる。最小元は$ 0 束であれば$ a\le b:=a=a\cdot bとしても定められる 束では乘法も冪等である$ a\cdot a=a。冪等半環の乘法は可換とは限らない 例