Dependency Propagation: A Unified Theory of Sentence Comprehension and Generation

1. Introduction

Some systematic relationship must hold between sentence comprehension and generation by humans, as suggested by the following phenomena, among others. First, most naively, the language one speaks and that one hears have similar structures. Second, there is an affinity between the process of comprehension and that of generation. For insta,nce, we often literally guess how others' speech could contmue, or detect grammatical errors and semantic incon­ sistencies in our own speech. Third, the two processes become equally difficult in the case of, say, deep center­

embedding constructions.

In order to account for these phenomena, one might hypothesize some relationship between sentence comprehen­ sion and generation; i.e., between the two (maybe the same) grammars and between the two (maybe the same, too) pro­ grams for comprehension and generation. Here we adopt the strongest hypothesis:

1. A single mental program underlies both sentence comprehension and generation.

Let us call this the Common Program Hypothesis (CPH for short), and the mental program mentioned therein the Common Program (CP). The challenge of the current work is to figure out how CP operates, as well as to what extent CPH can be supported.

CP must be a coherent system of instructions (and/or constraints, as it will in fact tum out) rather than a patch­ work of subroutines independent of each other. As an extreme instance, CP must not consist of two modules, one for comprehension and the other for generation. More pre­ cisely, CP is defined to be the maximum domain of the mind every part of which is potentially exploited in both sentence comprehension and generation. This definition ensures the existence of CP ~ithout saying anything about its coverage, whereas CPH cla1ms that the coverage encompasses some crucial part. of both sentence comprehension and generation. Another pomt to be drawn from this definition is that CP contains grammar rules and lexical entries as long as they have chance to be exploited in both comprehension and pro­ duction.

In the following discussion, we shall formulate CP as consisting of two components. One is a declarative representation of linguistic knowledge. This representation is m<>?elize~ in terms of a logic-programming formalism, and b1~sed m favor of neither sentence comprehension nor generat10n. The other component of our model of CP is an interpreter of this knowledge. It is the operation of this interpreter that is called Dependency Propagation. This interpreter is exempt from language-specific aspects, not to speak of comprehension-specific or generation-specific aspects.

This model of CP is based upon the observation that sentence comprehension and generation make access to the same linguistic knowledge, but in different ways. For exam­ ple, consider the syntactic rule about English topicalization as in: Mary, Tom doesn't like to see. Put declaratively, this rule might look like (2), details being omitted.

1. A sentence S may consist of any constituent X plus a following sentence SIX which lacks X somewhere. Here X is semantically focused on.

This rule is exploited in different ways between sentence comprehension and generation. In comprehension, perhaps this rule is fully activated only when the beginning of SIX is detected. At that time X would get focused on. In typical cases of generation, on the other hand, the rule could be activated by a focused semantic element, whereby this ele­ ment is first put into a linguistic expression X.

The ?Ommon linguistic knowledge such as (2) would be modeled m terms of declarative rules, constraints, or the like. The apparent difference between comprehension and generation is in the manners of access to such knowledge. In the former models of language faculty (and in application programs such as those of machine translation), this difference has been stipulated in terms of comprehension- or generation-specific heuristics about when and how to activate most efficiently which piece of linguistic knowledge. For instance, a generation-oriented heuristic rule to exploit

1. might state:
2. If a verbalization into a sentence is currently attempted, and the topical focus is upon a part of the input seman­ tic content, then first translate the focused part into a language expression X , and next attempt to verbalize the remaining content as a sentence in which X is miss­ ing somewhere.

The major task in our pursuit of CPH is to substitute the heuristics of this sort with a general nonbiased paradigm of problem-solving to interpret the common declarative knowledge. That is, such a paradigm should control the tim­ ing of and data-flow in the exploitation of linguistic knowledge, just the same way as those heuristics do. For instance, Prolog interpreter does not provide such a para­ digm. In fact, the existing implementations of DCG (Pereira and Warren, 1980) cannot deal with sentence comprehension and generation equally efficiently; they must be biased (by virtue of procedure attachments, etc.) in favor of one or the other task, in order to work efficiency. DP will be proposed later as a candidate for the desired paradigm.

