Reversible Automata and Induction of the English Auxiliary System

REVERSIBLE AUTOMATA AND INDUCTION OF THE ENGLISH AUXILIARY SYSTEM

RobC'rt C. ßprwick SamupJ F. Pilato

MIT Artificial IntC'lligc·nrc Laboratory· 545 T<'duwlogy Square Cmnbriclv,e, MA 02139, USA

II LEAR.NING K-REVl;;llSIBLE LANGUAGES ----- -- - ~~1i0:M~}i}_X;!\._ME:kK~--- ... --- ---- ----

The qtH·st iou WP aclclrcss is , If a ]('amcr pn·stuuC's that a uat­ nral langHa~C' clomain iR syst.Pmatir iu somc· way, cau the lcamc·r intdligPntly infPr thc· cmnpkt.e systc·m from cmly a sHbsC't of sam­ ple seutc·ncps? Let IJS clc·wlop <UI cxampk to {(mnally cksrribc what WC' uJC·an by '·sy"l.l'llHÜic in snmc way," awl how such a sys­ tc·mat ir domain allows thc infc·n·ucC' of a complC't.e system from c·xamp!Ps. lf yon WC'f<' tolcl timt Mary lmkcs cake .~, John bakeB cakcs. and 11-fary eals pies an· legal strin~s in soml' langnagc, yon might gupss that .lohn cats pie.~ is also in that langnage. St.rings in the language scem to follow a recognizahlc pattcrn, so you cxpcd other st.rings that follow thc same pattcru to bc in thc langnage also.

In this particnlar case, you are prcsnming that the to-be­ learnecl lan~nagc is a zcro-rewr~iblc rcgnlar laHgnage. Angluin (1982) has dclinccl aucl cxplored thc formal prop<'rtiPs of reversible rcgnlar languages. Wc hcrc translate somc of her formal dcfini­ tions into less technical tcrms.

A rcgnlar langnagc' is any langnagethat ran be gcncratc·cl from a formula callc<l a rq;ular C'XprC'ssion. For C'Xamplc thc st.rings nwntionc<l abovc migbt have come from the langnage timt the following rcgular C'Xprcssion gcncratcs:

(MnryiJohn) (bakcs!eats) [[vcry" delicions] (r.akeslpies)l

A romplct.e natnml langnage is t.oo complcx to be gencrated by souw concisc rq~ular cxprpssion. but sornc simple subsets of a natural languagc Glll lit. this kincl of pattern.

To formally dcfin<~ whm a rc·gnlar langnage is reversible', Iet us first ckfinc a prd!x as any sul>st.ring (possibly ?.C'ro-length) that cau be fonncl ;:ü thc vcry IJC'ginning of somc lc·gal striug in a l:tn~nagc, and a srtirix as auy snbotring (a~ain , po:<sibly zcro­ lcngth) timt can he fonnd at the vcry end of somc legal string in a langua~e. In om casC' t,hc strings are sc·qncnccs of 'words, ancl tlw l:m~uatjl' is I he sd of all l<·gal scntenccs in our siruplified subsct of gngli sh. AJ,;o, in any h;al string say that thl' snffix that immC'cliat.dy fo.llows a prdix i,; <l t ail for that prcfix. Tlwn a n·gnlar langnage is zero-revcro~ib[,: if whcncvcr tw" prefixes in thc languag<' havc a I ail in conunon, then thc two prcfixcs havc all tail» iu comrnon.

In tlH' abovc c·xampiC', prdixC's MHry ancl .lohn have thc tail hake.~ cakf:.< in ro!lltliOII. If WC' presume I !tat thC' l.'lnguagP tllC'sc two st.rillgs comc· from is ZC'ro-rcvt·rsiblP, thc·n 11-fary il!Hl .lohn umst have all1 ails in connuoJJ. In partiruhr, t ltP thircl st ri11g sbows that Mnry !Ja,; wls l'i~:s ao< a tail , so .lohn mnst abo have t:af.~ pieB a,; a tail. Onr c:nrrmt .hypotlw,;is aller having ,;ccn thPsc tltrc·l' string8 isthat tlH'y cnnlc' not from t]a· tlirr·<'·''tring la11gtt:t~~<' PXJH'C'SRccl by ( 1\fa.ryi.John) bal.: r;o~ '"'kc.~ I 1\Inry c"h J>ir:o~ , which is not Zl'ro­ n··,,,y,;j!JJ,., 11111. ratltn fnll< l tltc· fmtr-:<tring languagc (Mary!Jnhn) (hake.< wkr:.1 I "'"·' l'ic,<) , wl ti c:h is zc·ro-rc·wrsiblc·. Notire t!tat. WP bavc· Pr.laq~~d I lH' coqHt:-: jn:-;1. <'JJcngh tn tn ;tJ~(' 't~H' langnag<' zero-rc'V<'rsihlc.

ABSTRACT

Tu thi,; papc·r wc· <tpply somc· rc·n·ut work of Augluin (1982) to t hc· indnction of th<' En~]i,;h auxiliary V<'rh sy:.;t<'m. In ~c'H<'ral , t h(' inclnction of finite· antomata is compntatio11ally iutractah!C'. How<'vc·r. An~lnin ;llow,; tbat r<',;trictPd finite· antomat.a, tlw k­ rcvfr.<ihlt: auto1uala. rau bc· lc·am<'d by d!iri<'nt (polynomial time) al~orit !im;. Wc· pn·".·ul m1 c·xplirit coHtJHII.<T mockl c!Pmomt.rat­ in~ I bat tll<' Engli,;!J anxiliary wrh syst<'lll can in fact h<' karned a; a1-n·vc-r;ibk antomatou. ancl hc·un· in a rompntat.ionally fc·a~i­ hlP illliOtiiJt of liltH'. Thl' <'lllire systemraube acqnin·d by Ionking at nn!y halft ltc· pos;ibk anxiliary wrb s<'qnmcc·s, ancl thP pattcrn of ~<'nPralizat iou ,;c·c·ms rompat ihll' with what is known abont Im­ man au]nisition of anxiliarics. We concliak tliitt certain lingnist.ic snb,;ystc·ms may wdl hc· karnahle by incha:tive infnence methods of this kincJ. ancl su~gC'st an cxtc·nsion to context-frce languagcs.

Fonual incl11C:t.ivc· infPrCJJC<' mC'thoclö have rarcly bC'en applicd to actnal natnral laugnagc systc·ms. Lingnists ~;t'IIC'rally snppose tbat langnagcs an· easy to learn h<'ranse graruutar;; are highly con­ ~traiuecl; 11o "gc·nc-ral pmpns,·'' iucluctive inf<'rcnc:e mcthocls are rccp1irecl. This assnmption has gl'uerally lecl to fmit.ful insights ou tlw natme uf grauunars . Yd it r<'maius to dctcrmiue whcther all of a langnage is lc'anwcl in a grammar-sp<·cific: manncr. In this papc·r we sltow lww l.o sucrC''"fnlly apply onc computationally et!i­ ri C'ul. iuduc:tivc· iufcrc·urc· algoritluu to thc acqnisilion of a clomain of English syntax. Om resnlls "'gr(C':it timt partindar language su!.systcms can h" kamcd by g<'neral iurluc:tion proccclures, givrn t:erL:1i11 g<·JH'ral roustraints.

Thc probkm is that thesc Jnethods are in ~crwral computa­ t ioually iutract abk. Ewu for rc·gt ilar languagc·s iJI(lnction c;m bc <'X)l<>ti<'Htially clil!irnlt. (Gold, 107R). This sugg<'sh; timt t.hcr<' may iH' ~~<' ll<'ral coBsrrainls on the dc·<'ign of cert.ain lingnistic subsys­ t<'lliS tu mak<· thcm c'asy to lmm by gml'ral iucluctivc iBfcrcncc mcllwcb. We proposc· the rcmstmint of k-revcrsibdity as one such n·st rirtinn. This comtraiut gnar;mtc·P:< polynornial timl' infc·rcncc (Angluin, 1082). !11 thc n·mainckr of this papPr, wc also show, by au C'Xplicil compnlc·r modd, I hal thc' Engli:ih anxiliary vcrb ~yslem mert" this qm,;traiut, aud so is c·asily infc·rrc<l from a cor­ pn,;. TIH' thC'ory givc·s onc prC'c.isC' charactc'rization of just wherc W<' ruay <'XfH'd ~t'lwra l iucluctive iufNencc nwihocls t.o bc of valne in lnnguagc arqulsitiun.

· This paper dcscrihcs rc·search clone at the Artificial Iutelligcnce Lahomtory of the MassaclmseUs ln:;titntc of Technology. Sup­ port for thc laboratory's artificial intdligPIICC' rcsmrch is providcd in part by the Advancccl Research Projccts A~cncy of the De­ partnH'Jtt of DPfcmc nuc.lc:r thc Oflicc of Naval Research Contract NOOO l'l-80-C-0505.

A rq~ular languagP is k-rever.lible , whPr<' k is a nou-uq~ative int.PgPr, if wh<'IWV<'r t.wo prdixC's whoo~e la8t k wordo~ match have a tail in ronu11on, t.hen t.hP t.wo prdixt·s havP all t.ails in com­ mon . A highPr value of k gives a mor<' couscrvativc comlition for iukn'nrt·. For PXillllplt·. if W<' prt·smn<' that. thc aforcnH·ntioncd strings rmn<' from il 1-r<'vPrsible lauguag<:, theu instcad of pre­ sumiug that whatC'ver Mary dtws .lohn doPs, wc would presume ouly that whatC'V<'r Marylmkes . .lohn hake.<. In this case t.!lC' third striug fails to yidd auy iufercucc, bnt if wc wen· lat.er told that Mary bakcs l'ies is iu thc lauguage, wc conld iufer t.hat .lohn bnkes 11ies is also in the languagc. Further atlding thc seutcncc Mary bakc8 wonld allow !-reversible infcrence to also iuducc .lohn bakes, rcsnlting in the SC'Veu-string 1-n:versible langnage expressed by (Maryi.John) bakes [cakeslpies] I Mary eats pies.

With these examples zero-reversible iufcrcnce would havc gen­ cratcd (Maryi.John) (bakr..<leats) (wkc .<l pics)* by now, which over­ generali?.cs an optional dircct objcct into zero or more direct ob­ jects. Ou the other hand , two-rcvcrsihle infereuce would have infcrred no additional strings yct. For a particular langnage we hopc to till(l a k that is small <'nough to yicld some infcrcnce bnt not so srnall that we overgeneralizc aud st.art infer ring strings that are in fact not in thc truc langnage we arc trying to lcarn.

III AN INFERENCE ALGORITHM

In adrlition to formally charact.erizing k-revcrsible languages, Angluin also developed an algorithm for inferring a k-n·versible langnage from a finite ~ct of po~itivc exampl<'s, as weil as a rncthod for discovering au appropriatc k when 1wgative exmnplcs (strings known not to bc in thc languag<') ar<' also prcscntcd. Shc also prescut.cd an algorit.hm for determiuing, giveu sorn<· k-rcversible regular laugnage, a minimal sct of sllortt>st. possible cxampll's (a "charad.C'ristic" or "covcring" sample) sulticient for iwlucing the languagc. Wr llave impkuwntcd t!Jcs<' proccdurcs on a compnter in MACLlSP and havc applied thc·m to all of thc art.ilicial lan­ guages iu Augluin's papcr as weil as to all of the naturallangnage examplt.>s in this paper.

To dC'scribc thP infer<'m·c algorithm, we makc nse of thc fact t.hat. cverr rcgalar langnage can be associat.C't! wit.h a corrcspond­ ing dctcrmiuist ic finite-st.atc automaton (DFA) which acccpts or gcneratcs cxactly that lauguage.

Giv('l! a samp!C' of st rings takcn frmn t.hc full corpus, wc first g<'nC'fatc a pr<'lix-tr<'l' :uüomat.on which acc<'pt.s or I~<'Ilt'rat.C's ex­ act.ly thos<· str i11 gs a!Jllno olht·rs. W<' no'.v want to infer ;:Jd it ional ~t.ri ugs so as to imlncc 11 k-r<'V<'l'sibk lilngua~~<' , for somc rhoscn k. Let us say t.hat. wlwn arrq>t.iug a l-.tri11g. t.ht· last. k :<ymbols encmmt.cn'd brforc nrriving at. a stat e is a k- lwder of that stat<'. Th<'n t.o gcu<'rali?.<' tlll' laugnagt', W<' r<'cnrsiwly lllt'rgl' any two ~tat.t·s wht'fl' auy of tlll' following i~ trn<':

• ·Anothl'r ~tat<' arrs to bot.h st.at.es on th<' same word. (This euforr<'s dct.Pnniuism.)
• ·Doth st.at.Ps hav<' a common k-kad<'r and either
• bot.h st.atC's are arrepting stat.C's or
• -both states arr to a common st.ate on the samc word.

Wkn w ·.:c of thPse condi t. ions obtaius any longcr , the rcsulting DFA acrepts or g<'Il!'rat .C's the smallcst k-r<'Vt>rsibl<> langnage t.hat inclmlcs the original smupk of striugs. (The l<'rm "reversible" is usctl bcranse a k-rcv<'rsihlc DFA is still det.crminist.ir with Iooka­ lwad k when its scts of iuitial and final states arc swapped and all of its arcs are rcvcrscd.)

This procednre works incremcnt.ally. Each new string may be added to the DFA in prctix-trec fashion and the state-merging al­ goritlJm rcpca t.cd. Thc resulting langnage iuduccd is indcpendcnt of the order of prcscntation of sample strings.

If an appropriate k is not known a priori , hut. some negative as weil as positive examplcs are prcsentcd, thcu onc can try in­ creasing valnes of k until thc indnccd langnage contains nonc of thc negative examples.

IV INF~RI!!_NCE Qji'_ THE ENGI,ISH A UXILIARY SYSTEM

Wc havc choscn to t.cst thc English auxiliary syst.cm nmkr k-rcversible infcreucc bccansc English vcrh s<'qucnccs are highly regular , yct thcy have some dcgre<' of complcxity a!Hl admit to some t'XC<'plions. We rcprescnt the English auxiliary sy:.;tcm as a corpns of 02 variant.s of a dC'clarativc st.at.cmcnt. in third pcrsou siugnlar. Thc variants covcr all stam];u·d kgal p!'rtnnt.ations of t.cnsc, aspect .. and voirc, iucluding do snpport and uinc modals. Wt· simply usc thc surfac<' forms, whiclt are st. rings of wonls with no a<lclit.ional informatiou such as syutactic cakgory or root-by­ iuUcct.ion breakdown. For iust.ancc, t.hc prcscut, simple, act.ive cxample is .ludy yive.l hread . One modal, pcrfcctivc, pa;;sive vari­ ant is .Judy would havc bew given bread.

We have explort'cl t.he k-revcrsiblc propt'rtil'S of th is uatural langnage subsy~tPm in two main sl1'ps. First. W<' d<'krmincd for what. valncs of k tht· corpus is in fact k-n'V<'rsiblc. (Civcu a finite corpus. we rould be Sill'<' tlH· lan~uag<' is k-n'V<'rsihk for all k at or abuvc some vahtt'.) To do t.his we lr<'aled t.he fnll corpns as a set. of ,-amplc stri n~;s and tried S IH'rt·~sivPl y largt·r valn<'S of k nnt il !iuding one wh··n· k-r<'VPrs iblP illft'fC'Il<'<' appli<'<l to th<' corpus g<'rt!'fa!t·s uo ad1litional strings. We rould t.hen h<' Sil l'<' lhat ;my k ofthat vahl<' or great.cr conld hP us<'d to inf<'r a11 acrurat.e model of thc English anxiliary sy;;tem without overgeucrali?.ing.

After finding t.h<' rang<' of valncs of k to work with, W<' wcre irlt.<'restcd in detcrmining which , if any, of tho;;e valucs of k would yi<'ld some power to infer thc full rorpns from a proper sn hset of cxamplcs. To do this we t.ook Uw DFA whirh rcprPscnts the full rorpns and cornput.cd, for a trial k, a sct of samplc st.rings that wonld bc minimally snffiricnt t.o inducc thc full corpns. If any such valncs of k exist, thC'n we can say that, in a nontrivial way, thc English auxiliary systcm is lcamable as a k-rcvcrsible langnage from examples.

We fonnd that the English anxiliary system can be faithfnlly modeled as a k-revcrsiblc regular langnage for k 2: 1. Only zero­ reversible iuference ovcrgcncralizcs thc fnll corpns as weil as the active and passive corpora treat.cd as sPparatc langnages. For the activc corpus, zero-reversible inft>rencc groups t.hc forms of do with the other modals. Thc DFAs for thc passive and fnll corpora also contain loops and thcrcby generate infinite numbers of illegal variants.

Docs trcating the English anxiliary systcm as a 1-or-morc­ reversiblc laugnage yicld any infcrcnt ial power? Thc English anx­ iliary systcm as aI-reversible languagc can in fact hc inferrcd from a covcr of only 48 cxamplcs out of thP 02 variant.s in thc corpns. The activc corpus t.reatcd scparat cly rcqnires 38 examplcs out of 46 and t.he passive corpus reqnircs 28 out. of 46. Treat.ing the fu ll corpus as a 2-rcversiblc languagc rcquircs 76 examplcs, and a 3+­ reversible model cannot infcr the corpus from any proper subsct whatsocvcr.

For 1-revcrsihle infercnce, 45 of t.he vcrb sequcnrcs of lcngth thrcc or shortcr will yield the r<'maiuing ninc such strings and none longcr. Verb scq1wuces of kngth four or fivc can be di­ vidcd int.o two patt.erns, <modal> havc been giv( inul cn) and ... bc[en] being yiven . Adding any one (l<'llgt.h-four) st.riug frorn the first pattcrn will yidd thc remaining .l7 st.rings of that pattern. Further adding t.wo leugth-fonr striugs from t.he awkward second patt.crn will yield the rcmaiuiug 18 st riugs of t.hat pattern, nine of which are of ]('ugth fivc. This completcs the corpn8.

Thc auxiliary sy~tem has often l>··ca regardcd as an acid tcst for a t.hcory of laug1t.1:~~' arquisition. Givc·u this, we arc cncour­ ag<'d thal it is in fad 1<-antahle via a compnt.ationally f'fficicut gl'll<'ral 1n<'i.ltod. It i~ ,;i ~niliraut. t.hat. at lc·asl in this domain wc have fnuud a k (oft) t.l!at is low c·nollgh lo :~<·m·rat." a good ammmt of iuf,·n·nn· frolll <'Xilll!plt·s y<'t. high CllOllf;h t.o avoid owrgcncral­ i~at.ioa. Ew11 llJOr<' !'l>ll:<i'l'Valive 2-rcv!'rsihilit.y gm<·ral<·s a littlc inft·reHn'.

This indurtiv<' powl'r <krivl's from t.hP syst.f'matic SI'CJllPnt.ial structun· of t.he English auxiliary syst.<'lll. In au ickali~<'d form (ignoriug l<'llS<' aud infkrtiom) thc rcgular I'Xpr!'ssion

[DO I [<modal>] [HAVE] [BE]] [BEpassive] GIVE

g<'IH'rai<·;; all English vcrh s<'<}llt'nr<' patt.erns iu onr corpus.

Zero-ri'Vf'rsibk infl'f<'lll'C basically at.tcmpts to simplify any partial. di,;j nnctivP JH'flmtt.atioulike (a Jb)x J ay int.o mt cxhanst.ivc, combiuat.orial pPrmut.atiou likf' (ajb)(1:jy). Siun· thc art.ivc cor­ pus (exrhtding ßE-pa88ivc from the ideali~ed rPgular cxpr<'ssion) iu fact. lws such a simple form <'xcept for t.hc DO disjuuction, zero-reversible infercncc productively completes thc thrce-place p<'rmntat.ion but nlso dc~troys t.IH' disjunction, by ovcrgcneral­ iziug what pat.tcrns can follow both DO and <modal>. One­ revcrsiblr iufcrcncc rcquircs t.hat. disjuncts ~hnre some final word to be mcrgcable, so that DO caunot nwrgc wit.h any anxiliary triplet , yct thc pcrmutation of <modal> HAVE by [BE] is still product iv<'. Similar cousidcrations obtain in the passive case, as weil as for thc joint corpus.

In complcx enviroumeut.s, rather than rcducc thc iufcrcntial power by raising k onc conld imtcad cmbcd this algorithm within a !arger sy,;l<·m. For cxamplc, a rnore realistic modcl of processing Engli>'h vc·rb scqHeBc<'s wonld have an extcrnal, morc linguistically motivatcd nwchanism forcc thc separate tr('at.ment of activc vcr­ sus passive forms. Then if, say 011 comiderations of fn·qnency of occurrcnr.c, do cxceplions wcrc Pxternally handkd and thc in­ frequent. ... ßE bcing ... cascs wcrc similarly cxcludecl from the immature lcarner, tll('n ouc could apply the more powf'rful zero­ reversible iuferencc to t.hc remaining activc and passive forms without ovt·r~<'fll'ralizing. In such a catit' thc activc syskm can bc iudnced from 18 examplcs out of H variants and the passive systcm from 14 out of 22. Thc cntirc activc systcm is karnable oncc examples of carh form of mch vcrh aud cach modal have bccu scen, plHs OIW c·x;.unplc to fix thc n ·lat.ive ordcr of hat·e vs. bc, and oue cxample cach to fix thc ordcr of modal vs. have or be.

ThoHgh a morc contplf'x motlel must ult.imatcly rcprc·scnt a domain like t IH' English auxiliary systcm, t.he way k-revPrsible infereun· .iu i!.,;t·lf hatullt·s a coutpkx lc·rritory sat.i~fies somc con­ ditions of ]J>;yrltological Ji<lelit y. Especially ~cro-rev<'rsibility is a ral hc·r si111plc form of i\< ' ll<'rilli~at.iun of S<'<JU<'Htial pattC'rns with wltirl! Wt' hl'licw· hum;ut s rmdily idcntify. Iu gen<'ral the hmgcr, morc cotnpkx rases Ci.lll IH' iuft'tTf'd fi·om si11tpler cascs. Also, t.hc·rc i,; a n·asouahl<· d< ~ grc<' of play in the COlll)HJsitiou of the cov­ t·rin~ ~illllplt·, an<l th·· ordl'f of pn·sent<ttiou dot'S uot. alf<'ct. lhe langnage l('arll<'d.

Childn·u t·vi<kntly ll<'vc·r lllilke mistakf's ou thl' rC'lat.iV<' order of illlxiliari<'~ , wl1idt is ronsi,tt ·Jll wilh t.he JTV<'rsihility modd, bnt tlli'Y do mistak<·nly c:olllhilll' do wit.h t.('us.·cl vnb fonns (Pink<·r, 1984). (;iv<'ll t!tat tlu· app<'armtre of do iu <kdarativt' sl'llt<·nres is abo fairly rare, ont· might pr<.fl'f t ht· afor<'llll'lll icnH·d ~Pro­ n·vt·rsihl<· syst.t·m that handks do ><Hpport as au except.iou, rather thau opt for a 1-n·versibh· inf<'rt'lln' which is tlawl··ss but a slower l<·arner.

Thc ... ßE being .. . cas<'s an· syst.C'ntatirally rPlatcd· to the rest. , bnt also havc a natural hmmdary: 1-rcvcrsiblc infcrence from simpkr casc·s do<'m't int.rud!' iuto that territory, y<t only a fcw sHrh cxamplcs allow on!' to inff'r t.ll<' remaimlf'r. Vcry rare scqnC'nccs like could have been being given will be successfully acquircd <'Vl'll if tlwy are not secn. This scC'ms cousistent with humau judgments that such phrasiug is awkward bnt apparently legal.

k-Revcrsibility is essentially a modcl of simplicity, not of com­ plcxity. As such, it induccs not liugnistic struct.urc but the substi­ tution classes that liuguistic structurcs t.ypically work with, build­ ing thcsc by aualogy from cxamples. In thc linguistic structure for which k-rcvcrsibilit.y is dcfincd - rcgular grannnars - it func­ tions to inducc t.he classcs that fill "slots" in a regtdar cxpression, based ou thc similarit.y of tail sets. Incrcasing the valne of k is a way of rcquiring a lügher dcgree of similarity bPfore calling a match. (Sec Gouzalcz and Thomasou, 1978, for othcr approachcs to ·'·ta.il inferencc that are not so efficieut.)

Thc same principlc cau apply to thc induction of su bstitution classes in ot.her linguistic domains including rnorphological, syn­ tactic, and semantic systcrns. For a particularly dircct cxamplc, considcr thc right-hand sidcs of contcxt-frec rewritc mies. Any subsct of such ruks haviug tbc sarnc lcft-hand side constitutes a regular langnage ovcr thc sct of t.cnuiual and nonterminal sym­ bols, and is thercfore a candidatc for induction. Onc might thus infcr new rewritc rules from the pattern of existing ones, thereby not only coucluding that word:> are mcmbcrs of certaiu simple syn­ tactic classcs, but also simplifying a disjunctive sct of rulcs iuto a morc coucise sct that exhibits systcnwtic proper t ies. Dcrwick's Lparsifal sy~tcm (1982) is an cxample of this kind of extcnsion.

Wc bclicve that. k-rcv!'rsibility illustratC's a psychologically plausible· pat.t.t·rn induction proccss for natural langnage lcarning that in it.s sirnplcst form has an cfficicnt. cornputatioual algorithrn associated with it. Tltc basic principlc behind k-rcvcrsible infer­ encc shows somc promise as a flexible tool within morc complcx models of langnage acquisit.ion. It is C'ncmtraging that , at least in a simple case, computatiouallinguist.ic modcls can ~uggcst for­ mallearnahility constraiuts t.hat arc natural cnough to bc useful in the lcamin~ of human lauguagcs.