Introduction: How to Build a Talking Robot - Computational Linguistics and Talking Robots - page 9

1.5 Surface Compositionality
The design of LA-grammars for natural languages is guided by the method-
ological principle of Surface Compositionality (cf. FoCL'99, Sect. 4.5). It pro-
hibits against tricks, such as the use of word forms with a meaning but an
empty surface or with a surface but an empty meaning - all for the sake of
empty “linguistic generalizations” (cf. FoCL'99, Sect. 4.4). 21
By interpreting Surface Compositionality as the condition that each time-
linear derivation step must “eat” a next word form in the input surface, the
computation of possible continuations at any point in the derivation is limited
to the small number of rules in the current rule package. The definition of (i)
an upper bound on the complexity of an LA-rule application and (ii) different
degrees of ambiguity resulted in the LA-grammar complexity hierarchy.
This hierarchy is the first, and so far the only, complexity hierarchy which is
orthogonal to the Chomsky hierarchy of Phrase Structure Grammar (TCS'92).
For example, the formal language a k b k is polynomial (context-free) while
a k b k c k is exponential (context-sensitive) in the Chomsky hierarchy (Aho and
Ullman 1977), whereas in DBS they are both C1-languages and therefore of
only linear complexity.
The LA-hierarchy of languages and complexity classes raised the question
of where natural language is located. Given that the only source of complexity
in the large class of C-languages are recursive ambiguities, we investigated
whether or not this kind of ambiguity may be found in natural languages. A
yes would mean a polynomial or exponential complexity of the natural lan-
guages. A no would mean that the natural languages parse in linear time.
The latter is what one would expect naturally - an argument elaborated
by Gazdar (1982). So far, detailed syntactic-semantic research found that se-
quences of prepositional phrases like on the table under the tree behind
the house are (i) the only candidates for a recursive ambiguity in natural lan-
guage, but (ii) allow an alternative analysis which runs in linear time (Sect.
8.3; FoCL'99, Sects. 12.5, 21.5; NLC'06, Chap. 15).
20 Thanks to Stuart Shieber and Dana Scott, who at different times and places helped in formulating the
algebraic definition for LA-grammar, published in CoL'89 and TCS'92.
21 Lately, HPSG has adopted some version of Surface Compositionality, called “surface-oriented” (Sag
and Wasow 2011). 27 years after SCG'84, this is a substantial step in the right direction. The next
step would be a metamorphosis into an agent-oriented approach. To be genuine, it would have to
model the cycle of natural language communication, which requires a time-linear derivation order at
least for the speak and the hear modes (Sect. 2.6). This, however, would require HPSG to part with
much of its Nativist baggage.