A New Kind of Finite-State Automaton: Register Vector Grammar

ABSTRACT

Register Vector _ Grammar is a new kind of finite-state automaton · that iS. sensitive to context--without, of course, being context­ sensitive in the sense of Chomsky hierarchy. Traditional automata are functionally simple: symbols match by identity and change by replacement . RVG is functionally complex: ternary feature vectors (e.g. +-~-~) match and change by masking (± matches but does not change any value). Functional complexity--as opposed to the computa­ tional complexity of non-finite memory--is well sui ted for modeHing multiple and discontinuous constraints. RVG is thus very good at handling the permutations and dependencies of syntax (wh-questions are explored as example). Because center-embedding in natural languages is in fact very shallCM and constrained, context-free power is not needed. RVG can thus be guaranteed to run in a small linear time, because it is FS, and yet can capture generalizations and constraints that functionally simple FS grammars cannot.

I INTRODUCTION

Lately there has been considerable impetus among natural language researchers to restriet the computational complexity required by an adequate theory ( cf. Gazdar 1 981 , Church 1 982, Langendoen 1984). Whereas FS languages guarantee linear recogni tion time, those calling for more computa­ tional power give rise to a combinatorial explosion with respect to worst recogni tion time. Certainly, were there no other fac·tors (such as those mentioned by Berwick and Weinberg 1982, Perrault 1983, Pullum 1983 and 1984), grammars with less computational complexity would be preferred, because they are more easily parsed, and probably also learned (see Berwick 1984).

Until recently, however, it has been supposed that grammars with a more desirable recognition time are cursed by a proliferation of rule structures when it comes to representing generalities and particularities of natural languages. The dilemma of computational com­ plexity vs. linguistic generality has resisted a satisfactory solution ever since Chomsky 1957 argued that competence for natural languages requires at least context-free power in order to

A NEW KIND OF FINITE-STATE ADTOMATON: REGISTER VECTOR GRAMHAB

Glenn David Blank

Lehigh University CSEE Department Packard Lab 1 9 Betblehem, PA 18015

handle embedding of clauses. Moreover, to capture generalizations about categories that participate in variations of order., he introduced transfor­ mations of phrase structure--further increasing .cQmputational complexity (cf. Peters and Ritchie 1973). Similarly, Woods 1970 justified recursion plus the manifold tests and registers of ATNs, which make his scheme "equivalent to a Turing machine in power," because "the actions which it performs are 1 natural 1 ones for the analysis of language."

But natural languages can be modelled by a kind of finite-state device that is quite compact. We can avoid excessive duplication of categories, and having to approximate unbounded memory resources. This is possible--j( we are willing to abandon the functional simplici ty implied by symbols in rule patterns.

II TABLE-DRIVEN FS AUTOMAT!

BelCM are two essentially equivalent ways to design a simple FS grammar: table-driven and network.

Simple (regular) FS automata

Transition Network

Examples: production table-driven

The table-driven implementation consists of 1) a register ( here called the Current Syntactic State Register, or CSSR), 2) a table of syntactic productions (the Synindex) and 3) a machine which initializes the CSSR, makes transitions from state to state, and responds to a final state. The Synindex is a list associating: i) a category symbol, 11) a condition state symbol and 11i) a result state symbol. A machine that recognizes sentences makes transi tions by first matehing a Synindex category symbol wi th a word 1 s lexical category and the production 1 s condition symbol wi th the CSSR; it then replaces the symbol in the CSSR with the production 1 s result symbol. Following the example grammar 1 a transition from N1 to N2 is possible because the CSSR has been initialized to N1, and the category of .s is DET. The CSSR then gets that production 1 s resul t symbol, N2. So long as the list of productions is finite, 1t is a FS grammar. Such a machine has a finite number of possible states, though it can run on indefinitely. The category PREP, for example, iterates back to N1.

A FS grammar requires that every category be determined as possible by a function of the immediately preceding category. Space for the register and index are pre-allocated; no external memory is available. This is as true of the equivalent RVG:

RVG Synindex for simple NPs

