论文标题
$ o_n $是$ n $ -mcfl
$O_n$ is an $n$-MCFL
论文作者
论文摘要
正式语言中的交换性能在计算机科学，计算语言学和计算群体理论的边界构成问题。这种突出的问题是语言$ o_n $的位置，即包含相同数量的字母$ a_i $和$ \ bar a_i $的语言，$ 1 \ leq i \ leq i \ leq n $，在已知的正式语言中。最近已经证明$ o_n $是一种多种无上下文语言（MCFL）。但是，Nederhof的更精确的猜想是，$ o_n $是尺寸$ n $的mcfl。我们提供了这一猜想的两个证据，都依赖于代数拓扑的工具。在途中，我们证明了项链分裂定理的一种变体。
Commutative properties in formal languages pose problems at the frontier of computer science, computational linguistics and computational group theory. A prominent problem of this kind is the position of the language $O_n$, the language that contains the same number of letters $a_i$ and $\bar a_i$ with $1\leq i\leq n$, in the known classes of formal languages. It has recently been shown that $O_n$ is a Multiple Context-Free Language (MCFL). However the more precise conjecture of Nederhof that $O_n$ is an MCFL of dimension $n$ was left open. We present two proofs of this conjecture, both relying on tools from algebraic topology. On our way, we prove a variant of the necklace splitting theorem.
