论文标题
解析作为提升问题和Chomsky-Schützenberger代表定理
Parsing as a lifting problem and the Chomsky-Schützenberger representation theorem
论文作者
论文摘要
我们首先要解释任何无上下文的语法如何编码从自由生成的作品的作品函数中，以某些“拼接单词的oparad”编码。这激发了任何类别$ c $的CFG的更一般概念，该概念定义为具有颜色的有限物种$ s $，表示起始符号和一个Operads $ P的函数$ p：free [s] \ w [c] $ to w [c] $ in $ c $ in $ c $。我们表明，可以在此框架内制定CFG的许多标准属性，并且CF语言的通常闭合属性将其推广到箭头的CF语言。我们还通过“显示” oprad的概念讨论了Foundor $ p $的双纤维视角，该概念对应于oparads $ w [c] \ to span（set）$的lax函数。 然后，我们转向乔姆斯基 - 雪松堡代表定理。我们描述了如何将非确定性的有限状态自动机视为一个类别$ Q $，配备了一对对象，这些对象表示初始和接受的状态和类别的函数$ q \ to c $ to c $ co $满足因素化属性和有限纤维属性的独特提升。然后，我们解释了如何将自动机的这种概念扩展到概括树自动机的函数，从而使我们能够将自动机抬高到一个自动机上，以在其剪接箭头的手术上将自动机提升到自动机。我们表明，可以将每个CFG的类别上的每个CFG沿同一类别的ND有限状态自动机撤回，因此CF语言在与普通语言的交叉点下关闭。最后一个重要的成分是识别左伴随$ c [ - ]：cat $ to cat $ to cat $ to pliced Arrows functor的cat $，构建了Operad的“轮廓类别”。使用此过程，我们将C-S表示定理概括，证明类别$ C $上的任何无上下文语言是$ C $ - 奇异的树轮廓语言和常规语言的相交的功能图像。
We begin by explaining how any context-free grammar encodes a functor of operads from a freely generated operad into a certain "operad of spliced words". This motivates a more general notion of CFG over any category $C$, defined as a finite species $S$ equipped with a color denoting the start symbol and a functor of operads $p : Free[S] \to W[C]$ into the operad of spliced arrows in $C$. We show that many standard properties of CFGs can be formulated within this framework, and that usual closure properties of CF languages generalize to CF languages of arrows. We also discuss a dual fibrational perspective on the functor $p$ via the notion of "displayed" operad, corresponding to a lax functor of operads $W[C] \to Span(Set)$. We then turn to the Chomsky-Schützenberger Representation Theorem. We describe how a non-deterministic finite state automaton can be seen as a category $Q$ equipped with a pair of objects denoting initial and accepting states and a functor of categories $Q \to C$ satisfying the unique lifting of factorizations property and the finite fiber property. Then, we explain how to extend this notion of automaton to functors of operads, which generalize tree automata, allowing us to lift an automaton over a category to an automaton over its operad of spliced arrows. We show that every CFG over a category can be pulled back along a ND finite state automaton over the same category, and hence that CF languages are closed under intersection with regular languages. The last important ingredient is the identification of a left adjoint $C[-] : Operad \to Cat$ to the operad of spliced arrows functor, building the "contour category" of an operad. Using this, we generalize the C-S representation theorem, proving that any context-free language of arrows over a category $C$ is the functorial image of the intersection of a $C$-chromatic tree contour language and a regular language.