Such a pursuit of CPH should be qualified, however, because there are some good reasons to conclude that some of those heuristics should survive for the sake of processing efficiency, and hence that CP does not encompass the entire language processing. For example, typical cases of Broca's aphasia exhibit so-called telegraphic speech (i.e., one which lacks grammatical markers such as inflections, conjugations, prepositions, etc.), the comprehension ability remaining fairly normal. Despite the apparent inconsistency, this phenomenon is compatible with CPH. A consistent interpre­ tation is that the function of retrieving words from meaning (plus syntactic features) do not belong to CP, and therefore may be lost without reducing the ability to listen. Other evi­ dences, including aphasic symptoms contrasted with tele­ graphic speech, suggest that CP should also exclude the function of retrieving meaning from words, thus totally excluding search in the lexicon.

That CP excludes lexical retrieval is predicted a priori, by taking into account the vastness of the lexicon. In the case of comprehension, a lexical entry is considered to be retrieved with its phonological form as the key. There must be some access paths which you traverse by using phonolog­ ical keys to reach desired words. These paths are not likely to be exploited in generation. Similarly, the access paths through which you find words from semantic keys need not be activated in comprehension. That is, the access paths of either direction must be out of CP. To retrieve grammar rules like (2), on the other hand, is quite another story. As is demonstrated in HG (Polloard, 1984), HPSG (Pollard, 1985), etc., the inventory of grammar rules is regarded as very small (i.e., complementation, adjunction, coordination, topicalization, and few more), when the lexicon is maxim­ ized. Such a demarcation between grammar and lexicon renders trivial the search of grammar rules. Hence the (perhaps simplifying) assumption that the access paths to grammar rules are shared between comprehension and gen­ eration would not separate the resulting model very far from the reality.

To summarize, our assumption is that CP subsumes the grammar rules, the access paths to them, and the lexicon, but not the access paths to the lexicon. The rest of the paper is concerned with how the information included in CP is put to use.

2. Constrained Patterns

Sentence comprehension is a task to figure out semantic structures of given strings of words, and sentence generation is a task in which, contrariwise, strings of words are worked out of given semantic structures. Among the currently avail­ able programming paradigms, unification seems to be most promising in order to capture this hi-directionality of data­ flow in CP.

Another reason for the employment of unification in describing the flow of linguistic information is that there have been developed several unification-based grammar for­ malisms, such as GPSG (Gazdar, Klein, Pullum, and Sag, 1985), LFG (Bresnan, 1982), HG, HPSG, FUG (Kay, 1985), and CUG (Uszkoreit, 1986). These theories provide a basis for a representation of linguistic knowledge shared between comprehension and generation. The reader may consider that the description of the grammar and the lexicon in our model exploits the techniques in the unification-based gram­ mars mentioned above, unless stipulated otherwise.

Here we introduce a scheme for representing linguistic information. This scheme exploits the Hom-logic program­ ming formalism (i.e., that of Prolog), so that information could flow back and forth via unification. Ordinary patterns as in Prolog in which variables are simply indeterminate, however, are problematic in that they are lacking in expres­ sive power. To remedy this, our scheme incorporates con­ straints on variables appearing in patterns; thus such pat­ terns are called constrained patterns (formerly called conditioned patterns in Hasida (1986)).

A constrained pattern is a pair of a pattern (of Prolog) and a constraint. A constraint is a sequence of atomic for­ mulas (again, of Prolog), where all the predicates heading those atomic formulas (e.g., p of an atomic formula p (X, Y)) are defined by Hom clauses; that is, every predi­ cate considered here must not be system-defined. For instance,

is a constrained pattern with pattern a (j (X, Y), A , B) and constraint fp (X, A), q (Y, B)], provided that predicates p and q are defined in terms of Hom clauses. Note that a con­ strained pattern looks just like a Hom clause, except that the pattern and the constraint are separated by t> rather than :-.

The semantic difference between a Hom clause and a constrained pattern is that the former expresses a scheme of logical inference, while the latter denotes a set of patterns. For example, (4) represents the set exhibited in (5), in the case where predicates p and q are defined by (6).

