MMMay, 2024

合取类别文法与添加剂的 Lambek 文法

TL;DR提出了一种新的范畴语法家族,通过丰富基本的范畴语法,引入了一个连接操作。证明了这种方式得到的形式与带有连接的上下文无关文法具有相同的表达能力。还证明了带有连接的范畴语法可以自然地嵌入到带有连接和析取操作的 Lambek 演算中。这进一步意味着可以在带有连接的 Lambek 演算中定义一个特定的 NP 完全集。还展示了如何处理与空字符串相关的一些微妙问题。最后,证明了由连词语法生成的语言可以由不带有连接但具有析取的 Lambek 语法描述。