论文标题
语法上的兰贝克微积分有置换：识别与状态的分支向量系统的力量和连接
Grammars over the Lambek Calculus with Permutation: Recognizing Power and Connection to Branching Vector Addition Systems with States
论文作者
论文摘要
在（van Benthem，1991年）中，可以证明，语法可以由lambek colculus在列表中（LP-Grammars）生成所有无上下文语言的排列。但是，据我们所知，是否确定匡威是否成立。在本文中，我们表明，LP-Grammars等同于具有状态和其他内存的线性限制的分支向量添加系统（不久，LBVASSAM），它们是与状态的修改分支向量添加系统。然后提出了这样的LBVASSAM的示例，该示例会产生一组非旋转矢量。这产生了LP-Grammars所产生的不仅仅是无上下文语言的排列封闭。此外，LP-Grammars和Lbvassam的等效性使我们能够为LP-Grammars提供正常形式，因此，证明LP-Grammars等同于没有产品的LP-Grammars。最后，我们证明，LP-Grammars生成的语言类别在交集下关闭。
In (Van Benthem, 1991) it is proved that all permutation closures of context-free languages can be generated by grammars over the Lambek calculus with the permutation rule (LP-grammars); however, to our best knowledge, it is not established whether the converse holds or not. In this paper, we show that LP-grammars are equivalent to linearly-restricted branching vector addition systems with states and with additional memory (shortly, lBVASSAM), which are modified branching vector addition systems with states. Then an example of such an lBVASSAM is presented, which generates a non-semilinear set of vectors; this yields that LP-grammars generate more than permutation closures of context-free languages. Moreover, equivalence of LP-grammars and lBVASSAM allows us to present a normal form for LP-grammars and, as a consequence, prove that LP-grammars are equivalent to LP-grammars without product. Finally, we prove that the class of languages generated by LP-grammars is closed under intersection.