In a RVG, the symbols become vectors of features, each capable of three possible values (+,-,±., or "on", "off", "mask", or henceforward 1,0,2). The match function allows either identity or ambiguity (2 matches any value); the change function allows ei ther li teral or masked replacement ( 2 doesn' t change anything). For example, if the CSSR is ini tialized to 1111 , the condi tion vector of DET ( 1222) matches, and the result of DET ( 0222) can be applied, yielding 0111. This is what is meant by functional comolexity: whereas in a simple FS automaton match is identi ty and change is wholesale replacement, in RVG match and change allow ambigui ty and masking. Nevertheless the ternary functions are quite simple and deter­

minate.

Note that the RVG Synindex is considerably more compact than the equivalent FS table. Whereas the FS table has three productions for the category ADJ and six for N, the RVG Synindex has .iY.§1 2M groduction ~ category. The savings--not only of space in the table, but time trying alternatives-­ will mul tiply as more permutations of' order are introduced.

How do RVGs achieve their efficiency? Func­ tional complexity confers two properties that functionally simple grammars do not have: mul tiplici ty and masking. Condition vectors can convey mu1 tiple constraints. For example, PREP (condition 0001) cannot occur until the first three features have been reversed in value. Moreover, result vectors can produce multiple effects: PREP (result 1112) re-enables all NP-opening productions. Note also that dis1oint categories (e.g. N and PHON) share the same position in ordering vectors, so that they mutually excl ude each other. That is, the resul t of N and PHON both disable the same feature (governing the HEAD position). (PRON (result 0000) also rules out · having a post-modifying prepositional phrase.)

Masking is a consequence of ternary values. The third possible value (2) matches any value and does not change any value. Thus constraints may be passed through intervening states. For example, the category N is oblivious to whether or not the categories DET or ADJ have already occurred, since its condition vector (2212) matches the initial state (1111) or the state after DET ( 0111) or after ADJ ( 0011). Thus we can represent Options as well as obliga tions. (Note that the ordering of optional productions is enforced by having successive categories also disable the constraining features, e.g. the result of N is 0002.) Moreover, iteration may be treated as a special case of optionality. Whereas a one-occurrence category disables itself (e.g. the result of DET is 0111), an iterative category does not ( the resul t of ADJ is 0211 ) · Like an optional category, an iterative category is disabled by successive categories up to the next obligatory category (e.g. the result of N is 0002). Finally, masking features allows con­ straints to be held through any number of intervening states--as will be demonstrated when we consider long-distance dependencies.

Finite functional complexity can thus increase the expressiveness of a grammar considerably. It is not to be confused with "complex symbols" found elsewhere in linguistic theory. The sub­ categorization symbols of Chomsky 1965 allow for context-sensitive power; the f'eatures of Gazdar and Pullum 1982 call for recursive elaboration of symbols. Features attached to GPSl phrase structure nodes themsel ves take the f'orm of open-ended trees or directed graphs. The feature vectors of RVG, on the other hand, are finite and do not expand. Moreover, RVG is not an attribute-value system requiring piecemeal inter­ pretation of individual features. Whole vectors (a ternary vector can be implemented as a pair of bit vectors), rather than lists of symbols, are the oparational uni t of on-line processing.

In any case, other researchers have used complex features to govern categorization, but never to describe svntactic ~.

III WH-QUESTIONS

Wh-questions are perhaps the long-distance dependency par excellence. A wh-word (ld:!Q, .1ffiM, etc.) provokes the grammar to watch and wait for a 'gap·--an expected but missing noun phrase. The gap may be filled wherever a noun phrase is expected in a clause:

What is the robot seeking? WH:what; AUX:is; SUBJ:NP:DET:the; N:robot; VTRANS:seeking; OBJ:NGAP:CCLOSE:?;

What is the wrench on? WH:what; AUX:is; SUBJ:NP:DET:the; N:wrench; PREP:on; NGAP:CCLOSE:?;

What did the robot find the wrench on? WH:what; AUX:did; SUBJ:NP:DET:the; N:robot; VTRANS:find; OBJ:NP:DET:the; N:wrench; PREPPOST:on; NGAP:CCLOSE:?;

What is a robot? WH:what; AUX:is; SUBJ:NP:DET:a; N:robot; PREDNP:NGAP:CCLOSE:?;

What did the robot find the wrench? Synindex search fails at: ?

Delaying, for the moment, discussion of embedded clauses, we can see that wh-questions can be modellad straightforwardly.

Synindex fo~ Wb-Questions

Feature Key: 1-SUBJ 2-AUX 3-PRED 4-0BJ 5-PREPPOST 6-NP 7-DET 8-N 9-GAP 10-WH L?: 'L' - consume a lexeme; 'n' - don't

The result of production WH, among other things, switches "on" a feature GAP. Only the production NGAP can turn this feature "off." NGAP can occur in quite a number of places--in fact, just about wherever an NP can occur (except SUBJ). But sooner or later NGAP ~ occur, · inasmuch as CCLOSE requires that GAP have been turned off. The last sentence above fails because GAP is never disobligated.

It should be observed that in RVG the recurrence of noun phrases at various posi tions within a clause does not involve calling a subnetwork. Eschewing recursion, we instead allocate separate sections of the ordering vector type to deal with clause matters and phrase matters. Ternary masking allows the CSSR to preserve its clause-level status while it traverses a phrase. A number of boundary productions--SUBJ, OBJ, IOBJ, PREP, etc.--set a feature which at once temporarily disables subsequent clause-level productions, and enables the boundary production NP. If NP is chosen-­ there are other possibili ties--all of the features ordering a phrase will be reset. One alternative is NGAP, whose condition requires that both the NP and GAP be on, and its result turns both of these features off. Thus NP and NGAP are disjoint.

IV EMBEDDING

Clause embedding was the primary evidence cited by Chomsky 1957 for cl aiming that natural languages are at least context-free. He discusses, for example, the following kinds of struct ur es:

if S1 then S2 if [either S3 or S4lsl then S2 if [either [George sa d that S5J 53

or S4J 51 then S2

The argument goes: i) finite-state automata cannot handle anbn (or "mirror image") grammars because they do not have the memory to keep track of n; ii) 1f ·· then, ei ther ·· or constructions suggest that natural languages are of this type; iii) therefore natural languages cannot be finite­ state.

There are, however, severe constraints on embedding. The most well-known case is that of obj ect relative constructions:

The mouse the cat chased squeaked. The mouse the cat the dog bit chased squeaked.

Embedding object relatives once is not unusual, but twice is boggling. The most common explanantion for this problem is that center­ embedding causes an overload of short-term memory processing. But as Kac 1980 has pointed out, this cannot be the whole story. For if it were we would expect embedding to break down at a predictable depth. But it does not. For example, though one clause can embed another of a different type, there is .llQ. .3.lf- embedding:

If 1f the Pope is Catholic then pigs have wings then Napoleon loves Josephine. That that Dan likes Sue annoys Bob bothers me.

These sort of constructs are plausible, of course, in truly context-free languages such as Pascal or LISP.

Nor are relative clauses a uniform phenomena. First of all, subject relatives are possible indefini tely:

The fellow who saw the dog that bit the cat that chased the mouse is willing to testify.

Object relatives appear to be limited to a depth of one, but combinations of an object relative and a noun compl ement are not:

The statement that the election which he lost ended his career dismays him.

The only one who the fact that George resigned pleased was Tom.

Embedding also goes to deeper levels in order to attach suspended arguments or adverbial adjuncts:

A teacher who wants students who persuade their classmates who don' t know the material to help them to ask him instead must make himself available.

Do you see WhY I wanted to deny that grammar is recursive so vehemently now?

In tfle first sentence, each infini tive clau~>e is projected as an argument of an earlier predicate (~, persuade). All of the relatives are subj ect relatives, so for each no gap is suspended, only an argument. In the second sentence, adverbs are attached to predicates after intervening complement clauses--..§.2 yehemently to ~ and .!lQK all the way back to the main clause' s predicate, ~.

Though short-term memory is related to the shallowness of center-embedding generally, 1t is not an adequate account for the variety of specific constraints. Typically, memory limita­ tions have been regarded as an aspect of per{ormance rather than comoetence. The perfor­ mance processor, wi th limi ted memory, is said to "approximate" competence, which is said to "idealize" the unlimited memory of a CF automaton. Thus when Church 1982 talks about finite-state processing, his aim is just "to design a parser that approximates competence with realistic resources." But one wonders: since memory constraints are universal to the species, why aren' t they of import to models of comoetence? The various constraints on center-embedding argue against the functionally simple notation for denoting clauses (e.g. S or 3-bar), which seems to imply that all clauses are (almost) alike. The versatility possible with the finite functional complexi ty of RVG re-opens the question whether CF power is needed.

If .· then and ei ther .. or are better trea ted as discontinuous constraints than as "mirror-image" syntax. A single feature allocated for each paired construct can give us the Obligations and options we want, with the help of a production to enforce the closure of discourse-level units:

Paired Particles

This fragment effectively enforces these con­ straints: i) IF obligates a THm clause before Dclose; 11) EITHER obligates an EITH-OR clause before DCLOOE; i11) IF forbids another IF until a THm re-options 1t; iv) EITHER forbids another EITHER until EITH-OR re-options it; v) EITHER forbids IF until EITH-OR re-options it. The last case ensures a constraint that Kac 1980 notes but cannot explain:

