Reply to Andrews: The power of linear logic

[Ron Kaplan]

This thread of discussion has advanced since Avery's first message,
but I have some comments to offer on the issues he raised in
his original contribution (Fri, 24 May 96 15:02:39 EST).

Avery has two main concerns about the linear logic proposals for LFG
semantics:

1.  Power:  The linear logic apparatus is so powerful that it could, in
principle, be used for all linguistic analysis.  If you let it in for
semantics, what's to stop you from using it for everything else?

2.  Spirit of LFG:  Even if we confine linear logic just to the semantics,
it really doesn't seem to be in the "spirit" of LFG (correspondences,
monotonicity, etc.)

Of course, these concerns are related (if linear logic was either weak or in
the spirit, presumably Avery's objections would diminish), but I want to
comment on them separately.

In this message I'll comment on the power issue.  I'll address the "spirit"
issue in a later msssage.

Avery correctly notes that the linear logic is a
very powerful formal system.  It could indeed be used to do all sorts
of other jobs that, in LFG, we carefully assign to several other weaker
mechanisms (context-free grammar for c-structure, quantifier-free theory of
equality for f-descriptions, etc.).  But the same question could be asked
about these other mechanisms, which have always been part of the LFG
architecture.  For example, in 1985 Kelly Roach* proved that the
string-to-f-structure mapping of any LFG grammar could be described by
another LFG grammar with a vacuous c-structure component (essentially a
single rule S -> (S) word ).  In essence, the attribute-value mechanism is
so powerful that it can by itself implement all the grammatical conditions
that come from phrase structure grouping and hierarchy--it just needs to
have a trivial finite-state base to provide a string of input words.

[*Roach's paper remains unpublished but is discussed briefly in the new
Formal Issues book (Dalrymple, Kaplan, Maxwell, & Zaenen (CSLI-1995).]

On the Occam's Razor view of scientific methodology, when we realized that
we COULD have dispensed with c-structure and context-free rules as a
separate level of representation, we SHOULD have done that because those
things were then known to be "beyond necessity".  Indeed, HPSG seems to have
opted for this approach--it dispenses with a formally distinct notion of
phrase structure and instead encodes it under various attributes in the
feature structure.  Similarly, classical transformational grammar avoided a
separate representation for grammatical functions, defining them in
phrase-structure terms (SUBJ = NP under S); even its present-day descendants
tend to avoid representations other than trees.

But before making such a move, there is a crucial question that must be
answered:  necessity for what?  If all we care about is getting the string-
to-f-structure mapping to work, then a separate c-structure clearly isn't
necessary (Roach).  But what we really care about is EXPLAINING and
UNDERSTANDING how the mapping works, and in formulating LFG we took the view
that this could best be achieved by breaking it down into a small number of
(relatively) independent modules whose components are related in carefully
defined ways.  This is what led to the LFG architecture of different
structures encoding different aspects of linguistic organization in
different ways, with structural correspondences defined to connected
them--a particular way of formalizing the notion of a "nearly decomposable
system".  Thus, we continue to include a non-trivial context-free c-structure
component in our grammatical descriptions because it seems (at least to us)
that this system of interacting components is better for scientific
reasoning and understanding than the (provably) equivalent monolithic set up.

There are many other illustrations of the same point (that "could" doesn't
imply "should").  We don't use attribute-value logic to describe phonology
because neither the mechanism nor the notation will help to reveal the
underlying phonological generalizations.  Despite its provable sufficiency,
we wouldn't use Mark Johnson's Schoenfinkel-Bernays set of formulas as the
f-description language unless we were sure that important organizing
principles would still be expressed.  Going beyond linguistics, physicists
keep around a lot of "unnecessary" concepts (energy, momentum, power...)
because they help to bring out and explain invariant relationships that
would otherwise be obscure. etc.

[In the world of computational and cognitive modelling there are other
considerations that can be brought to bear:  If you are worried about the
number of different "programs" that you have to write or that have to be
instantiated in the brain, you might favor having the smallest number of the
most powerful set of devices--fewer lines of code.  On the other hand, if
you are worried about speed of execution, memory usage, etc., then you might
see a major folly in using powerful techniques to solve simple problems.
For example, context-free parsing is cubic as an isolated system of
constraints--translating it to a problem in a disjunctive attribute-value
logic invokes mechanisms that are frequently exponential.  On the
mathematics side, transforming a weaker system into a more powerful one
let's you inherit the known properties of the more powerful one (e.g.
decidability might come for free, if it isn't too much more powerful)]

To get back to Avery's concern, clearly general mechanisms should
be used to eliminate more specific ones only when this entails no loss
of explanatory power.  LFG aims to find appropriate divisions of explanatory
responsibility; we are not particularly searching for a single, uniform set
of formal devices to apply to every subproblem.  Thus, although linear logic
COULD probably be used to replace the existing c-structure and f-structure
representations and characterizations, a strong argument needs to be made
that that is the right thing to do.  It is not something to do just because
we find ourselves in Occam's Barbershop.

Ron Kaplan

-------
Until June 30:  Kaplan at nias.knaw.nl
Permanent:  Kaplan at parc.xerox.com