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 offers interesting features to deal with such processing issues.
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 proposals for incremental proof net constructions, and their relevance for human language processing issues. Also we investigate the trade-off between expressivity and processing efficiency for some approximations of the full grammar logic.