Either if [clause] then [clause] or [clause]

(A possible explanation· for this constraint is that 1t avoids many ambiguities that might otherwise be brought on by the conjunction QI:.)

In general, embedding can be modelled by any FS automata so long as the maximum depth is finite. Conceivably even a simple FS automaton can manage embedding, by duplicating clause syntax at every possible entry point. But such a grammar would be enormous, and is perhaps justifiably scorned as lacking "explanatory adequacy."

But· ternary vectors can consolidate matters considerably. Rather than having to respecify for every possible site of embedding, an RVG need only keep track of the current ~ of embedding.

The data reviewed in this paper can be managed by keeping track of up to three levels of embedding. The top, or main clause level, is treated differently from the bottom two. Where the grammar does allow us to embed more deeply (e.g. right-embedded complements, subject rela­ tives, etc.), 1t will begin to iterate in the space of the bottom two clauses. Thus we can adjoin arguments or adverbials to the current clause, or one clause higher, or to the main clause, which is always kept. E.g.:

Do you see [wey I wanted [to deny [that grammar is recursive] so vehemently]] now?

The adverbial JlQ. vehemently is attached back over an intervening clause; .llQH to the main clause.

There are two styles in which one might implement clause embedding in RVG. They are virtually equivalent in terms of computational efficiency, but reviewing both will perhaps elucidate RVG methodology. The first is in the same spirit as NP embedding. Just as ordering of phrasal consti tuents is managed by a segment of the complete ordering vector, so each clause level might be treated as a separate segment of a long ordering vector type. Just as several boundary productions (SUBJ, PREP, etc.) suspend further clause-level productions while enabling NP, so other boundary productions may shift attention fran one clause level to another. All of the segments are part of the same vector type, so that there is no need for storage beyond the CSSR, which holds a complete vector. Yet it is possible, because of ternary masking, for boundary productions to, as it were, open and close "windows" on relevant segments. The drawback of this technique is that, for each level, the grammar must replicate the features for clauses (the ordering vectors all get wider), and also replicate most of the clause-level productions (the Synindex table gets longer). Replicating production.s such as SUBJ, CADJ, et al., is necessary in order to apply different condition and resul t vectors at each clause level. Increased size is not necessarily a clinching drawback, since it is by a factor sanewhat less than three (phrasal and discourse-level features and productions need not be replicated). The alternative approach makes for a smaller Synindex, to be manipulated by a slightly more complicated algorithm.

