半群

半群保留连续组合所需的最低结构。先把一串操作分成若干连续片段，各片段算出一个结果，再按原顺序组合，结果应与一次处理整串相同。字符串连接、矩阵乘法和状态转换都遵循这个规则。

“括号不重要”与“顺序不重要”是两回事。例如先写入状态再读取，与先读取再写入通常不同，但把三步过程的前两步或后两步封装为一个过程，不应改变整体含义。空过程需要额外指定单位元，撤销过程则需要更强的可逆性。

正整数在加法下构成半群，所需单位元 $0$ 不在集合中。正偶数在乘法下也构成半群：两个正偶数相乘仍是正偶数，结合律来自整数乘法。若它有单位元 $e$，由 $2e=2$ 必得 $e=1$，与 $e$ 为正偶数矛盾。

非空字符串在连接下构成半群。把三个片段 ab、c、de 送入不同计算树：左边先拼成 abc 再接 de，右边先拼成 cde 再接 ab 的后面，最终都得到 abcde。但交换前两个片段会得到 cabde，已经改变了输入顺序。这里连接后的字符串依然非空，所以每个中间结果都留在同一底集中。

结合性不能由交换性推出。在实数上定义 $a\ast b=(a+b)/2$，运算封闭且交换，但

通常减法也失败：$(5-3)-1=1$，而 $5-(3-1)=3$。

另一种极端是非空集合 $X$ 上的左零运算 $x\ast y=x$。两种括号都给出 $x$，所以它结合；当 $X$ 至少有两个元素时，它不交换，也没有双侧单位元。它还说明半群一般不能消去因子：任选不同的 $y,z$，都有 $x\ast y=x=x\ast z$。左因子 $x$ 会抹掉第二个输入，等式因而不能反推出 $y=z$；结合性本身没有承诺保存信息。

给半群加入双侧单位元就得到幺半群理路幺半群Monoid具有双侧单位元的半群。。若原来没有单位元，可添一个新元素 $e$ 并规定 $e\ast a=a\ast e=a$；这样空序列也有了乘积。再要求所有元素可逆，便进入群的范畴。

自动机读入一个词所产生的状态变换，可以按词的连接组合。有限状态集只产生有限多个这样的变换，因而半群和幺半群能把正则语言理路正则语言Regular language存在有限状态识别器的有限字语言，也就是只需固定有限种前缀摘要即可判断的语言。的识别转化为有限代数问题。区间聚合与并行前缀扫描理路并行前缀扫描parallel prefix scan · parallel scan · prefix computation用上扫归约和下扫传播在线性工作、对数深度内计算任意幺半群运算的全部前缀。同样依赖结合性：可改变计算树的形状，但对非交换运算必须保持叶子的原次序。动态规划理路动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。中的摘要合并只有在确实满足这一接口时才能如此重排；一般状态转移并不自动构成半群。