Workshop: Proof nets and their linguistic applications

Eric Auer <eric@coli.uni-sb.de> Feb. 12, 2002

This is a short report on the UiL OTS Workshop on Computational Linguistics and Logic on January 31st 2002 in Utrecht, titled Proof nets and their linguistic applications. The task was to write a short summary/newsitem for an imaginary scientific newspaper. As a result, this will be both short and superficial.

Introduction

In the course of our lecture on proof nets, we were invited to join this workshop and follow the four talks about using proof nets, in particular their linguistic applications. Each of the talks had a time slot of 45 minutes, and most of the speakers were visitors from other universities. We were bound for an afternoon packed with information about ongoing research in this field. To begin with, a list of the presentations: Aravind Joshi (University of Pennsylvania): Some new directions for applications of NLP techniques for modeling biological sequences Quintijn Puite (Rome University): A bilateral-free notion of modules for non-commutative logic Francois Lamarche (Calligrame Nancy): A generic cutelimination theorem Willemijn Vermaat (UiL OTS Utrecht): Inflection: Minimalist Grammar versus Type Logical Grammar

Joshi: trees and structures

In contrast to the other talks, Joshi presented some application outside of the realm of linguistics: His research involves the use of TAG (tree adjoining grammar) to predict folding structures of biological sequences such as proteines and DNA sequences. Such sequences show far more complex structure than simple chains of molecules: Driven by attraction of matching subsequences, the molecules fold. The folding works on several layers: the simplest structure is linear, next are alpha helices and beta sheets, further folding leads to complex three dimensional structures. Joshi uses the topology of TAG trees as predictor for the molecular proximity structure, which he demonstrated in several examples. As for the relation of this research to linguistics, Joshi reminded of the analogy between certain folding patterns and linguistic dependency structures.

Puite: modules as building blocks

Puite reported about research towards a notion of orthogonality of modules (parts of proof nets) which he is doing together with a colleague: A module and an orthogonal module can be combined to a proof net. The representation of modules is done in a graphical way, for which Puite showed some abbreviated notation. He also presented some especially suited graph notation for proof nets. Given that notation, modules can be seen as building blocks which clip together in an intuitive way iff they are orthogonal to each other.

Lamarche: Generic cut-elimination

Lamarche introduced his presentation as one starting with the conclusion, so even people with very limited attention span would be satisfied with it… His philosophy says that any logic consists of a theory of structural context augmented by connectives: For the sequent calculus, cut elimination is an important connective. Adding input/output polarity, algebra becomes logic (reasoning). Lamarche showed two graphical approaches on the example of Lambek calculus: Have polarity built into a (bigger) set of connectives, or pair the polarity with the formula using explicit rules. Finally, an elegant implementation of cut and cut-elimination in this framework was presented.

Vermaat: Comparing grammars

In the final talk, Vermaat presented a fast paced comparison of the treatment of several linguistic effects by two different grammar frameworks: Minimalist Grammar (Chomsky, making heavy use of Move and Merge operations) and TLG. Vermaat showed intermediate results of work in progress, so her data was sometimes sketchy. As an example, word/inflection order effects in French and English sentences are compared: In Guillaume n’aime pas (n’a jamais aimé) du Maxima and William does not love (has never loved) Maxima, movement constraints on verbs, auxiliaries and negation particles vary across languages. Comparing handling of those and other effects by the two mentioned grammar frameworks is the main topic of the presented research. For the fulltime participants, the workshop was later continued in a more relaxed meeting including some calories to be worked on…

L^{A}TEX/joe      http://www.coli.uni-sb.de/˜ eric/