arXiv:2608.18813cs.FLcs.AI2026-08
改进了$O_2$为多上下文自由语法的因子分解刻画。
A strengthening of the MCFL-ness of $O_2$
- 基于字符串元组的因子分解，提出更强的刻画方式。
- 相较已有定理，提升了对因子分解结构的约束力。
- 适合关注形式语言与语法理论的读者。
近年来，关于$O_2$是多上下文自由语法（MCFG）的证明陆续出现，这些成果在计算语言学与计算代数领域具有应用价值。本文聚焦于近期以字符串元组因子分解形式给出的证明，提出一个更强的因子分解刻画结果，优于现有定理。该结果深化了对$O_2$语法结构的理解，为相关理论研究提供更精细的工具。
原文摘要 · Abstract (English)
In the last years, a number of proofs of the fact that $O_2$ is a multiple context-free grammar (MCFG) were given. Such results can be exploited in the fields of both computational linguistics and of computational algebra. Here, we focus on a recent such proof spelled in terms of factorizations of string tuples, and give a new result with a stronger characterization of such factorizations than in existing theorems.
形式语言语法理论逻辑
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。