When some predicate in the constraint has a recursive definition, a constrained pattern may represent a set which cannot be denoted by a finite set of patterns possibly con­ taining variables. For instance, the constrained pattern (7) represents the set of all the lists ending with the null list (i.e., [ ]), where predicate list is defined as in (8).

(7) X t> list (X).

(8) list([]). list ([A I X]) :- list (X).

A number of problems can be represented as a con­ strained pattern; i.e. , a constrained pattern is regarded as denoting the set (or a subset) of the solutions of a problem. The problem for CP to solve, for example, is represented by a constrained pattern such as shown in (9), where the predi­ cate constituent is defined as in ( 10).

1. struct (Category, X, Y) t> constituent (Category, X, Y).

1. constituent(Category, X, Y) :­ lexicon (Category, X, f) . constituent(Mother, X, Z) :- phrase _structure _rule (Mother, LeftDaughter, RightDaughter ), constituent(LeftDaughter, X, f), constituent (RightDaughter, f, Z ).

In short, this is a sort of DCG. The predicates lexicon and phr,as~ _s~ructure _rule are also defined by Horn clauses, and, as 1s md1cated by their names, represent the access paths to the mental lexicon and the mental grammar. Variables X, f, and Z in (10) denote some portions of the terminal string, whereby the last two arguments of constituent consti­ tute the differential list representing the part of the terminal ~tring wh~ch the constituent in question exhaustively dom­ mates, as m:

(11) constituent (sentence, [tom, loves, mary I X], X)

3. Dependency Propagation

This ~ection is devoted to a formulation of a problem-soling parad1gm under the representation scheme just illustrated above. In this paradigm, the logical structure of the problem to be solved determines the ordering of execution to process the information represented as constraints. In contrast the existin~ Prolog intel'\'re~rs CllfTY out execution si:nply accordmg .to the ordenng m wh1ch atomic formulas happen to appear m source programs.

3.1. Dependency versus Modularity

Let us say that there is a dependency between two atomic formulas sharing some variable, in the sense that the instan­ tiation of the shared variable can be licensed only through some possibly nontrivial interaction between the two formu­ las. For instance, p (X , Y) and q (f, Z) are dependent on ea~h other; there does not necessarily exist a pattern y satis­ .fymg. q (~. y) for every a and ~ satisfying p (a, ~). An atorruc formula some of whose arguments is not a variable involves dependency as well; i.e., the dependency between that argument and the predicate of the atomic formula. For example, there is a dependency in p (f (X ) ), in the sense that there does not necessarily exist a pattern ~ such that a =I(~) for every a satisfying p (a).

Let us say that a constraint is modular when it con­ tains no dependency at all in such a sense. In order to put it more formal, let us define the notion of superficial modu­ larity. A superficially modular constraint is one in which all the arguments of all the atomic formula are variables and no variable occurs twice. A constraint is modular iff all the relevan~ constr~ints are superficially modular; all the relevant constramts bemg defined to be the constraint itself the bodies . of the Horn clauses defining the predicates i~ the constramt (note that the body of a Horn clause is looked upon as a constraint), the bodies of the Horn clauses defining the predicates in those bodies, and so on. A con­ strained pattern is said to be modular when its constraint is modular. A predicate is modular when it is defined in terms of only Horn clauses whose bodies are modular constraints. For example, .(4) and (7). are modular constrained patterns, when the pred1cates expl01ted there are modular for instance being defined by (6) and (8), respectively. '

3.2. A View of Problem Solving

As demonstrated above, a constrained pattern represents a solution set of a problem. As a matter of course, however, to represent does not necessarily imply to solve. Granted that the solution should also be represented in terms of a constrained pattern, that constrained pattern would be of what might be called a 'resolved form.'

A modular constrained pattern is looked upon as 'resolved.' That is, it is an almost extensional enumeration of patterns, as typically seen in (4), thus conforming to the intuition that, in general, a resolved form should enable you to enumerate the solutions in time proportional to the sum of their complexity. Consequently, a problem represented as a constrained pattern is resolved by modularizing that con­ strained pattern; i.e., transforming it into a modular equivalent. The modularization is regarded as driven by dependency: Dependency in some parts of a constraint invokes execution which in tum gives rise to dependency in the neighboring parts of the constraint, which invokes further execution, and so on until dependency disappears. We refer t? this problem-solving paradigm as Dependency Propaga­ tion (DP).