Instead of widening the ordering vector, we add ~ to the CSSR. The new CSSR is mul ti-leveled:

ClauseLevel --> Main clause vector ist embedded vector 2lld embedded vector

The state register is still finite and fully visible; no external memory is needed. Only now it has ordered ~ as well as features. It is as if we broke up a long vector, masking inactive segments with an array subscript rather than ternary values. To embed a clause, the shifting facility increments ClauseLevel, and initializes the lower clause fran the .higher (so that features like GAP can be passed down). To return, it simply decrements ClauseLevel.

This scheme captures generalizations about what clause levels hold in common. It also allows specialized productions to distinguish clause types--wi th different resul t vectors. E. g., the complementizer ~ sets up a complete clause, but the infini tive particle to arranges for a clause starting with a non-finite verb. Similarly, the complex NP constraint (Ross 1967) is easily modellad by different resul t codes. After shifting clause level, change applies as usual. Complement productions allow feature GAP to be passed down (by masking), whereas relatives reset

it:

What did you think that the robot which found? Synindex search falls at: ?

What did you hope to find? WH:what; TENSE:-past,DO:do; SUBJ:NP:PRON:you NPCLOSE: NONFIN:-inf, VTRANS:hope; OBJ: COMPINF :to; NONFIN:-inf, VTRANS:find;

