半环

半环把“合并候选方案”与“串联两个步骤”放到同一接口中。加法负责合并，所以不依赖候选排列；乘法负责串联，所以可以依赖先后顺序。分配律表示先合并再串联，与分别串联后合并得到相同结果。

$0$ 表示没有方案，和后续任何方案串联仍是没有方案；$1$ 表示什么都不做的空步骤。这两个符号按运算角色命名：在最短路模型中，无路线的代价 $\mathrm{\infty }$ 充当 $0_S$，空路线的代价 $0$ 充当 $1_S$。

通常自然数 $(\mathbb{N},+,\times ,0,1)$ 是交换半环，正数没有加法逆元。布尔半环 $(\{0,1\},\vee ,\wedge ,0,1)$ 则把合并理解为“至少一个成立”，把串联理解为“二者都成立”。它满足 $1+1=1$，不会保留方案个数。

热带半环为

其中规定 $a+\mathrm{\infty }=\mathrm{\infty }+a=\mathrm{\infty }$。例如先走长度为 $4$ 的边，再从长度 $3$ 与 $7$ 的后续路线中择优，有

这就是分配律在路径语言中的含义。没有路线的代价 $\mathrm{\infty }$ 对串联吸收，而空路线长度 $0$ 不改变总长。

加上负数会改变幂等加法的结构。若把布尔等式 $1+1=1$ 送入一个环，减去 $1$ 就得 $1=0$，因此保持加法和单位元的映射会把整个布尔半环压成零环。相反，自然数的加法有消去律，其环化得到整数，并保留原来的自然数。

半环上的方阵仍组成半环，矩阵乘法为 $(AB{)}_{ij}=\sum _k{A}_{ik}{B}_{kj}$。若 $A_{ij}$ 表示从 $i$ 到 $j$ 的边权，则 $A^2$ 汇总恰好两条边的行走，$A^k$ 汇总恰好 $k$ 条边的行走。布尔半环计算是否存在，通常自然数半环计算数量，min-plus 半环计算这些行走的最小总权重。例如两条两步路线的边权分别为 $2,5$ 与 $4,1$，对应条目是 $min(2+5,4+1)=5$。

有限有向无环图只有有限多条路径，动态规划公理库动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。可按拓扑顺序汇总它们。有环图的行走长度则可能任意增长。例如从起点可达、且还能通往目标的负权环，每多绕一圈都会降低总权重，使该目标的最短路公理库最短路问题Shortest-path problem在有限有向实权图中寻找源点到各顶点的最小有向游走成本。代价没有有限最小值。这时问题涉及任意长行走的极限，而普通半环只定义有限次加法。

查询来源与半环标注公理库查询来源与半环标注Query provenance · Provenance semiring · K-relation · 查询溯源用有限支撑的半环标注关系记录查询见证，证明来源多项式的通用求值性质，并计算重数、事实删除与最小见证击中集。把同一结构用于有限关系查询：连接将共同使用的事实标注相乘，投影把替代见证相加。先在自然数系数多项式半环中保存结果，再通过同态求值，就能从同一份来源得到输入重数下的见证数、布尔存在性或删除事实后的答案；关键条件是交换含幺半环与有限正查询。

形式语言中的加权有限自动机公理库加权有限自动机Weighted finite automaton · Weighted automaton · WFA · 加权自动机在半环中沿匹配输入的路径顺序乘权、跨候选路径加权，把每个有限字映射为一个值的有限状态模型。把路径串联和候选合并交给两种运算，并按输入字母逐步求值；同一个 aab 示例可分别算出带重数的计数、最小代价与存在性。代数上，对加法交换幺半群做 Grothendieck 群完备化，再用分配律将乘法延拓到形式差，就得到通用环化；上面的自然数与布尔半环展示了它分别保留信息和合并信息的情形。