~or example, if a problem is represented by (12), then (13) 1s a resolved representation, where p is an arbitrary unary modular predicate and member and mp are defined as in (14).

(12) I (E, S) p. member(E, S), p (E).

1. f(E, S) p. mp(E, S).
2. member(E, [E IS]). . member(E, [A IS]):- member (E, S ).

mp(E, [E IS]):- p(E). mp(E, [A IS]):- mp(E, S).

A constraint is modularized by means of an algorith~ simi­ lar to fold/unfold program transformation. In the above example, the dependency (i.e., the double occurrence of E) in the constraint-part of (12) invokes unfolding of member (E, S ), and then folding the resulting constraint into mp (E, S ). For further details of the algorithm see Hasida (1986) or Hasida and Sirai (1986). '

Note two aspects of DP here. First, DP is optimized in the sense that it responds only to 'pressing needs' represented as dependency, thus minimizing the waste of processing. Second, according to DP, the procedure to inter­ pre~ a given representation of a problem reflects more of the log1cal structure of that problem rather than artifacts in the representation. Compare this with Prolog interpreters, which ten~ to indulge in inve~tigation of top-down hypotheses wh1ch happened to be activated on the way of the execution ordering predetermined by the ordering in the source pro­ gram. Some proposals su~h as freeze (Colmerauer, 1982) are made to overcome th1s defect of Prolog, but they are partial solutions unlike DP.

The current problem, represented by (9) together with ~10), l_llay general!>: be solved by modularizing (9) after mstant1atmg the var1ables Category, X and f according to ~he given information. Put more precise, in the case of pars­ mg. Category is first left indeterminate, X is set to be the given sentence, such as [tom, loves, mary]. In the case of sentence generation, the semantic part of Category is first instantiated to be the given semantic content (e.g., love (tom, mary)) of the target sentence, X being left unin­ stantiated. f is initially set to nil (i.e., []) in both cases.

3.3. Compilation as Partial Computation

One might expect that (9) could be modularized in advance, so that the amount of computation is greatly saved in indivi­ dual ca~es . of . comprehension and generation; a sort of prc:comp1.lation m terms. of partial computation. This expec­ tation fa1ls, however, m almost every nontrivial case. In fact, ~9) h~s a modular eq~ivalent only when the language in question 1s regular, detailed mathematical account being omitted.

Nevertheless, one can consider instead an equivalent constrained pattern which is semi-modular: modular except that a variable may occur more than once in a constraint iff the instantiation of that variable is influenced at most one occurrence. A variable representing a part of the terminal string is a typical example of such a variable; it appears first as the latter component of a differential list, and second as the first component of another differential list, as Y does in (10). Such a semi-modular description of a language is available through precompilation in great many significant cases; i.e., for the class of languages including all the context-free languages, such repetition languages as {wn I w e .1:*} (n is an arbitrary natural number, and .1: an arbitrary finite set of alphabets), etc.

For instance, when the language in question is deter­ mined by (15) (i.e., the grammar given in (16)), a semi­ modular equivalent cO of constituent, is obtained simply as in (17).

Note here that the bodies of the two Hom clauses in (17) are modular except that Y appears twice in the second.

4. A Cognitive Model

Parsing and generation by modularizing (10) or (9) in a sin­ gle stroke, however, fails to fit the reality with respect to the following two aspects. First, humans process sentences from left to right, not necessarily having in mind the global view of what the sentence eventually turns out to be. Second, presumably on account of the limitation on STM capacity, humans do not pay attention to every possible solution; oth­ erwise such phenomena as garden-path sentences and resumptive pronouns would not take any place.

4.1. Left-to-Right Processing

Sentences may be formulated as processed (i.e., comprehended or generated) little by little from left to right, so that the first aspect is incorporated in the model. To illustrate this, a sentence Tom loves Mary is parsed as fol­ lows.