OBJ :NGAP:FILLEDGAP:CCLOSE:?;

Who were you persuaded to find the wrench by? WH:who; TENSE:-past,BE:be; SUBJ:NP:PRON:you; NPCLOSE: PASSIVE:-pastpart,VDITRANS:persuade; COMPINF:to; NONFIN:-inf,VTRANS:find; OBJ:NP: DET:the; NUMBER:-sing,N:wrench; NPCLOSE: PASSGAP: PASSIVEBY:by; NGAP:CCLOSE:?;

Clause-closing productions may or may not insist that GAP be off. RELCLOSE makes this requirement, but does not affect the higher clause, whereas FILLEOOAP does turn off GAP in the higher clause,

and PASSGAP leaves GAP alone.

After the shifting facility has embedded two clauses, it resorts to re-use. That is, the second embedded clause is shifted up to the first. Thus right-embedding can iterate in two registers, but preserves the main clause. Two embedded clause registers are enough to allow the parser to resume suspended arguments or adverbials, as in

• A teacher who wants students who persuade their classmates who don't know the material to help them to ask him instead must make himself available.

But its center-embedding capacity has now has been reached. The parser is baffled by this sentence:

Pamela persuaded the robot who wanted to give the pyramid which was on the blocks which it found to her very much to find a wrench instead.

By the time it encounters ~ ~. the clause to which the adverbial might have been attached (~ ··· ) has been lost to re-use. But such a sentence is beyond the tolerance of maey human

speakers as well.

Superficially this embedding scheme resembles a bounded stack. But there are some crucial differences. First of all, a bounded stack scheme (such as that of Church 1982) typically calls for a great deal more storage than just three registers, since it will have to keep track of the full gamut of embedding implied by PS rules--NPs, VPs, X-bars and the like. Second, whereas functionally simple systems treat every level of embedding alike, in RVG each level of embedding is marked--main clause, first embedded, re-usable. Thus in RVG there is no W,r-embedding. Third, CSSR levels are oot really organized like a stack, since the lower two registers are re-used i teratively, and the main clause register is always preserved. In fact there is nothing which prevents a RVG from accessing clause levels in another order. For example, we could model cross-serial dependencies in Dutch (see Bresnan et al. 1982), by allowing boundary productions to access storage registers in a queue-like order. (Assuming that cross-serial dependency, like center-embedding, is limited.)

V Tal ARD A COMPLETE RVO SYSTEM

RVG syntax may be thought of a general-purpose scbeduler, witb potential applications wberever such a device would be desirabl e. Generally, non-syntactic procedures can be scheduled by association witb Synindex productions. Indeed, syntactic productions are motivated by non­ syntactic requirements. For example, nouns, pronouns and names are very s1m1lar posi tionally, but tbey are treated as distinct categories because of semantics. In this section I will briefly describe how an RVG can, while maintaining modular autonomf to a considerable degree, support integration of processes.

Categories. In earlier versions of RVG, categories, like ayntactic ordering and semantic constraints, were represented in terms of ternary feature vectors. Ternary values supported cross-categorization well--lexemes in more tban one category could allow them with 2 's. But since RVG holds down duplication of productions, it is feasable to associate, with each lexeme, a list of Synindex production numbers. Moreover it is possible, with some pre-processing, to let these production numbers be generated from labels, and also to infer the set of non-lexical productions that could precede each lexical production. Thus, for example, the lexeme ~ is categorized by the label H, which is converted to a production number; the non-lexical production numbers for SUBJ, OBJ, NP, etc., are kept in a precedes set associated with the Synindex entry for H. This approach is at once more convenient, because categories are kept functionally simple with respect to notation, and more efficient, because the lexicon is 1 wired 1 directly to the Synindex, obviating any on-line processing of categories.

