Course description This course focuses on computational aspects of grammar logics. In a companion course , we have presented grammatical derivations in the Gentzen calculus and in the Natural Deduction format. From a computational point of view, these formats are problematic. Natural Deduction is good for the presentation of proofs once they have been found, but it doesn't offer pleasant proof search facilities. The proof-net approach of Linear Logic has attractive properties for natural language processing.
Proof nets are graphs satisfying certain well-formedness conditions.
The challenge, in adapting the nets for NLP purposes, is to introduce additional constraints to also check the relevant aspects of grammatical structure . One way of doing that is to decorate the nodes in a proof structure graph with terms taken from an algebra of structural labels . Alternatively, one can build in the structural factors directly in the graph-theoretic characterization of nets. In the second part of the course, we look at some alternative computational regimes that can be used for fragments of the full grammar logic. We investigate the trade-off between expressivity and computational efficiency.