In general, parsing proceeds by successively semi­ modularizing the constraint [ci(Category, [ai I X], Y)] to [ci+l(Category, X, Y)], for 0 S i < n, n being the sentence length and ai the i -th terminal symbol.

Generation goes similarly:

That is, at first the constraint [c0(a,[Aol X], Y)] is semi­ modularized to yield a constraint on variables A 0, X, and Y. The variables contained in a is concealed in the definition of c1. Afterwards, [ci(A 0, · · ·,Ai-l ,[Ai I X], Y)] is semi­ modularized to [ci+1(A 0, · · · ,Ai,X, Y)], consecutively for i =1, 2, Under this formulation of sentence generation, the whole constraint on the entire sentence should at the very beginning be fit with the semantic structure embedded in a . This result should be rejected, since it is not always possible to have the complete meaning of the entire sentence before generation begins. A further investigation presented later will overcome this weakness.

4.2. Memory Limitation

In order to capture the limitation on the STM capacity, let us assume that there is a finite bound on the amount of working memory in which to store the Hom clauses produced dynamically during comprehension and generation. Follow­ ing this assumption, Hom clauses whose activation inten­ sity is weaker than others are pruned off so that the remain­ ing Hom clauses should fall together within the limited storage.

The activation intensity of a Hom clause is mentioned here as a neurophysiological metaphor. A Hom clause activates or deactivates some other Hom clauses. The strength of this (de)activation is positively correlated with the activation intensity of that Hom clause. Hom clauses competing with each other should be inhibitory against each other. For instance, different clauses defining the same predicate should tend to deactivate one another.

This paper does not go any further into the question of what activation intensity should be like. A fuller account would require something like the connectionist approach (Waltz and Pollack, 1985). In the current computer imple­ mentation, the intensity is simulated by an integer assigned to a Hom clause.

It must be emphasized that the memory limitation is crucial in our present approach to CPH. For instance, the fluency of generation follows from the memory limitation. In (19), the constraint on Ai 's instantiation can be retained for only a few j such that 0 S j S i, due to the memory limitation. Hence the determined value of A i should have been emitted as a part of utterance except for j very near to i. Incidentally, therefore, in practice we come up with ci+l (Ak , · · · , Ai, X, Y) for some k close to i, instead of ci+l(Ao, . .. , Ai, X, Y).

4.3. The Head-Driven Propagation

The currently assumed DP (i.e., the exhaustive semi­ modularization in precompilation and execution) eliminates every non-vacuous dependency. This is problematic, how­ ever, for several reasons that follow. First, (semi-) modular­ ization as currently conceived tend to consume too much memory. For example, the amount of memory occupied by the constraint of any modular equivalent of the constrained pattern (20) is 0 (m xn ), where m and n are prime to each other, and listm and listn are defined as in (21).

(20) X ~ listm (X), listn (X).

Since the memory requirement of the given representation (20) with (21) is O(m+n), the coding efficiency of the representation is deemed as often reduced by modularization.

Second, the current formulation tend to waste process­ ing time, in the sense that predicates are often generated which are never referenced. For instance, if (semi-) modu­ larization takes place when two constrained patterns I (X) ~ p (X) and I (Y) ~ q (Y) are unified with each other, then a new constrained pattern I (X) ~ r (X) is yielded together with the new predicate r. If an unsuccessful unification between g (Z) and f (X) P. r (X ) is attempted next, r (X) is simply discarded without being exploited at all.

Third, there are many important predicates which have no semi-modular equivalents. Mathematical details being omitted, those predicates include permutation (a binary predicate to the effect that the two arguments are lists which are permutations of each other), subset (a binary predicate to the effect that the two arguments are lists and that the former represents a subset of the latter), etc.

To avoid these problems, let revise DP by relaxing the present requirement that DP semi-modularizes given constraints. To overcome the defects discussed above, DP should instead operate selectively on the parts of the given constraint which are likely to be referenced more often than others.

A typical bias of reference likelihood is found between the head and nonhead daughters in a local tree. Consider a local tree shown below, for example.

