半环

形式陈述 ​

半环是五元组 $(S,+,\cdot ,0,1)$，其中 $(S,+,0)$ 是交换幺半群，$(S,\cdot ,1)$ 是幺半群，并且对任意 $a,b,c\in S$ 有

$$a(b+c)=ab+ac,(a+b)c=ac+bc,$$$$0a=a0=0.$$

本库允许退化情形 $0=1$。半环不要求加法逆元，也不要求乘法交换；若乘法交换，则称交换半环。含幺环在忘掉“每个元素有加法逆元”这一额外性质后给出半环，但许多半环并不能扩成同一底集上的环。

直觉 ​

半环保留有限求和与乘积所需的全部规则，却不强迫做减法。很多动态规划和路径算法只会把候选答案“合并”，再把相邻步骤“串联”；只要这两种运算满足分配律，就能像普通算术一样展开和重组，而无需人为引入负数。

加法的零元同时对乘法具有吸收性，使“没有方案”与任意后续组合仍然没有方案。乘法单位元则代表空路径、空词或不改变结果的组合步骤。

例子与边界 ​

自然数 $\mathbb{N}$ 配通常加法和乘法是交换半环，但不是环，因为正整数没有加法逆元。布尔半环

$$(\{0,1\},\vee ,\wedge ,0,1)$$

把加法解释为“存在某种选择”、乘法解释为“两个条件同时成立”；其矩阵乘法可计算图的可达性。热带半环

$$(\mathbb{R}\cup \{\mathrm{\infty }\},min,+,\mathrm{\infty },0)$$

则把“加法”解释为取更短路径、“乘法”解释为连接路径并累加长度。

半环与无幺环不是同一概念：前者有乘法单位元但可能没有加法逆元，后者有加法逆元却可能没有乘法单位元。若去掉半环的乘法单位元，还会得到 rng-like 或 hemiring 等不同约定，使用时必须另行说明。

推论与应用 ​

任意半环 $S$ 上都可定义矩阵加法与 Cauchy 型矩阵乘法，方阵组成半环 $M_n(S)$。形式语言的权重、自动机路径、动态规划和图闭包常通过选择不同半环复用同一算法骨架。向半环补入加法逆元得到其 Grothendieck 环化，但该过程会改变对象，不能把原半环中的减法当作已经存在。

参考资料

• Jonathan S. Golan, Semirings and Their Applications, Springer, 1999, Chapters 1–2.
• François Baccelli, Guy Cohen, Geert Jan Olsder, and Jean-Pierre Quadrat, Synchronization and Linearity, Wiley, 1992, Chapters 2–3.