结果族 134：Generalized star height at most three · 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
正则表达式里的星号 @@M@@(\cdots)^*@@ 表示”重复任意遍”，而且可以套娃：@@M@@((a)^*)^*@@。星高就是套娃层数。如果在并、连接、星号之外还允许”取补”（否定），套娃会不会想套多深就套多深？本文给出绝对天花板：任何正则语言 13 层一定够——此前人们连”有没有天花板”都不知道。
关键词卡片
@@M@@\Sigma^*@@ 取补之后的星高。看个具体例子
看补运算的威力：语言 @@M@@a^*b^*@@ 用星号写星高为 1，但它也等于 @@M@@\neg(\Sigma^*\,b\,\Sigma^*\,a\,\Sigma^*)@@，其中 @@M@@\Sigma^*=\neg\varnothing@@ 不花星号——取补有时能把星号完全消掉。定理则保证最坏情形也封顶：@@M@@h_\Sigma(L)\le 13@@ 对一切正则语言 @@M@@L@@ 成立，证明思路是把幺半群计算写成 @@M@@v\mapsto vA+b@@ 的仿射更新，再经十二次分裂构造复原（层数路径 @@M@@0\to2\to\cdots\to13@@）。
为什么值得关心
广义星高是 1960 年代起的经典公开问题，此前人们甚至找不到一个广义星高大于 1 的具体语言；”存在绝对常数上界”是定性层面的重大进展。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读里的”套娃”与”黑白反转”翻译过来：对象是由并、连接、星号（重复任意遍）和取补四种原料搭成的正则表达式，星高就是星号套星号的层数；取补像黑白反转，不新开一层。问题问：允许取补之后，最坏情形的套娃深度有没有一个与字母表、语言、机器规模都无关的绝对天花板？
第二级台阶
本科术语化：正则语言由有限自动机识别，其转移幺半群 @@M@@M@@ 连同态射 @@M@@T:\Sigma^*\to M@@ 是语言的代数画像。星高指 Kleene 星号的嵌套深度；再允许对 @@M@@\Sigma^*@@ 取补即得广义星高 @@M@@h_\Sigma(L)@@。经典锚点：星高为零的语言恰是星自由语言，由非周期幺半群识别（Schützenberger 定理）；而普通星高在二元字母表上无界（Dejean–Schützenberger），但这些下界一旦允许取补便失效。
第三级台阶
定理的语境：对每个有限字母表 @@M@@\Sigma@@ 与每个正则语言 @@M@@L\subseteq\Sigma^*@@，都有 @@M@@h_\Sigma(L)\le13@@，表达式直接建在原字母表上，补运算对同一个 @@M@@\Sigma^*@@ 取；13 不依赖任何参数。论证骨架：把 @@M@@M@@ 的计算表示为仿射更新 @@M@@v\mapsto vA+b@@，经恰好十二次分裂构造复原，层数沿 @@M@@0\to2\to\cdots\to13@@ 攀升。”表达式长度不作有用估计”挡住了对构造实用性的过度期待；结论肯定回答了广义星高问题的一致有界性版本——天花板存在。
本文证明：任何正则语言（regular language）都可用嵌套星号至多 13 层、且允许取补运算的广义正则表达式写出，星号嵌套层数有一个与字母表和自动机规模无关的绝对上界，从而肯定回答了广义星高问题（generalized star-height problem）的一致有界性版本。
正则表达式的”星高”（star height）指 Kleene 星号的嵌套深度。若在并、连接、星号之外再允许对 @@M@@\Sigma^*@@ 取补，得到的就是广义星高 @@M@@h_\Sigma(L)@@，这是自 1960 年代起悬而未决的经典问题。普通星高方向已有坚实基础：Eggan（1963）将其联系到转移图的圈结构，Dejean 与 Schützenberger（1966）证明二元字母表上普通星高无界；但这些下界在允许取补后不再适用。星高为零的语言由 Schützenberger 定理（1965）刻画为恰被非周期有限幺半群（aperiodic monoid）识别的星自由语言（star-free languages）。星高一的结果覆盖交换群（Henneman）、二类幂零群（Pin–Straubing–Thérien 1992）等代数族，但都限于特定识别类。真正卡住的是任意有限幺半群的一致界：此前既不知是否存在绝对上界，也不知道高度一是否总够用——Straubing（2002）明确区分了这两个问题，而直到 Place–Zeitoun（2017）的综述，人们甚至找不到一个广义星高大于一的具体语言。
定理 1.1：对每个有限字母表 @@M@@\Sigma@@ 和每个正则语言 @@M@@L\subseteq\Sigma^*@@，都有 @@M@@h_\Sigma(L)\le 13@@。这里的表达式直接建立在原字母表 @@M@@\Sigma@@ 上，补运算对同一个自由幺半群 @@M@@\Sigma^*@@ 取；上界 13 不依赖于 @@M@@\Sigma@@、@@M@@L@@ 或识别自动机的状态数。论文对表达式的长度和其中有限对象的大小不作任何有用估计——关键只是嵌套层数被绝对地控制。这一构造通过把有限幺半群计算表示为仿射更新（affine updates），再经过恰好十二次分裂构造（split constructions）复原而得。
先做标准的代数归约：取 DFA 的转移幺半群 @@M@@M@@ 与态射 @@M@@T:\Sigma^*\to M@@，只需为 @@M@@T@@ 的每个纤维造低星高表达式。把 @@M@@M@@ 忠实地线性作用在向量空间 @@M@@\mathbf F_2^M@@ 上，然后将词切分为”片段”（episodes）——它们构成前缀码（prefix code），故切分唯一——每个片段携带一个仿射更新 @@M@@v\mapsto vA+b@@。核心是分裂恒等式：把片段切成前缀测试 @@M@@P_x@@ 与后缀测试 @@M@@Q_y@@，若每个独立成功的配对都恰好消费一个片段并传递更新（可靠性），且每个非跳过片段对每个输入都存在成功切分（可用性），则片段序列的图语言（graph language）可写为高度 @@M@@\max\{2,H+1\}@@ 的表达式；而仿射恢复引理说明线性部分等于 @@M@@g_w(v)-g_w(0)@@，可用有限布尔运算提取，不加星号。难点在绕开两侧都读不到的区间乘积与计时不确定性。本文用三套机制：其一，有限时钟（finite clock）保证在同一总长剩余类下独立成功的标签要么一致、要么恰有一对固定的偏差对，后者被一次仿射校正吸收；其二，预测试验（prediction trials）把片段按固定分点预测各段幺半群乘积，两个”理想合格”块迫使整体乘积等于预测乘积（只用乘法结合、不用消去），完美预测为每个输入提供切分，局部标记（Krieger 型标记引理）选定试验边界，标记缺失时周期性让切分沿周期区域滑动——这是两次外层分裂；其三，可用性的失败归结为五种显式残差类型，每类用两次对齐分裂处理：在模板里放置每种所需切分的大量副本，后缀检查所有候选起点并识别唯一真起点，对歧义有序对的计数保证总剩一个可用副本，而完整决策历史（full decision history）使两次分裂在更大空间上算出同一仿射更新。十二次分裂后高度恰为 13（@@M@@0\to 2\to\cdots\to 13@@）。最后编译：片段结束规则使每个成分语言只有一段无界周期延续，落入模板 @@M@@ab^jc@@，一切数据在 @@M@@j@@ 上终归周期（ultimately periodic），故高度至多一；未成片段的尾部 @@M@@F=\neg(E\top)@@ 同样高度至多一，最终语言为 @@M@@\bigcup_{mn\in A}L_mF_n@@。
本文属 OpenAI 星高系列三篇之一，验证状态为未形式化，即主结果尚无 Lean 形式化证明，请以社区核验为准。姊妹篇分别用多尺度周期输运与移位表方法给出更强的数值界 4 与 3，但按论文自述，三篇各自独立完整，本篇 13 的证明（预测试验加完整决策历史）没有被更强界取代，其每个局部引理均在文中自行证明。依照 OpenAI 官方声明，未经形式化的结果可能有问题，读者引用前宜等待同行评议。
问 1：证明中最脆弱的一步是什么？
答：可用性方向的残差分类。可靠性（每个独立成功的配对恰消费一个片段并传递更新）相对可控；可用性要求每个非跳过片段对每个输入都存在成功切分，论文把失败归结为五种显式残差类型、每类用两次对齐分裂处理，靠歧义有序对的计数保证总剩一个可用副本。若分类漏掉一种构型，某个输入将无切分可用，高度 13 的链条断在中间。
问 2：13 这个数是逼近最优，还是纯粹构造的产物？
答：纯属构造产物：十二次分裂、每次加层，恰好堆到 13。姊妹篇用多尺度周期输运与移位表方法分别得到 4 与 3。真正的下界几乎空白——至今没有一个已知语言被证明广义星高超过 1，本文也未提供。
问 3：一致上界与”高度一总够用”是同一个问题吗？
答：不是，Straubing 2002 年明确区分了二者。本文只肯定回答前者：存在绝对常数；后者（是否 @@M@@h_\Sigma(L)\le1@@ 恒成立）依然完全开放——连一个反例都找不到。
问 4：与已有工作相比真正的新意是什么？
答：Eggan、Dejean–Schützenberger 的无界性针对普通星高，取补后失效；Schützenberger（星自由）、Henneman、Pin–Straubing–Thérien 只覆盖特定代数类。本文首次对任意有限幺半群给出一致界，方法是仿射更新加十二次分裂，全新且自足。
问 5：AI 生成证明最可能出错的模式？
答：这类多层分裂构造的典型风险是”计时漂移”：有限时钟保证同一剩余类下标签要么一致、要么恰有一对固定偏差，预测试验与完整决策历史必须逐层同步；一处周期性滑动的边界处理不当，两层分裂就会算出不同的仿射更新。本文未经形式化，只能靠人工重放构造核验；幸运的是姊妹篇用不同方法独立证得更好数值界，为”天花板存在”提供了旁证。
问 6：谁会用到它？
答：代数自动机理论方向的定性突破：它把广义星高问题从”是否有界”推进到”求更小常数”；对表达式复杂度与描述复杂度研究，这是基线性质的定理。
总评
它终结了”广义星高是否有一致上界”六十年悬案，定性意义大于数值；最大风险是未经形式化的十二层分裂构造中残差分类与计时的完备性，且 13 很快被姊妹篇的 4 与 3 在数值上超越——本篇的价值在方法与自足性。