研究揭示：唯一素因子分解不保证有限表示性，提出FSRP与PTLD新性质
arXiv论文通过36元素商实例证明唯一精确分解与有限相对表示性（FRP）可分离，引入FSRP和PTLD并给出多项式时间学习算法。
AI解读：这项研究直接冲击了形式语言理论中一个隐含假设：只要语言有唯一的素因子分解，就能用有限规则集描述它。作者用计算机穷举验证的一个36元素有限商构造出反例——每个非单位类都有唯一的精确素因子分解，但合法规则却包含无限族，因此唯一分解并不蕴含有限表示性。这个缺陷还被提升到非正则上下文无关语言，说明问题并非有限商特有。为了界定障碍范围，他们定义了FSRP（允许用有限状态控制器表示右侧语言）和PTLD（一种更强的确定性条件），并证明FRP严格弱于FSRP，而PTLD能保证二次规模的规则集。对理论计算机科学研究者，这意味着设计文法推断算法时不能依赖唯一分解作为有限性的代理指标；对机器学习领域，论文给出的正数据学习器能在多项式时间内更新假设并拥有有限特征样本，但适用于固定观察态射h下的PTLD表示，不是通用解决方案。普通读者无需行动，这项工作是纯理论进展，短期内不会直接影响任何应用系统。
9月3日提交至arXiv的论文《Relative Prime Factorization and Finite-State Presentations under Fixed Finite-Monoid Observation》中，作者Takayuki Kuriyama研究固定有限幺半群观察下的精确分解与规范表示，证明唯一分解不等于有限相对表示性（FRP）。
核心反例与缺陷提升
设L⊆Σ*并固定态射h:Σ*→M到有限幺半群。研究在相对语法同余θ_{L,h}:=≡_L∩ker h中区分唯一分解与有限直接表示。一个经穷举计算机验证的36元素商对每个活非单位类都有唯一精确素因子分解，但其合法素返回规则含无限族——因此即使对有限商，唯一分解也不蕴含FRP。
- 同一缺陷被提升到非正则上下文无关语言：该语言有无限相对商和有限素谱。
- 可复现验证代码及36元素见证的机器可读证书通过论文引用的固定GitHub快照提供。
新性质FSRP与PTLD
为隔离障碍，作者引入有限态相对表示性（FSRP），其中规范合法右侧语言由有限残差控制器表示，并证明FRP⊊FSRP。随后引入素目标左除确定性（PTLD），它蕴含唯一精确分解、尾精确性、尾确定性以及合法规则的二次界。
一个具有有限群观察器的非正则确定性上下文无关例子满足PTLD，但位于每个固定(k,ℓ)-可替换类之外。
学习算法
对固定h，论文给出规范PTLD表示的强正数据学习器，具有多项式时间假设更新和有限特征样本；并给出从弱行为正确CFG值学习器对规范FSRP控制器的极限重构。