用拓扑量子场论描述自动机与上下文无关语法，建立形式语言新框架。
Formal Languages and TQFTs with Defects
- 将有限自动机映射为带缺陷的1维布尔TQFT，保持变换的函子性。
- 特定子正则语言对应于TQFT的上同调结构，揭示语言复杂度的拓扑特征。
- 推广至上下文无关语法，通过范畴化形式证明构建彩色操作数上的场论映射。
最近，Gustafson、Im、Kaldawy、Khovanov 和 Lihn 构造了一种将有限状态自动机映射为带缺陷的布尔1维拓扑量子场论（TQFT）的方法。本文证明该构造在以转录器为态射的有限状态自动机范畴下是函子性的。某些子正则语言类对应于关联TQFT上的额外上同调结构。此外，我们通过Melliès和Zeilberger提出的范畴化Chomsky-Schützenberger表示定理，将该构造推广到上下文无关语法。此时对应的TQFT可被描述为在带有缺陷的流形操作数范畴上的彩色操作数之间的态射。
原文摘要 · Abstract (English)
A construction that assigns a Boolean 1D TQFT with defects to a finite state automaton was recently developed by Gustafson, Im, Kaldawy, Khovanov, and Lihn. We show that the construction is functorial with respect to the category of finite state automata with transducers as morphisms. Certain classes of subregular languages correspond to additional cohomological structures on the associated TQFTs. We also show that the construction generalizes to context-free grammars through a categorical version of the Chomsky-Schützenberger representation theorem, due to Melliès and Zeilberger. The corresponding TQFTs are then described as morphisms of colored operads on an operad of cobordisms with defects.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。