Semantics. RVG syntax can in fact support just about aey form of semantics. But I present our biases. Since RVG permits a relatively flat, direct treatment of permutations of order, there is no reason to complicate matters--as trees do, since they imply recursion. Rather than transform syntactic structures, or propose meta-rules or lexical-dependency subtrees which have s1m1lar effect, why not let categorized actions oparate upon semantic structures directly? The problem of mapping consti tuent structures into lexical structures is simplified by just eliminating context-free consti tuent structures. There is no need to move or unify sub-trees in RVG; there are no trees at all. Moreover, semantic and morphological agreement can be simpl ified: there is no need to 1 percolate· or 'inherit' features up and down trees, nor to design special fil ters or powerful constraints to regulate such activity. Functional complexity allows RVG to be sensitive to context without being context-sensitive in the sense of the Chomsky hierarchy.

In RVG, registers Registers, relations. we allocate a fixed configuration of (the Current Predication State or CPSR) for managing grammatical The CPSR and CSSR together comprise the state of a clause (or a pbrase in a clause), and as shown above, RVG keeps track of up to three clauses. Permanent semantic representation is buil t up dynamically ( it is here that we allow open-ended structures); CPSR slots hold addresses of proposed semantic referents.

Categorized actions (associated wi th ayntactic productions) have the responsibility of mapping new lexical material into existing semantic structure. In the spiri t of RVG, lexemes are viewed as standardized in structure. All semantic features are organized in a single vector type, the first-order semantic vector. Every lexeme has an IHTRINSIC first-order code. Constraints on arguments of predicates are specified, as needed, in terms of additional first-order vectors. First_Order_Pred, a generalized procedure called by many categorized actions, for all arguments, first matches vectors ( thus checking selectional restrictions), then unifies them. E.g., 22201 matches 01202 and yields 01201. Thus in RVG features are not used merely to validate, but also to ~ semantic structures.

Morpbology. Kunst and Blank ( 1982) show that morphology can be efficiently implemented as a retrieval troee, with provision for morphological paradigms as nodes encountered during lexical lookup. Currently, we represent morphemes as lexemes in their own right, each with its own list of Synindex production numbers and semantic structure. Thus, for example, lookup recognizes .sli.U as two lexemes: -.12l..l.!l: and ~. The lexeme -Rl..W: has an INTRINSIC vector (distinguishing 1t from -.äng). It also lists the subscript for the Synindex production NUM3ER, which maps the IHTRINSIC of the lexeme (-J2l...l.ll:) to CPSR[Head], and then calls First_Order_Pred: thus enforci,ng number agreement. Another morphologically categorized production, TENSE, enforces 'subject-verb' agree­ ment. Actually, ~ kittens .1§ olaying fails at TENSE, whereas ~ ~ ~ playing violates constraints at VTRANS. But note that .äll. agreement is managed by uniform operations upon a Single vector type.

Letters must have been being written. roBJ:NP:NUM3ER :-plur, N:letter; NPCLOSE: TENSE:-pres, KlDAL :must; NOOFIN :-inf; HAVE :have; PERF:-pastpart,BE:be; PROG:-progpart,BE:be; PASSIVE:-pastpart,VTRANS:write; CCLOSE:.;

Discourse, etc. RVG does not require that 'S 1 be the root of ayntax. The examples in this paper suggest that a discouse-level ayntax could be integrated as part of the Synindex, or as a separate production table interfacing with the Synindex. Paired partielas were modellad as discourse-level discontinuity, and wb-questions are marked by a feature switched on by the production WH. Generalizations about ayntax, expressed by features in vectors rather than by complex rule patterns, are thus more readily available to other aystems.

RVGs are highly reversible. A parser and a generator can be implemented (and have been) using the same Synindex and basic table-driving algorithm. Indeed, all of the major data structures of RVG work in ei ther direction as is; only the procedures need actually be reversed. While parsing, discourse-level features are set by syntax for higher-level consideration. While generating, discourse-level features are set from above to choose particular sentence forms.

