问题
伪簇(pseudovariety)是有限半群的类,对商、子半群、有限直积封闭(例:A = aperiodic 类、J = J-平凡类、R、DA…)。对伪簇 V 与有限半群 S,点态集 PV(S) ⊆ S 是 «在 V 的意义下不可分» 的元素集:元素 x ∈ PV(S) 若 x 到 V 的 «因子» 们 «点态不可分»——精确定义涉及 «relational morphism»(S → V 的多值同态)。Henckell 定理(1988):对 J(及 aperiodic 型伪簇),点态集有显式刻画且可判定—— «有限半群论的深度定理»(Ash 的证明、Henckell–Rhodes–Sapir 的后续)。问题:整个伪簇格上的 «可判定地图»:哪些伪簇的点态集可判定?Place–Zeitoun 等解决了 R、DA、L 等, «地图» 远未画完。它与电路复杂度(AC⁰ 的代数刻画,22 号)直接挂钩:A 的点态集判定 ⟺ «star-free 语言的正则前缀» 类的判定。
主要概念
relational morphism 与点态可分
relational morphism τ : S ↠ T:把 S 的每个元素映到 T 的非空子集,满足 τ(s)τ(t) ⊆ τ(st) 且每处非空。元素 x ∈ S 称 V-点态:存在 relational morphism τ : S → T(T ∈ V)与 t ∈ T 使 τ⁻¹(t) 含 x 且 «V 的分辨率» 意义下 x 与 τ⁻¹(t) 的全体元素不可分——技术定义(点态可分的精确口径)见 Henckell–Rhodes–Weil 的标准形式。可判定:给定乘法表,计算 PV(S) 的算法存在。
J-序与 Henckell 的显式刻画
Green 关系:x ≤𝓙 y ⟺ x ∈ SyS(双主理想包含);J-平凡半群 = 𝓙 只有一类。Henckell 刻画:对 J-平凡伪簇 J,点态集由 «Z-序»(乘法组合的传递闭包)显式给出,判定算法多项式;A(aperiodic)的点态集由 Ash 的幂等图定理刻画——Hall 定理式的组合核心(12 号命题 1 的 Green 序是其基础)。
主要命题与证明
命题 1(Green 双主理想序的基础性质;完整证明) 有限半群 S 中:x ≤𝓙 y ⟺ x ∈ SyS;≤𝓙 是前序(自反、传递),其等价类是 𝓙-类;乘法降序:对一切 u,v(含空侧)有 uxv ≤𝓙 x。
证明 自反:x ∈ SxS(约定允许空积;严格半群加外单位不改变 𝓙 结构)。传递:x = ayb、y = czd ⟹ x = (ac)z(db) ∈ SzS。等价类:𝓙 定义为双向 ≤。降序:uxv = u·x·v ∈ SxS,即 uxv ≤𝓙 x。□
命题 2(乘法降序与 J-平凡判定;完整证明) (i)对一切 u,v ∈ S(含空侧),uxv ≤𝓙 x。(ii)有限半群 S 是 J-平凡的 ⟺ 一切生成元的 «双乘闭包» 里每个元素恰由自身 𝓙-代表——判定算法:计算 ≤𝓙 的矩阵(乘法表的传递闭包,O(n³)),检查所有 𝓙-类单点。
证明 (i)uxv = u·x·v ∈ SxS ✓。(ii)𝓙-类的计算:≤𝓙 由 «x ∈ SyS» 的布尔矩阵(乘法表直接给出 «x 是否被 a,b 生成»)做传递闭包;等价类 = 双向 ≤ 的对;检查每类是否单点。复杂度:O(n³) 的标准传递闭包。□
命题 3(Henckell 定理与可判定地图;文献口径陈述) (i)Henckell(1988):J(与相关 aperiodic 伪簇)的点态集可判定,显式 «Z-序» 刻画;Ash(1991)给出幂等图定理的独立证明( «relational morphism 的 «幂等提升»»)。(ii)Place–Zeitoun(2010 年代):R、L、DA 及若干 «绿书» 伪簇的可判定性逐个解决(工具: «转移的 «层析»» 与 «ω-自动» 技术)。(iii)开放:伪簇格上 «可判定/不可判定» 的分界——没有任何 «不可判定» 的反例已知( «全部已知点态集都可判定» 与 «没有统一算法» 之间的张力); «地图» 的完成等价于 «正则语言前缀层级» 的完整代数刻画(22、25 号的联合空白)。
现状说明 Henckell–Ash 定理的 «组合核»(幂等图 + Hall 型配对)为每个新伪簇提供了 «模板»,但每个伪簇的 «适配» 都是独立攻坚( «J 的论证不能用两次»)。 «统一判据» 的存在性本身开放——这使 24 号成为 «地图上有整个未勘探大陆» 的典型条目。□
进展与文献
Henckell《Pointlike sets: the finest aperiodic hierarchy》(1988);Ash《Inevitable sequences and the Krohn–Rhodes theorem》(1991,幂等图定理);Place–Zeitoun 的点态集系列(2013–2019);Rhodes–Steinberg《The q-theory of Finite Semigroups》(专著,现代框架)。开放核心:可判定地图的完成; «统一算法» 的存在性;与 22、25、45 号的联合谱。