solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看2550次
Commutative linear logic as a multiple context-free grammar. (arXiv:1810.02047v1 [cs.LO])
来源于:arXiv
The formalism of multiple context-free grammars (MCFG) is a non-trivial
generalization of context-free grammars (CFG), where basic constituents on
which rules operate are discontinuous tuples of words rather than single words.
Just as context-free ones, multiple context-free grammars have polynomial
parsing algorithms, but their expressive power is strictly stronger.
It is well known that CFG generate the same class of languages as type
logical grammars based on Lambek calculus, which is, basically, a variant of
noncommutative linear logic.
We construct a system of type logical grammars based on ordinary commutative
linear logic and show that these grammars are in the same relationship with
MCFG as Lambek grammars with CFG.
It turns out that tuples of words on which MCFG operate can be organized into
a symmetric monoidal category, very similar to the category of topological
cobordisms; we call it the category of word cobordisms. In particular, this
category is compact closed and, thus, 查看全文>>