RVGs are computationally simple and compact. The basic algorithm is that of a table-driven finite-state device, modified to invoke ternary match and change functions. Ternary vectors can be represented on a binary computer by paired bi t vectors. Ternary match and change are implemented by combining logical operations (exploiting the 1 ow-1 ev el parall elism of bi ts in canputer words) · The most recent version of RVG, in Pascal (earlier versions were in SN <BOL and Icon), does so, wi th great gains in speed. On a DEC-20, the ayntactic parser averages about 5 milliseconds per lexeme. Further improvement is possible--on ternary circuitry.

Expansion to fuller coverage (a substantial fragment of English syntax has been implemented) will have a minimal slowing effect, since each new category motivates one new production, rather than many new rules (or a meta-rule that generates many rules). Each revision is on features already allocated in all productions. Occasionally new features must be allocated, but most frequently early in grammar-making, and least frequently late.

Ambiguous parsing to be sure slows processing down, though not unbearably. The canbination of well-specified category vectors, semantic con­ straints and possibly a form of bounded parallelism (under investigation) can hold syntac­ tic processing time to a · small linear time. Thus parsing of natural languages appears to be feasable by machines in real time. Indeed, syntax ~ be fast, 1f it is to facilitate the many other processes--fran phonology to reasoning-­ which all go on in real time.

ACKNaß.EOOEMENT

RVG originates in unpublished work by A. E. Kunst, to whom I am also grateful for help with this paper. In an unpublished paper, Professor Kunst compares RVGs to Petri nets ( rather than simple transi tion networks). Petri nets also allow functional complexi ty. Specifi­ cally, he compares of aafe Petri nets (which are known to be weaklY equivalent to FS automata) and RVGs.

REFERFliCES

1. Berwick, R. & A. Weinberg. Parsing efficiency and the evaluation of grammatical theories. Linguistic Inquirv 13:4 (1982) 135-191.
2. Berwick, R. Bounded context parsing and easy learnability. ~. ~ .ACI,., Stanford, Palo Alto, 1984, pp. 20-23.
3. Blank, G. Lexicalized metaohors: .A cognitive ~ .in ~ framework .Qf Rerlster ~ semantics. PhD thesis, University of Wisconsin-Hadison, 1984.
4. Bresnan, J., R. Kaplan, S. Paters and A. Zaenan. Cross-serial dependencies in Dutch. Lingyistic Inguiry 13:4 (1982) 613-35.
5. Chomsky, N. SVntactic structures. Mouton, The Hague, 1957.
6. Chansky, N. Asoects .Qf ~ ~ .Qf ~. MIT Press, Cambridge, MA, 1965.
7. Church, K. Qn ~ limitations i.!l natural language processing. IU Linguistics Club, Bloomington, Indiana, 1982.
8. Gazdar, G. & G. K. Pullum. Generalized ~ structure grammar: ~ theoretical synopsis. IU Linguistics Club, Bloomington, Indiana, 1982.
9. Kac, M. On the recognition of complex NP's. Worlcshop .211 Language Processing .rull1 Acg_uisi­ ~. Brown University, Providence, RI, 1980.
10. Kunst, A. E. Petri net theory and the repre­ sentation of natural languages. Unpublished paper, Comparative Literature, University of Wisconsin-Hadison, 1983.
11. Langendoen, D. T. and Y. Langsam. The repre­ sentation of constituent structures for finite-state parsing. ~. 22n!1 AQI,.. Palo Al to, 1984, pp. 24-27.
12. Perrault, C. On the mathematical properties of linguistic theories. ~. z.w. AC~.., MIT, Cambridge, MA, 1983, pp. 98-104.
13. Peters, ·P. S. and R. W. Ritchie. On the gen­ erative power of transformational grammars. Information Science 6 (1973) 49-63.
14. Pullum, G. Context-freeness and the computer processing of human languages. ~. Z.W. AC!.. MIT, Cambridge, MA, 1983.
15. Pullum, G. Syntactic and semantic parsabili­ ty. ~. ~ AQI,., 1984, pp. 112-22.
16. Ross, J. Constraints .211 variables .in~. PhD thesis, MIT, 1 967.
17. [ 17] Woods, W. Transition network grammars for natural language analysis. g.,w 13:10 (1970) 591-606.