This local tree may be regarded as an instantiation of a rule such as S --+ NP VP and NP --+ Det N, in a familiar nota­ tion. When one of Mother and HeadDaughter is refer­ enced, then it is nearly certain that the other is also refer­ enced, because these two nodes share almost the same infor­ mation. Mother and HeadDaughter, than to dependency that NonHeadDaughter has with Mother or HeadDaughter. Let us tentatively formulate this as the following extremely simplified form.

(23) In both sentence comprehension and generation, DP operates so that:

1. the constraint on every node is modular which dominates an exhaustively processed part of the terminal string, and
2. there is no remaining dependency between any node and its grammatical head.

Let us call this the Head-Driven Propagation (HDP, for short).

Due to (23a), HDP roughly amounts to a parallel exe­ cution of what Hasida (1985) calls the Canonical Pro­ cedure. The Canonical Procedure is a nondeterministic pro­ cedure to handle a coherent substructure of a sentence at a time. In general, the partial structure regarded as resolved (i.e., modularized, in our current terminology) at any stage during the execution of the Canonical Procedure looks like the one enclosed in the curve of (24) below, where the categories C:Xt. !31, · · · c:xd, 13d, and c:x are memorized in the working storage.

On account of (23b), the modular domain in the case of HDP may be a little wider than the area enclosed in the curve; That is, the former also includes the path from B; down to its lexical head. For example, when terminal string A dog which is just processed, a maximal coherent structure dynamically generated would look like (25), provided that VP is a head of S and S is a head of S.

Since a node and its heads greatly share information, the substantial difference between (24) and (25) is smaller than it appears.

An advantage of adopting principle-based grammars such as GB (Chomsky, 1981, 1986) and HPSG is that one can remove much of artifact in the grammar by controlling the precompilation. Such a control is possible because principle-based grammars are of the 'least precompiled' form. In HPSG, for instance, the phrase-structure rules have been abstracted away from information in the lexicon, and also from general properties of local trees, which are fac­ tored out as general principles like the Binding Inheritance Principle, the Head Feature Principle, etc. If a grammar of a more precompiled form such as GPSG were adopted, the distribution of the reference likelihood in compiled represen­ tation of grammar would be less controllable.

4.4. An Example

Now let us look at some concrete cases of DP as presently conceived in sentence processing. Since it would be too complicated as an example to precisely demonstrate how an actual natural language sentence is processed, first we exam­ ine here the language defined by (15). Several more linguistically real instances will be considered later.

Shown below is how a sentence aaa · · · of the language in question is parsed, following the procedure illus­ trated in (18).

Hom clauses have not been pruned off here. To see what a pruning is, let us simulate the memory limitation by a simplistic requirement that the number of Hom clauses in the working memory should be no more than, say, seven, according to Miller (1958). After a possible pruning, we might be left with, for instance, the Hom clauses listed in (27):

The Hom clauses defining c0 are not discarded dynamically, because they have been yielded by precompilation and thus are regarded as stored in the long-term memory.

Note that every atomic formula in the bodies of the remaining Hom clauses are solvable by finite patterns, based only upon the remaining Hom clauses; e.g., c 2(B , X, Y) is solvable with B = g (j, f) and X = [a I Y). This is impor­ tant because a mental representation must be finite. So for instance the first Hom clause defining c 1 must be retained; otherwise no finite pattern could solve c 1 (B , X, Y). In order for pruning to take care of this, smaller intensity values should be assigned to Hom clauses (e.g., the second clause defining c 1 ) taking part in recursive definitions of predicates.

Incidentally, if a predicate is defined by only one Hom clause, it is usually more efficient (with regard to both memory and time) to unfold that predicate at all its occurrences and discard it. For instance, in (27) there remains only one clause defining c2· Thus we obtain (28) by unfolding and eliminating c 2·

(28) c 3 (g(j, g(j, B)), X, Y) :- c 1(B, X, Y).

c 3(g (g (j, f), B), X, Y) :- c 1 (B , X, Y).

c 3 (g(g(j, g(j, f)), B), X, Y) :- c 0 (B, X, Y).

