Abstract

The formalism of multiple context-free grammars (MCFG) is a non-trivialgeneralization of context-free grammars (CFG), where basic constituents onwhich rules operate are discontinuous tuples of words rather than single words.Just as context-free ones, multiple context-free grammars have polynomialparsing algorithms, but their expressive power is strictly stronger. It is well known that CFG generate the same class of languages as typelogical grammars based on Lambek calculus, which is, basically, a variant ofnoncommutative linear logic. We construct a system of type logical grammars based on ordinary commutativelinear logic and show that these grammars are in the same relationship withMCFG as Lambek grammars with CFG. It turns out that tuples of words on which MCFG operate can be organized intoa symmetric monoidal category, very similar to the category of topologicalcobordisms; we call it the category of word cobordisms. In particular, thiscategory is compact closed and, thus, a model of linear logic. Usinginterpretation of linear logic proofs as word cobordisms allows us to definetype logical grammars by adding extra axioms (a lexicon) and interpreting themas cobordisms as well. Such grammars turn out to be equivalent to MCFG.

 

Introduction (beta)

None

 

Conclusion (beta)

None