#
Efficient Linear Logic Meaning Assembly

Vineet Gupta, John Lamping
### Introduction

The "glue" approach to semantic composition in
Lexical-Functional Grammar uses linear logic to assemble meanings from
syntactic analyses [Dalrymple et al, 1993]. It has been
computationally feasible in practice [Dalrymple et al, 1997b]. Yet
deduction in linear logic is known to be intractable. Even the
propositional tensor fragment is NP complete. In this paper, we
investigate what has made the glue approach computationally feasible
and show how to exploit that to efficiently deduce underspecified
representations.
In the next section, we identify a restricted pattern of use of linear
logic in the glue analyses we are aware of, including those in [Crouch
and van Genabith 1997, Dalrymple et al 1996,Dalrymple et al 1995] .
And we show why that fragment is computationally feasible. In other
words, while the glue approach could be used to express
computationally intractable analyses, actual analyses have adhered to
a pattern of use of linear logic that is tractable.

The rest of the paper shows how this pattern of use can be exploited
to efficiently capture all possible deductions. We present a
conservative extension of linear logic that allows a reformulation of
the semantic contributions to better exploit this pattern, almost
turning them into Horn clauses. We present a deduction algorithm for
this formulation that yields a compact description of the possible
deductions. And finally, we show how that description of deductions
can be turned into a compact underspecified description of the
possible meanings.

Postscript file.

Pdf file.