c 3 (g(A,B),X,Z) :- c 3 (A,X, Y), c0(B, Y,Z).

This example of DP amounts to a parallel execution of the Canonical Procedure. For instance, the four Hom clauses in (29) extracted from. (28) represent together the tentative partial structure depicted in (30).

Here the node labeled g (j, g (j, B 1)) is on the left comer of A 0 , being possibly identical to it. These two nodes are related through the second clause defining c3 in (29), and the distance between them in a potential completion of (30) is equal to the number of times that this clause is exploited. g (j , B 2 ) stands in the same sort of relationship with B 1 through the second clause defining c 1. (30) amounts to a snapshot just before (24) with d = 2. That is, a 1, ~1 , ~. and ~ 2 in (24) correspond to g (j, g (j, B 1)), B 1, g (j, B 2), and B 2 , respectively; a in (24) has no counterpart in (30). As exemplified here, the amount of memory occupied by Hom clauses representing together the partial structure in (24) is proportional to d.

4.5. Accounts of Some Linguistic Phenomena

HDP provides a measure of transient memory load (TML; i.e., the load on STM) which is finer-grained than left-branching (Yngve, 1960), center-embedding (Church, 1980), self-embedding (Miller and Chomsky, 1963), etc.

First, the complexity of a single coherent structure of a sentence is measured in terms of the memory requirement by Hom clauses needed to represent a coherent substructure of that structure at a given stage of processing. That is, TML of a maximal coherent structure is estimated to be 0 (d) with respect to the moment depicted in (24). This measure amounts to a refinement of center-embedding; we have d ~ 8 ~ 2d+1, where 8 is the depth of center-embedding.

Moreover, the entire memory requirement at a stage of processing in HDP captures also local structural ambiguity. Some authors have attempted to measure local ambiguity by means of the degree of lookahead (Marcus, 1980; McDonald, 1980), but the defect of such a measure is that it is not by itself sensitive to static complexity of sentences. The present framework lays a basis for talking about static complexity and local ambiguity at the same time.

HOP seems to approximate the reference likelihood of the actual mental representation of grammar. Let us con­ sider two examples.

First, HDP is compatible with the observation that humans can 'predict' the relationship between a category and its left-comer. In English, for instance, a sentence often begins with a determiner, in constructions like (31).

HDP is enough to 'predict' the relationship between S and Det, because, the moment Det is processed, the information that VP takes NP and NP in tum takes Det as complements (or maybe as specifiers), is exploited. It is also enough to deal with agreements of gender, number, etc. For example, the information about the agreement between the head N and Det (and AP) in (32) is incorporated in precompilation.

Second, HDP does not modularize too much. Consider resumptive pronouns, for instance. A typical context where a resumptive pronoun is found is something like (33).

(33) the man who I wonder whether he is wise Here, he is a resumptive pronoun coreferring with the ~n. HDP accounts for why such an apparently ungrammatical utterance is generated. Let us take a look at (34), the struc­ ture of (33).

HDP leaves unresolved the relationship between So and NP2 and the one between S1 and NP3· Therefore, it is impossible to detect the grammatical inconsistency until generation of sl is attempted.

McDonald (1980) proposes a different explanation of the same phenomenon, based on a deterministic model of sentence generation: a generation version of Marcus' (1980) parser. McDonald draws upon the limited lookahead presup­ posed in the determinism doctrine. ~is discussion is ~ong or at best incomplete, because he fatls to P.ay atte?tlon to how far the coming structure can be predtcted v1a HDP rather than lookahead.

5. Final Remarks

A model has been proposed which de~cribes both senten~e comprehension and production as a smgle program. Thts program is a system of constraint rath~r than a s~uen.ce of instructions, and the procedure CP to mterpret gtven mfor­ mation is derived from the computational structure of the task to be performed. This model exploited . a problem­ solving paradigm called De~nd~ncy Propagatu;m: De~n­ dency in the given constramt mvokes execution, whtch proceeds so that the likelihood of reference becomes homo­ geneous over the whole constraint.

