Classical linear logic, cobordisms and categorial grammars
This work addresses a theoretical problem in computational linguistics by providing a concrete and intuitive representation for categorial grammars, though it appears incremental as it builds upon existing ACG frameworks.
The authors tackled the problem of representing categorial grammars by proposing linear logic grammars (LLG) based on classical multiplicative linear logic, which extends abstract categorial grammars (ACG) and is at least as expressive, using word cobordisms as constituents instead of abstract λ-terms.
We propose a categorial grammar based on classical multiplicative linear logic. This can be seen as an extension of abstract categorial grammars (ACG) and is at least as expressive. However, constituents of {\it linear logic grammars (LLG)} are not abstract $λ$-terms, but simply tuples of words with labeled endpoints and supplied with specific {\it plugging instructions}: the sets of endpoints are subdivided into the {\it incoming} and the {\it outgoing} parts. We call such objects {\it word cobordisms}. A key observation is that word cobordisms can be organized in a category, very similar to the familiar category of topological cobordisms. This category is symmetric monoidal closed and compact closed and thus is a model of linear $λ$-calculus and classical, as well as intuitionistic linear logic. This allows us using linear logic as a typing system for word cobordisms. At least, this gives a concrete and intuitive representation of ACG. We think, however, that the category of word cobordisms, which has a rich structure and is independent of any grammar, might be interesting on its own right.