结果族 134：Generalized star height at most three · 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
还是”星号套娃几层够用”的问题，这次的答案更狠：3 层。诀窍像切香肠：把一个长词切成首尾相接的小段，并规定任何一段都不许是另一段的开头，于是无论词多长，切法都唯一。靠着这本”唯一切分账”，论文把所有正则语言的星号嵌套深度压到 3 层封顶。
关键词卡片
看个具体例子
把 @@M@@ababbaab\cdots@@ 切成 @@M@@ab\,|\,abba\,|\,ab\cdots@@：只要每段都不是别的段的开头，整词就只会切出这一种片段序列；每段查一次账、更新一次状态，词的归属便定了。定理：任何正则语言 @@M@@L@@ 都满足 @@M@@h_\Sigma(L)\le 3@@，补在同一个 @@M@@\Sigma^*@@ 中取。
为什么值得关心
在此系列之前，人们甚至找不到一个广义星高大于 1 的具体语言，更没有绝对上界；本系列三个独立证明（界 13、4、3）互相印证，本篇的 3 是当前最强纪录。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读里的比喻是切香肠：一根长词按固定花样切成首尾相接的小段，且花样设计得让任何一段都不许是另一段的开头，于是切法唯一，每段各自记一笔”状态账”。把这幅图换成半数学说法：研究对象是字符串集合，表达式允许并、连接、取补与”重复任意遍”的星号；我们关心的量，是星号嵌套自身的深度。这篇论文的办法是先把长词的判读问题化归为”唯一切分后逐段查账”，再用低深度的表达式把查账过程整段写出来。
第二级台阶
用本科术语精确化。有限字母表 @@M@@\Sigma@@ 上全体字符串构成自由幺半群 @@M@@\Sigma^*@@。正则语言可等价描述为：取有限幺半群 @@M@@M@@ 与幺半群态射 @@M@@T:\Sigma^*\to M@@，语言是若干”取值落在指定子集”的字符串之并。前缀码是满足”任一成员都不是另一成员前缀”的有限词集 @@M@@E@@，它保证每个能切开的词只有一种 @@M@@E@@-切分；片段（episode）就是切出的成员，携带一次仿射更新——线性部分记状态如何转移，常数部分记一笔平移。广义星高 @@M@@h_\Sigma(L)@@ 定义如常：并、连接、补不增高，星加一，取最小值。
第三级台阶
定理 1.1 的语境：对每个有限字母表 @@M@@\Sigma@@ 与每个正则语言 @@M@@L\subseteq\Sigma^*@@，有 @@M@@h_\Sigma(L)\le 3@@，其中补在同一 @@M@@\Sigma^*@@ 中取。两个假设挡住两层麻烦：补的全集必须是原字母表上的全部字符串（换字母表会破坏高度守恒），且识别 @@M@@L@@ 的有限幺半群完全一般——不交换、不幂零也可。结论是说，把词按前缀码唯一切开、逐段做仿射账目更新后，整条”查账语言”只需两次分裂（外层处理常规片段、内层处理例外片段），星号嵌套便停在 3 层；有限参数可依赖语言，但层数是绝对常数。
本文证明：任何正则语言都可用嵌套星号至多 3 层、允许取补的广义正则表达式在原字母表上写出。这是广义星高问题一致有界性当前已知的最强上界，用”词片段前缀码 + 任意函数移位表 + 全模板解码器”仅两次分裂即达成。
广义星高问题（generalized star-height problem）问：允许并、连接、星号与取补后，表达所有正则语言需要多深的星号嵌套。星高零即星自由语言，由 Schützenberger 定理（1965）用非周期有限幺半群刻画。普通星高有 Dejean–Schützenberger（1966）的无界下界，但加入补后失效。星高一的正面结果散见于有限交换群（Henneman）、二类幂零群（Pin–Straubing–Thérien 1992）、固定因子计数模 @@M@@n@@ 的语言（Bourne–Ruškuc 2016；Bourne 2017 推广到任意固定因子）等受限族，均不含任意正则语言。Straubing（2002）把”是否存在绝对上界”与”高度一是否总够”列为两个不同问题；直到近年综述仍没有已知广义星高大于一的语言。本族三篇论文分别给出 13、4、3 的绝对上界，本文给出最强的一个。
定理 1.1：对每个有限字母表 @@M@@\Sigma@@ 与每个正则语言 @@M@@L\subseteq\Sigma^*@@，有 @@M@@h_\Sigma(L)\le3@@，其中补在同一个自由幺半群 @@M@@\Sigma^*@@ 中取。有限参数与表达式长度可依赖于语言，但嵌套层数被绝对控制；论文不给表达式规模或运行时间的界。核心技术是把有限幺半群计算表达为一组词片段（前缀码）上的仿射更新，配合对任意函数都成立的移位表（shift table）与覆盖全部候选切分的”全模板”（whole-stencil）解码器，使整条递归只需要两次分裂。
先归约到有限幺半群态射 @@M@@T:\Sigma^*\to M@@，让 @@M@@M@@ 忠实右作用于 @@M@@V=\mathbf F_2^M@@（基向量 @@M@@e_m@@ 满足 @@M@@e_md=e_{md}@@）。把词切成片段（episodes）构成前缀码 @@M@@E@@，切分唯一；每段携带一个仿射更新。分裂恒等式把”段序列的图语言”化为高度 @@M@@\max\{2,H+1\}@@ 的表达式，条件是前缀/后缀测试对独立成功配对可靠、对非跳过段可用；仿射恢复用 @@M@@g_w(v)-g_w(0)@@ 提取线性部分，齐次提升 @@M@@(v,c)\mapsto(vL+c\gamma,c)@@ 把仿射映射变成线性映射，都不加星号。第一步（外层分裂）处理大多数片段：标签（tags）记录状态、区间乘积与指标，时钟限制前后缀能共同实现的标签对——要么一致，要么恰有一对不等，后者由按段定义的仿射平移吸收；一致时若有标记边界，用移位表让乘积元组中一个坐标对传递的输出无关（前缀查早期乘积、后缀查后期乘积、有限证书检查跨界乘积的每个可能值），若某标记缺失，则用有限幺半群中幂的终归周期性让切口穿过全部时钟剩余类而前缀乘积不变。关键的移位表引理对任意函数 @@M@@f:A^l\to\operatorname{End}_{\rm lin}(S)@@ 成立：存在只依赖 @@M@@|A|,|S|@@ 的 @@M@@l@@，使每个 @@M@@f@@ 都有校正 @@M@@\beta_f@@，让每组输入与元组各有一条常值坐标线——其证明是把 @@M@@\beta@@ 视为独立随机向量、用 Erdős–Lovász 相依图方法避免所有坏事件。第二步（内层分裂）处理时钟与标记条件失效的例外片段集 @@M@@D@@：在片段早期放置含 @@M@@\mu@@ 份副本的模板（stencil），后缀把每个候选起点 @@M@@\tau_{p'}=k+L-p'@@ 的异常谓词当作”见证”来唯一解码真起点——大、小两级末端搜索的配合保证真见证在唯一性判定前不被误删，而对全模板中假起点的计数（末端不稳至多 4 对、每个固定锚点时钟部分至多 @@M@@c_{\rm cl}\log(2m)@@ 对、每锚点每标签内部标记失败至多 3 对）得出总数小于 @@M@@\mu@@，故每种元数据都有可用副本；随后后缀用一个对每个假设前缀乘积 @@M@@m'\in M@@（含不可行值）都有定义的总表 @@M@@\psi_e@@ 完成传输，其线性部分恰是原更新的齐次提升。高度计数：内层分裂从空跳过类出发得 2，布尔恢复后作为外层分裂的跳过类得 3。编译阶段每个成分至多一段无界周期延续，落入模板 @@M@@ac^ib@@、数据终归周期，故高度至多一；尾部 @@M@@F=\neg(E\Sigma^*)@@ 高度一，最终语言为 @@M@@\bigcup_{df\in S}A_dF_f@@。
本文验证状态为未形式化：主结果尚无 Lean 证明，请以社区核验为准。同族姊妹篇（界 13 的预测—历史方法、界 4 的多尺度输运方法）与本篇共享分裂恒等式、仿射恢复与标记—周期性原理，三者各自完整、互不引用对方数值定理，构成同一结论的多重独立验证。依照 OpenAI 官方声明，未经形式化的结果可能有问题，本文构造规模巨大且技术繁复，正式采信前宜等待同行评议。
问 1：本篇压到 3 的支点是哪一步，它最脆弱吗？
答：支点是移位表引理——对任意函数 @@M@@f:A^l\to\operatorname{End}_{\rm lin}(S)@@，存在只依赖 @@M@@|A|,|S|@@ 的 @@M@@l@@，使每个 @@M@@f@@ 都有校正 @@M@@\beta_f@@ 让每组输入与元组各有一条常值坐标线；其存在性用把 @@M@@\beta@@ 视为独立随机向量、以 Erdős–Lovász 相依图避开所有坏事件的论证。整条链上”对任意函数都成立”的普适性正是它比姊妹篇（界 4）多压一层的原因，也是概率论证若失效最先塌的地方。
问 2：内层分裂里”假起点计数 < 副本数 @@M@@\mu@@“为什么是全篇最脆的计数？
答：内层要处理时钟与标记条件同时失效的例外片段集，靠含 @@M@@\mu@@ 份副本的模板解码真起点；证明需逐类数清假见证（末端不稳至多 4 对、每锚点时钟部分至多 @@M@@c_{\rm cl}\log(2m)@@ 对、内部标记失败至多 3 对）并验证其总数小于 @@M@@\mu@@。这是典型的多来源计数拼合，任何一类漏数或边界差一，唯一解码就不再保证，第二次分裂失效。
问 3：前缀码真的保证切分唯一吗，这个假设能去掉吗？
答：能成立但依赖”任何片段不是另一片段开头”这一定义性约束，剩余不能开段的尾巴由补运算 @@M@@\neg(E\Sigma^*)@@ 单独处理、高度至多一。若放松为一般码，切分歧义会直接破坏”每段一笔账”的账目对齐；论文没有讨论非前缀码变体。
问 4：与已有工作相比真正的新意是什么？
答：此前所有星高一结果都限于特殊幺半群族（有限交换群、二类幂零群、固定因子计数模 @@M@@n@@ 等），且学界连一个广义星高大于一的具体语言都未找到；本篇与同族另两篇（界 13、界 4）首次给出任意正则语言的绝对上界，本篇用”任意函数移位表 + 全模板解码器”只两次分裂达到 3，按论文自述三篇互不引用对方数值定理，是独立的多重印证而非递进改良。
问 5：AI 生成证明在这类构造上最典型的出错模式是什么？
答：巨大而未显式化的有限选择与逐案计数的组合。校正 @@M@@\beta_f@@ 的存在性是概率式存在论证、总表 @@M@@\psi_e@@ 需对每个假设前缀乘积（包括不可行值）都有定义、两次分裂之间还要做齐次提升 @@M@@(v,c)\mapsto(vL+c\gamma,c)@@ 的簿记——这些环节各自正确不等于拼起来正确；论文自述不给出表达式规模界，人工复核几乎只能抽查。
问 6：结果落地后谁受益，能推什么？
答：自动机理论与描述复杂性社区。它把 Straubing（2002）所列”是否存在绝对上界”从开放变为肯定，把纪录钉在 3；它与”高度一是否总够”之间仍隔着两层，论文未讨论往下压的技术障碍，也未给任何算法应用。最自然的下游是重燃对高度一猜想的攻击与对星高大于一实例的搜索。
总评
若构造无误，这是广义星高问题半个多世纪以来最强的绝对上界，且与两篇姊妹篇构成罕见的独立多重验证；最大风险在于全篇依赖的精细计数与存在性选择未被形式化，当前完全依赖人工核验。