If we note that the likelihood of reference is related with the density of some sort of info~~tion, some. p~ ?f the discussion suggests a general pnnctple that lmgutstlc information should be homogeneously distributed over the entire representation of the mental &ra~mar: fl: J?rinciple perhaps stemming out of the more ubtquttous p~nctple ~at evolution optimizes the resulting syste.~. In th~ hght of t~1s, Dependency Propagation lays a promtsmg basts upon whtch to talk about how cerebral coding of knowledge is reformed as new information comes in; more specifically, how an accumulation of concrete instances gives rise to abstract rules of the mental grammar.

Bresnan, J. (ed.) (1982) The Mental Repesentati~n of Gram­ matical Relations, MIT Press, Cambndge, Mas­ sachusetts.

Chomsky, N. (1981) Lectures on Government and Binding, Foris, Dordrecht.

Chomsky, N. (1986) Barriers, MIT Press, Cambridge, Mas­ sachusetts.

Church, K. (1981) On Memory Limitations in Natural Language Processing, MIT/LCSrrR-245, Laboratory for Computer Science, MIT.

Colmerauer, A. (1982) Prolog II Reference Manual and Theoretical Model, ERA CNRS 363, Groupe d'Intelligence Artificielle, Universite de Marselle, Mar­ sene.

Gazdar, G., Klein, K., Pullum, G., and Sag, I .. <1985) Gen­ eralized Phrase Structure Grammar, Bast! Blackwell, Oxford.

Hasida, K. (1985) Bounded Paralleli~m: A. Theory_ of Linguistic Performance, Doctoral D1ssertat10n, Umver­ sity of Tokyo.

Has ida, K. ( 1986) 'Conditioned Unification for Natural Language Processing,' Proceedings of the 11th COLlNG, pp. 85-87. . .

Hasida, K. and Sirai, H. (1986) 'Zyookentuk1 Tan-1tuka (Conditioned Unification; in Japanese),' Computer Software, Vol. 3, pp. 28-38. .

Kay, M. (1985) 'Parsing in Functional Unification. Gram­ mar,' in Dowty, D., Kartunnen, L., and Zwtcky A. Natural Language Parsing, pp. 251-278.

Langendoen T. (1975) 'Finite State Parsing of Phrase Struc­ ture La~guages and the Status of Readjustment Rules in Grammar,' Linguistic Inquiry, Vol. 6, pp. 533-?54.

McDonald, D. (1981) Natural Language Prod'!ct10n as a Process of Decision Making under Cons!ramt, Doctoral Dissertation, Laboratory of Computer Sctence, MIT ..

Miller, G. (1958) 'Magical Number Seven Plus or Mu~us Two: Some Limits on Our Capacity for Processmg Information,' The Psychological Review, Vol. 63, pp. 81-97.

Miller, G. and Chomsky, N. (1963) 'Finitary Models of Language Users,' in Luce, R., Bush, R., and Galanter, E. (eds.) Handbook of Mathematical Psychology, Vol. II, pp. 419-491, John Wiley and Sons, New York.

Pereira, F., and Warren, D. (1980) 'Definite Clause Gram­ mar for Language Analysis - A Survey and a Com­ parison with Augmented Transition Networks,' Artificial Intelligence, Vol. 13, pp. 231-278.

Pollard, C. (1984) Generalized Phrase-Structure Grammar, Head Gramamrs, and Natural Languages, Doctoral Dissertation, Stanford University, Stanford, California.

Pollard, C. (1985) Lecture Notes on Head-Driven Phrase­ Structure Grammar, Center for the Study of Language and Infol'Il}ation, Stanford University, Stanford, Califor­ nia.

Uszkoreit, H. (1986) 'Categorial Unification Grammars,' Proceedings of the 11th CO LING, pp. 187-194.

Waltz, D., and Pollack, J. (1985) 'Massively Parallel Pars­ ing: A Strongly Interactive Model of Natural Language Interpretation,' Cognitive Science, Vol. 9, pp. 51-74.

Yngve, V. (1960) 'A Model and an Hypothesis for Language Structure,' in Ferguson, D. and Slobin, D. (eds.) Proceedings of the American Psychological Society, Vol. 104, pp. 444-466.