%!PS-Adobe-2.0 %%Creator: dvipsk 5.58f Copyright 1986, 1994 Radical Eye Software %%Title: paper.dvi %%Pages: 5 -1 %%PageOrder: Descend %%BoundingBox: 0 0 596 842 %%DocumentFonts: Times-Bold Times-Roman Times-Italic %%EndComments %DVIPSCommandLine: dvips paper.dvi %DVIPSParameters: dpi=300, compressed, comments removed %DVIPSSource: TeX output 1996.05.02:1607 %%BeginProcSet: texc.pro /TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N /X{S N}B /TR{translate}N /isls false N /vsize 11 72 mul N /hsize 8.5 72 mul N /landplus90{false}def /@rigin{isls{[0 landplus90{1 -1}{-1 1} ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[matrix currentmatrix{dup dup round sub abs 0.00001 lt{round}if} forall round exch round exch]setmatrix}N /@landscape{/isls true N}B /@manualfeed{statusdict /manualfeed true put}B /@copies{/#copies X}B /FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{ /nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N string /base X array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{ /sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0] N df-tail}B /E{pop nn dup definefont setfont}B /ch-width{ch-data dup length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{ 128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N /rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 sub]/id ch-image N /rw ch-width 7 add 8 idiv string N /rc 0 N /gp 0 N /cp 0 N{rc 0 ne{rc 1 sub /rc X rw}{G}ifelse}imagemask restore}B /G{{id gp get /gp gp 1 add N dup 18 mod S 18 idiv pl S get exec}loop}B /adv{cp add /cp X}B /chg{rw cp id gp 4 index getinterval putinterval dup gp add /gp X adv}B /nd{/cp 0 N rw exit}B /lsh{rw cp 2 copy get dup 0 eq{pop 1}{ dup 255 eq{pop 254}{dup dup add 255 and S 1 and or}ifelse}ifelse put 1 adv}B /rsh{rw cp 2 copy get dup 0 eq{pop 128}{dup 255 eq{pop 127}{dup 2 idiv S 128 and or}ifelse}ifelse put 1 adv}B /clr{rw cp 2 index string putinterval adv}B /set{rw cp fillstr 0 4 index getinterval putinterval adv}B /fillstr 18 string 0 1 17{2 copy 255 put pop}for N /pl[{adv 1 chg} {adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{ adv rsh nd}{1 add adv}{/rc X nd}{1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]dup{bind pop}forall N /D{/cc X dup type /stringtype ne{] }if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{ cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin 0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore userdict /eop-hook known{eop-hook}if showpage}N /@start{userdict /start-hook known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X /IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for 65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0 0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V {}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7 getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false} ifelse}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale rulex ruley false RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR rulex ruley scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave newpath transform round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail {dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail}B /c{-4 M} B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{3 M}B /k{ 4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{ p 1 w}B /r{p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{3 2 roll p a}B /bos{/SS save N}B /eos{SS restore}B end %%EndProcSet %%BeginFont: Times-Bold % @psencodingfile{ % author = "P. MacKay, Alan Jeffrey, S. Rahtz, K. Berry, B. Horn", % version = "0.2", % date = "7 September 94", % filename = "8r.enc", % email = "kb@cs.umb.edu", % address = "135 Center Hill Rd. // Plymouth, MA 02360", % codetable = "ISO/ASCII", % checksum = "xx", % docstring = "Encoding for TrueType or Type 1 fonts to be used with TeX." % } % % Idea is to have all the characters normally included in Type 1 fonts % available for typesetting. This is effectively the characters in Adobe % Standard Encoding + ISO Latin 1 + extra characters from Lucida. % % Character code assignments were made as follows: % % (1) the Windows ANSI characters are in their Windows ANSI positions, % because Windows users cannot easily reencode the fonts, and it makes % no difference on other systems. The only Windows ANSI characters not % available are those that make no sense for typesetting -- rubout % (127 decimal), nobreakspace (160), softhyphen (173). % % (2) The caron and dotlessi characters are in the positions used by % Y&Y for their modified ATM encoding. % % (3) Remaining characters are assigned arbitrarily to the first few % positions. % % (4) (Y&Y) Lucida Bright includes some extra text characters; in the % hopes that other PostScript fonts, perhaps created for public % consumption, will include them, they are included starting at 0x10. % % (5) Remaining positions left undefined are for use in (hopefully) % upward-compatible revisions, if someday more characters are generally % available in the Type 1 fonts. % % Ligatures are omitted, since this encoding is intended for use at the % driver end. Including ligatures and kerns would make the TFM files % much larger, to no particular purpose. If someone actually wants to % typeset in this encoding, they can pick a different name, and regenerate % the fonts. /TeXBase1Encoding [ % 0x00 (encoded characters from Adobe Standard not in Windows 3.1) /breve /dotaccent /fi /fl /fraction /hungarumlaut /Lslash /lslash /ogonek /ring /tilde /minus % These are the only two remaining unencoded characters, so may as % well include them. /Zcaron /zcaron /.notdef /.notdef % 0x10 (TeX characters from, e.g., Lucida Bright) /dotlessj /ff /ffi /ffl /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef % 0x20 (ASCII begins) /space /exclam /quotedbl /numbersign /dollar /percent /ampersand /quotesingle /parenleft /parenright /asterisk /plus /comma /hyphen /period /slash % 0x30 /zero /one /two /three /four /five /six /seven /eight /nine /colon /semicolon /less /equal /greater /question % 0x40 /at /A /B /C /D /E /F /G /H /I /J /K /L /M /N /O % 0x50 /P /Q /R /S /T /U /V /W /X /Y /Z /bracketleft /backslash /bracketright /asciicircum /underscore % 0x60 /grave /a /b /c /d /e /f /g /h /i /j /k /l /m /n /o % 0x70 /p /q /r /s /t /u /v /w /x /y /z /braceleft /bar /braceright /asciitilde /.notdef % rubout; ASCII ends % 0x80 /.notdef /.notdef /quotesinglbase /florin /quotedblbase /ellipsis /dagger /daggerdbl /circumflex /perthousand /Scaron /guilsinglleft /OE /caron % Y&Y /.notdef /.notdef % 0x90 /.notdef /quoteleft /quoteright /quotedblleft /quotedblright /bullet /endash /emdash /tildeaccent /trademark /scaron /guilsinglright /oe /dotlessi % Y&Y /.notdef /Ydieresis % 0xA0 /.notdef % nobreakspace /exclamdown /cent /sterling /currency /yen /brokenbar /section /dieresis /copyright /ordfeminine /guillemotleft /logicalnot /hyphen % Y&Y (also at 45); Windows' softhyphen /registered /macron % 0xD0 /degree /plusminus /twosuperior /threesuperior /acute /mu /paragraph /periodcentered /cedilla /onesuperior /ordmasculine /guillemotright /onequarter /onehalf /threequarters /questiondown % 0xC0 /Agrave /Aacute /Acircumflex /Atilde /Adieresis /Aring /AE /Ccedilla /Egrave /Eacute /Ecircumflex /Edieresis /Igrave /Iacute /Icircumflex /Idieresis % 0xD0 /Eth /Ntilde /Ograve /Oacute /Ocircumflex /Otilde /Odieresis /multiply /Oslash /Ugrave /Uacute /Ucircumflex /Udieresis /Yacute /Thorn /germandbls % 0xE0 /agrave /aacute /acircumflex /atilde /adieresis /aring /ae /ccedilla /egrave /eacute /ecircumflex /edieresis /igrave /iacute /icircumflex /idieresis % 0xF0 /eth /ntilde /ograve /oacute /ocircumflex /otilde /odieresis /divide /oslash /ugrave /uacute /ucircumflex /udieresis /yacute /thorn /ydieresis ] def %%EndFont %%BeginProcSet: texps.pro TeXDict begin /rf{findfont dup length 1 add dict begin{1 index /FID ne 2 index /UniqueID ne and{def}{pop pop}ifelse}forall[1 index 0 6 -1 roll exec 0 exch 5 -1 roll VResolution Resolution div mul neg 0 0]/Metrics exch def dict begin Encoding{exch dup type /integertype ne{pop pop 1 sub dup 0 le{pop}{[}ifelse}{FontMatrix 0 get div Metrics 0 get div def} ifelse}forall Metrics /Metrics currentdict end def[2 index currentdict end definefont 3 -1 roll makefont /setfont load]cvx def}def /ObliqueSlant{dup sin S cos div neg}B /SlantFont{4 index mul add}def /ExtendFont{3 -1 roll mul exch}def /ReEncodeFont{/Encoding exch def}def end %%EndProcSet %%BeginProcSet: special.pro TeXDict begin /SDict 200 dict N SDict begin /@SpecialDefaults{/hs 612 N /vs 792 N /ho 0 N /vo 0 N /hsc 1 N /vsc 1 N /ang 0 N /CLIP 0 N /rwiSeen false N /rhiSeen false N /letter{}N /note{}N /a4{}N /legal{}N}B /@scaleunit 100 N /@hscale{@scaleunit div /hsc X}B /@vscale{@scaleunit div /vsc X}B /@hsize{/hs X /CLIP 1 N}B /@vsize{/vs X /CLIP 1 N}B /@clip{ /CLIP 2 N}B /@hoffset{/ho X}B /@voffset{/vo X}B /@angle{/ang X}B /@rwi{ 10 div /rwi X /rwiSeen true N}B /@rhi{10 div /rhi X /rhiSeen true N}B /@llx{/llx X}B /@lly{/lly X}B /@urx{/urx X}B /@ury{/ury X}B /magscale true def end /@MacSetUp{userdict /md known{userdict /md get type /dicttype eq{userdict begin md length 10 add md maxlength ge{/md md dup length 20 add dict copy def}if end md begin /letter{}N /note{}N /legal{} N /od{txpose 1 0 mtx defaultmatrix dtransform S atan/pa X newpath clippath mark{transform{itransform moveto}}{transform{itransform lineto} }{6 -2 roll transform 6 -2 roll transform 6 -2 roll transform{ itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll curveto}}{{ closepath}}pathforall newpath counttomark array astore /gc xdf pop ct 39 0 put 10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack}if}N /txpose{pxs pys scale ppr aload pop por{noflips{pop S neg S TR pop 1 -1 scale}if xflip yflip and{pop S neg S TR 180 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{pop S neg S TR pop 180 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{ppr 1 get neg ppr 0 get neg TR}if}{noflips{TR pop pop 270 rotate 1 -1 scale}if xflip yflip and{TR pop pop 90 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{TR pop pop 90 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{TR pop pop 270 rotate ppr 2 get ppr 0 get neg sub neg 0 S TR}if}ifelse scaleby96{ppr aload pop 4 -1 roll add 2 div 3 1 roll add 2 div 2 copy TR .96 dup scale neg S neg S TR}if}N /cp {pop pop showpage pm restore}N end}if}if}N /normalscale{Resolution 72 div VResolution 72 div neg scale magscale{DVImag dup scale}if 0 setgray} N /psfts{S 65781.76 div N}N /startTexFig{/psf$SavedState save N userdict maxlength dict begin /magscale true def normalscale currentpoint TR /psf$ury psfts /psf$urx psfts /psf$lly psfts /psf$llx psfts /psf$y psfts /psf$x psfts currentpoint /psf$cy X /psf$cx X /psf$sx psf$x psf$urx psf$llx sub div N /psf$sy psf$y psf$ury psf$lly sub div N psf$sx psf$sy scale psf$cx psf$sx div psf$llx sub psf$cy psf$sy div psf$ury sub TR /showpage{}N /erasepage{}N /copypage{}N /p 3 def @MacSetUp}N /doclip{ psf$llx psf$lly psf$urx psf$ury currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll S lineto S lineto S lineto closepath clip newpath moveto}N /endTexFig{end psf$SavedState restore}N /@beginspecial{SDict begin /SpecialSave save N gsave normalscale currentpoint TR @SpecialDefaults count /ocount X /dcount countdictstack N}N /@setspecial {CLIP 1 eq{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlineto closepath clip}if ho vo TR hsc vsc scale ang rotate rwiSeen{rwi urx llx sub div rhiSeen{rhi ury lly sub div}{dup}ifelse scale llx neg lly neg TR }{rhiSeen{rhi ury lly sub div dup scale llx neg lly neg TR}if}ifelse CLIP 2 eq{newpath llx lly moveto urx lly lineto urx ury lineto llx ury lineto closepath clip}if /showpage{}N /erasepage{}N /copypage{}N newpath }N /@endspecial{count ocount sub{pop}repeat countdictstack dcount sub{ end}repeat grestore SpecialSave restore end}N /@defspecial{SDict begin} N /@fedspecial{end}B /li{lineto}B /rl{rlineto}B /rc{rcurveto}B /np{ /SaveX currentpoint /SaveY X N 1 setlinecap newpath}N /st{stroke SaveX SaveY moveto}N /fil{fill SaveX SaveY moveto}N /ellipse{/endangle X /startangle X /yrad X /xrad X /savematrix matrix currentmatrix N TR xrad yrad scale 0 0 1 startangle endangle arc savematrix setmatrix}N end %%EndProcSet TeXDict begin @defspecial /magscale 1 def @fedspecial end TeXDict begin 39158280 55380996 1000 300 300 (paper.dvi) @start /Fa 2 84 df73 D83 D E /Fb 1 44 df<13C0A9B51280A23800C000A911147E8F17>43 D E /Fc 170[19 16 1[18 2[19 1[24 16 2[9 19 19 1[16 1[18 1[19 65[{TeXBase1Encoding ReEncodeFont}12 26.666641 /Times-Roman rf /Fd 18 104 df2 D13 D<143014F0EB01C0EB0700131E1378EA01E0EA0380000EC7FC123C 12F0A21238120E6C7EEA01E0EA0078131C1307EB03C0EB00F014301400A6387FFFE0B512 F0141E7D951B>20 D<3801FFF01207000EC7FC12185A5AA35AA61260A37E7E120E3807FF F0120114167D921B>26 D44 D<3801FF801207000EC7FC12185A5AA35AA2B51280A200C0C7FCA212 60A37E7E120E3807FF80120111167D9218>50 D<1303A21306A2130CA21318A21330A213 60A213C0A2EA0180A2EA0300A21206A25AA25AA25AA25AA25A1240101E7B9600>54 D57 DI67 D<01041408010E1418011E1438167016F0011F130115030117147001271306EC800C ED1C6001431338ED70E0ECC0E0903883C1C0903881E3800001EBE700EB00EE4813FC0002 5B00C6137000FC012013F891C712F00038150025187F962A>77 D<3801FFE0000F13F838 18E0FC0020133E0060131E00C0130E1200140C13C01418000113101420EB8040EB818038 03BE00137890C7FC5A1206A2120E120CA25A17187F9619>80 D<3801FFF8000F13FE3818 E03F0020130F00607F12C000001306A2495A140800015B1460EB8780018FC7FC00037FEB 07C01303486C7E1206903800F02048EBF8C0EC7F0048133C1B177F961E>82 DI< 134013E0A2EA01B0A2EA0318A2EA060CA2487EA2487EA238300180A2386000C0A2481360 142013137E9218>94 D<00C013201460006013C0A238300180A238180300A2EA0C06A26C 5AA26C5AA2EA01B0A2EA00E0A2134013137E9218>I<137813C0EA0180EA0300AB12065A 12F0120C7E7EABEA0180EA00C013780D217E9812>102 D<12F0120C7E7EABEA0180EA00 C0137813C0EA0180EA0300AB12065A12F00D217E9812>I E /Fe 15 116 df<126012F0A2126004047D830A>58 D<126012F0A212701210A21220A21240A2 040A7D830A>I<130813181330A31360A313C0A3EA0180A3EA0300A21206A35AA35AA35A A35AA35AA20D217E9812>61 D<12C012F0123C120EEA0380EA01E0EA0078131E1307EB01 C0EB00F0A2EB01C0EB0700131E1378EA01E0EA0380000EC7FC123C12F012C014167D921B >I67 D<38FFC0FF381C00181410A3481320A4481340A4481380A4EB010013025BEA6008EA3830 EA0FC018177E9618>85 D97 D<133E130CA41318A4EA0730EA18F0EA30701260136012C0 A3EA80C013C4A212C1EA46C8EA38700F177E9612>100 DI<121F1206A45AA4EA18F0 EA1B18EA1C081218EA38181230A3EA6030133113611362EAC026133810177E9614>104 D<120313801300C7FCA6121C12241246A25A120C5AA31231A21232A2121C09177F960C> I<1318133813101300A6EA01C0EA0220EA0430A2EA08601200A313C0A4EA0180A4EA6300 12E312C612780D1D80960E>I110 D114 DI E /Ff 3 62 df<120112021204120C12 18A21230A212701260A312E0AA1260A312701230A21218A2120C12041202120108227D98 0E>40 D<12801240122012301218A2120CA2120E1206A31207AA1206A3120E120CA21218 A2123012201240128008227E980E>I61 D E /Fg 147[9 6[15 2[18 17 12[22 28[17 17 17 17 17 17 17 2[8 46[{TeXBase1Encoding ReEncodeFont}13 33.333332 /Times-Bold rf /Fh 3 62 df<1380EA010012025A120C120812185AA35AA412E0AA12 60A47EA37E1208120C12047E7EEA008009267D9B0F>40 D<7E12407E7E12181208120C7E A37EA41380AA1300A41206A35A1208121812105A5A5A09267E9B0F>I61 D E /Fi 17 123 df<124012E0124003037D8209>58 D<124012E012601220A21240A2128003087D8209>I67 D<12781218A25AA31237EA78C0EA60401360A2EAC0C0A3EA4180EA6300123C0B117E900E >98 DI<13E0 EA01B013A0EA0300A3EA1FE0EA03001206A65AA41208125812D012600C167D900F>102 D<1204120C1200A5123012581298A21230A212601264A21268123006127E910B>105 D<1320A21300A5EA0380EA04C01208A21200EA0180A4EA0300A4124612CC12780B178091 0D>I<3871F1F0389A1A18EA9C1CEA9818121838303030A214321462386060641438170B 7E8A1B>109 DI112 D114 D<120FEA10801221EA2000123E7EEA01801280EAC0001283127C090B7D8A0F>I<120812 18A312FF1230A41260A212621264A21238080F7E8E0C>I120 DII E /Fj 5 83 df0 D<120CA2EACCC012EDEA7F80EA0C00EA7F80 EAEDC012CCEA0C00A20A0B7D8B10>3 D<13FCEA030C120CEA1008EA3018EA2010EA6000 124012C0A5EAE008EA7010EA3860EA1F800E117E9011>67 D<3801FFFC3802100C380430 001208120013201360A2EB7FC0EBC0005B120190C7FC5A120212C412F816117E9016>70 D<380FFFC0383180F00041133012C11201EB00204813401480EB0300133CEA021CEA060E 1306EA0407380C0382380801CC381800F017117F901A>82 D E /Fk 21 123 df<126012F0A2126004047D830B>58 D<126012F0A212701210A31220A21240A2 040B7D830B>I<1406141E1478EB01E0EB0780EB1E00133813E0EA03C0000FC7FC123C12 F0A2123C120FEA03C0C67E1338131EEB0780EB01E0EB0078141E140617187D941E>I<12 C012F0123C120FEA03C0EA00F01338130EEB0780EB01E0EB0078141EA21478EB01E0EB07 80EB0E00133813F0EA03C0000FC7FC123C12F012C017187D941E>62 D<903807E04090383C18C0EBE0053801C0033903800180EA0700120E5A003C1400123800 7890C7FCA25AA41404A35C00705B1230003813606C1380D80703C7FCEA01FC1A1A7E991B >67 D73 D<3903F001FE39007800701520135C019C1340138EA3D801071380A2EB0380A239 0201C100A3EB00E14813E21472A2143A48133CA2141C121800381308B4FC1F1A7E991F> 78 D<397FE03FC0390E000E001404A2485BA4485BA4485BA4485BA35CA249C7FCEA6002 6C5AEA1818EA07E01A1A7E991A>85 D97 D99 D101 D103 D<120313801300C7FCA7123C124EA2128EA2129C121CA25AA212391271A21272A2123C09 1A7E990D>105 D<1302130713061300A71370EA0198EA021CA21204A2EA0038A41370A4 13E0A4EA01C01261EAE380EAC700127C1021809910>I110 D<38070780380598403809E060EBC07014301470EA0380A31460380700E014C01301EB03 80380E8600137C90C7FCA25AA4B4FC1417828F13>112 D114 DI<38078780 3808C8C0EA10F1EA20E01400A2EA01C0A4EA0381A212C3EAE582EAC584EA787812107F8F 16>120 DII E /Fl 18 104 df<6C13C0EAC00138600300EA30066C5A6C5A6C5A6C5A6C5A A2EA0360EA0630487E487E487E487E38C001C0EA800012127A911E>2 D15 D26 D50 D<1460A214C0A2EB0180A2EB0300A213065BA25BA25BA25BA25BA2485AA248C7FCA21206 A25A5AA25AA25AA25A124013227B9900>54 D67 D<90380FFFFC133F903843C038D8018313200003EB8000EA07 03EA0607120091C7FCA25B130E90380FFF8090381FFE00011CC7FC133C1338A25BA25BA2 EA31C0EA7980B4C8FC127C1E1A7F991C>70 D73 D76 D<01061401010E14021606010F140E161E49143E011714 3C167C6E13FCED01BC01231303ED073CECC00E0143EB1C3801411338ED7078903881E060 15C0903880F180390100F700147F0002137E0066137C00FC0130137C91C7127F48153C00 701500281B7E992E>I80 D82 DI<150848B512F0000714C039180380004848C7FC1270EAF00F12E0EA00 0EA2131EA2131CA2133CA31338A21378A21370A213F05BA212015B5B0002C8FC1D1E7E9A 15>I<13201370A213D8A2EA018CA2EA0306A2EA0603A3380C0180A2381800C0A2481360 A2481330A2481318140815167E951A>94 D<00C01308141800601330A26C1360A26C13C0 A2380C0180A238060300A3EA0306A2EA018CA2EA00D8A21370A2132015167E951A>I<13 3C13E0EA01C0EA0380ADEA0700121E12F8121E1207EA0380ADEA01C0EA00E0133C0E257E 9B13>102 D<12F8121E1207EA0380ADEA01C0EA00E0133C13E0EA01C0EA0380ADEA0700 121E12F80E257E9B13>I E /Fm 203[12 12 12 12 12 48[{ TeXBase1Encoding ReEncodeFont}5 25.000000 /Times-Roman rf /Fn 166[22 1[28 1[22 18 17 20 1[17 22 22 27 18 22 1[10 22 22 1[18 22 20 20 22 65[{TeXBase1Encoding ReEncodeFont}20 29.999987 /Times-Roman rf /Fo 82[11 24[18 18 24[13 15 15 22 15 17 9 13 13 1[17 17 17 24 9 15 9 9 17 17 9 15 17 15 17 17 3[13 1[13 3[28 2[18 17 20 1[20 24 22 28 18 1[15 11 24 24 20 20 24 22 1[20 7[17 17 1[17 17 17 17 17 17 2[8 1[8 5[26 35[17 2[{TeXBase1Encoding ReEncodeFont}60 33.333332 /Times-Italic rf /Fp 82[12 4[12 19[21 21 24[15 17 17 25 17 19 10 15 15 1[19 19 19 27 10 17 10 10 19 19 10 17 19 17 19 19 9[31 2[21 19 23 1[23 1[25 31 21 2[12 27 27 23 23 1[25 23 23 3[25 6[19 2[19 1[19 19 10 9 1[9 2[12 12 12 36[19 2[{TeXBase1Encoding ReEncodeFont}57 37.500000 /Times-Italic rf /Fq 82[12 22[19 1[17 17 24[17 19 19 27 19 19 10 15 12 19 19 19 19 29 10 19 10 10 19 19 12 17 19 17 19 17 3[12 1[12 3[35 1[27 23 21 25 1[21 27 27 33 23 27 1[12 27 27 21 23 27 25 25 27 3[21 1[10 10 19 19 19 19 19 19 19 19 19 19 10 9 1[9 2[12 12 12 1[31 33[21 21 2[{TeXBase1Encoding ReEncodeFont}74 37.500000 /Times-Roman rf /Fr 134[19 1[27 1[21 12 15 17 1[21 19 21 31 10 21 1[10 21 19 1[17 21 17 21 19 11[27 1[21 2[23 1[27 35 25 29 1[15 29 4[27 1[27 9[19 19 19 19 19 4[9 1[9 44[{TeXBase1Encoding ReEncodeFont}38 37.500000 /Times-Bold rf /Fs 82[11 4[11 17[17 1[15 15 24[15 17 17 24 17 17 9 13 11 17 17 17 17 26 9 17 9 9 17 17 11 15 17 15 17 15 11 2[11 1[11 3[31 1[24 20 18 22 1[18 24 24 30 20 24 13 11 24 24 18 20 24 22 22 24 3[19 2[9 17 17 17 17 17 17 17 17 17 17 9 8 1[8 2[11 11 11 26 21[11 12[18 18 2[{ TeXBase1Encoding ReEncodeFont}77 33.333332 /Times-Roman rf /Ft 135[23 33 1[25 15 18 20 1[25 23 25 38 13 25 15 13 25 23 15 20 25 20 25 23 11[33 30 25 33 1[28 1[33 43 30 36 1[18 36 36 28 30 1[33 1[33 9[23 23 23 23 23 23 23 4[11 44[{TeXBase1Encoding ReEncodeFont}46 45.833332 /Times-Bold rf /Fu 135[42 2[46 28 32 37 1[46 42 46 1[23 2[23 46 42 1[37 1[37 1[42 12[55 1[60 12[55 1[60 1[60 65[{TeXBase1Encoding ReEncodeFont}20 83.333336 /Times-Bold rf end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%PaperSize: a4 %%EndSetup %%Page: 576 1 576 0 bop -83 25 a Fq(Unlike)12 b(DR)n(T)m(,)h(the)g(centering)e(model) i([6])g(to)g(which)f(we)h(adhere)e(is)i(not)-125 71 y(considered)6 b(a)h(semantic)g(theory)g(b)o(ut)h(rather)g(a)f(discourse)f(processing) f(model)-125 116 y(which)14 b(lends)f(itself)i(to)f(an)g(easy)e(inte)o (gration)j(into)f(a)g(te)o(xt)h(understanding)-125 162 y(frame)o(work.)h(Still,)i(it)f(does)d(not)i(pro)o(vide)g(for)g (well\255de)o(v)o(eloped)f(methods)-125 208 y(for)f(te)o(xtual)g (ellipsis)f(resolution.)g(Grosz)f(et)h(al.)h(rather)f(sketchily)f (point)h(to)-125 253 y(the)j(dif)o(ference)g(between)f(the)h(relations) g Fp(dir)o(ectly)f(r)o(ealizes)f Fq(and)h Fp(r)o(ealizes)-125 299 y Fq(whose)6 b(precise)h(de\002nition)f(the)o(y)i(suggest)d (depends)g(on)i(the)g(semantic)f(theory)-125 345 y(one)k(adopts)g([6,)i (p.209].)f(W)m(e)g(ha)o(v)o(e)f(sho)o(wn,)g(ho)o(we)o(v)o(er)o(,)g (that)h(there)g(are)g(a)f(lot)-125 390 y(of)16 b(constraints)d(at)i (the)g(conceptual)e(le)o(v)o(el)i(which)f(cannot)g(reasonably)e(be)-125 436 y(accounted)7 b(for)j(by)f(semantic)f(theories.)-83 482 y(Only)13 b(fe)o(w)h(NLP)f(systems)f(e)o(xist)h(which)g(deal)g (with)h(te)o(xtual)f(ellipsis)h(in)-125 527 y(a)d(dedicated)f(way)n(.)g (F)o(or)h(e)o(xample,)g(the)g(PUNDIT)g(system)f([17])i(pro)o(vides)e(a) -125 573 y(fairly)h(restricted)e(solution)g(in)h(that)f(only)g(direct)h (conceptual)d(links)i(between)-125 619 y(the)d(concept)f(denoted)g(by)g (the)h(antecedent)t(and)f(the)h(elliptical)h(e)o(xpression)e(are)-125 664 y(considered)10 b(\(\223plausible\224)g(paths)h(of)h(length)f Fp(1)p Fq(,)h(in)g(our)f(terminology\).)i(The)-125 710 y(approach)c(reported)g(in)i(this)f(paper)f(also)h(e)o(xtends)f(our)h (o)o(wn)f(pre)o(vious)g(work)-125 756 y(on)k(te)o(xtual)f(ellipses)g ([7])i(by)e(the)g(incorporation)g(of)h(an)f(elaborated)f(model)-125 801 y(of)e(functional)g(preferences)e(on)h Fk(C)330 805 y Fi(f)359 801 y Fq(elements)f(which)i(constrains)e(the)h(set)h(of)-125 847 y(possible)f(antecedents)f(according)h(to)h(information)h (structure)f(criteria.)-125 928 y Ft(7)46 b(Conclusions)-125 979 y Fq(In)10 b(this)f(paper)o(,)g(we)f(ha)o(v)o(e)h(outlined)g(a)g (model)g(of)g(te)o(xtual)h(ellipsis)f(resolution.)-125 1025 y(It)h(considers)e(conceptual)f(criteria)j(to)f(be)f(of)i(primary) f(importance)f(and)g(pro\255)-125 1071 y(vides)e(conceptual)f (well\255formedness)h(and)f(strength)h(criteria)i(for)f(role)g(chains) -125 1116 y(in)12 b(a)f(terminological)g(kno)o(wledge)e(base)h(in)h (order)h(to)f(assess)e(the)h(plausibil\255)-125 1162 y(ity)h(of)g(v)o(arious)e(possible)g(antecedents)e(as)j(proper)f (bridges)h([3])h(to)f(elliptical)-125 1208 y(e)o(xpressions.)j (Functional)g(constraints)g(based)g(on)g(the)h(utterances')f(infor)o (\255)-125 1253 y(mation)i(structure)f(contrib)o(ute)h(further)g (restrictions)g(on)f(proper)g(elliptical)-125 1299 y(antecedents)7 b(and)h(require)i(a)e(basic)h(re)o(vision)f(of)i(the)f(centering)f (model.)-83 1345 y(The)14 b(two)g(principled)g(dif)o(\002culties)h (inherent)f(in)h(e)o(v)o(ery)f(network\255based)-125 1390 y(symbolic)c(kno)o(wledge)f(representation)h(approach)f(are)h(its) h(dependenc)o(y)d(on)-125 1436 y(hand\255crafted)e(and)g(often)h (domain\255speci\002c)e(kno)o(wledge)g(and)h(the)h(e)o(xorbitant)-125 1482 y(costs)12 b(for)h(unconstrained)d(search)i(\(often)g(limiting)j (the)d(scalability)g(of)h(the)-125 1527 y(approach\).)e(W)m(e)i(cope)d (with)j(the)f(\002rst)g(of)h(these)e(problems)g(by)h(postulating)-125 1573 y(two)c(formal)g(criteria,)h Fp(viz.)f Fq(the)g(non\255c)o (yclicity)f(and)g(the)g(inclusion)g(condition,)-125 1619 y(which)h(only)h(depend)d(on)i(features)g(present)g(in)g(almost)h(an)o (y)f(kno)o(wledge)e(rep\255)-125 1664 y(resentation)k(language,)f (i.e.,)i Fp(isa)f Fq(links,)h(domains)e(and)g(ranges)g(of)i(relations) -125 1710 y(and)e(in)o(v)o(erse)g(relations.)g(No)h(reference)e(to)i(a) g Fp(speci\002c)d Fq(network)i(structure)h(or)-125 1756 y(a)e Fp(speci\002c)f Fq(domain)g(is)i(made.)e(The)h(de\002nition)g(of) g(patterns)g(relies)g(mainly)g(on)-125 1801 y(structural)f(properties)f (of)h(semantic)e(relations,)i(which)f(are)g(entirely)h(domain\255)-125 1847 y(independent.)h(Ho)o(we)o(v)o(er)o(,)h(this)h(heuristic)f (criterion)h(is)g(only)f(ef)o(fecti)o(v)o(e)h(when)-125 1893 y(the)j(underlying)e(kno)o(wledge)f(base)h(is)h(b)o(uilt)i(on)d (top)i(of)f(a)g(clear)g(taxonomy)-125 1938 y(of)d(relations)g (\(although)f(this)h(taxonomy)e(and)g(the)i(corresponding)d(path)j (pat\255)-125 1984 y(terns)j(can)e(be)h(speci\002ed)f(in)h(ways)g(dif)o (fering)h(from)g(ours\).)g(The)f(e)o(xpensi)o(v)o(e\255)-125 2030 y(ness)f(of)i(the)f(search)f(has)g(already)g(been)g(reduced)g (signi\002cantly)g(by)h(testing)-125 2075 y(the)k(non\255c)o(yclicity)f (of)h(the)f(paths)f(during)h(the)h(search.)e(W)m(e)i(are)f(currently) -125 2121 y(e)o(xperimenting)c(with)g(an)g(additional)f(search)g (constraint,)g(which)h(limits)h(the)-125 2166 y(search)c(to)i(certain)f Fp(dynamically)f(narr)n(owed)f(r)o(e)o(gions)f Fq(in)k(a)f(kno)o (wledge)e(base,)-125 2212 y(likely)15 b(to)g(make)e(the)i(algorithm)g (ef)o(\002ciently)g(e)o(x)o(ecutable)e(e)o(v)o(en)h(on)g(lar)o(ger)-125 2258 y(kno)o(wledge)8 b(bases.)-83 2303 y(The)h(ellipsis)g(handler)g (has)f(been)g(implemented)h(in)g(Smalltalk)h(as)f(part)h(of)-125 2349 y(a)i(comprehensi)o(v)o(e)e(te)o(xt)i(parser)f(for)i(German,)f (which)f(is)h(interfaced)f(to)h(the)-125 2395 y(LOOM)7 b(system)e([15].)j(Besides)d(the)h(information)h(technology)e(domain)g (\(this)-125 2440 y(kno)o(wledge)11 b(base)g(currently)i(contains)e (approximately)g(800)h(concept/role)-125 2486 y(speci\002cations\),)d (e)o(xperiments)g(with)i(our)f(parser)f(ha)o(v)o(e)h(also)f(been)g (success\255)-125 2532 y(fully)f(run)e(on)g(medical)h(domain)e(te)o (xts)i(\(the)g(corresponding)e(medical)h(domain)-125 2577 y(kno)o(wledge)11 b(base)g(currently)i(contains)e(approximately)g (500)h(concept/role)-125 2623 y(speci\002cations\).)6 b(These)f(results)h(indicate)h(that)g(the)f(heuristics)g(we)h(ha)o(v)o (e)f(been)-125 2669 y(de)o(v)o(eloping)i(are)h(not)g(bound)f(to)i(a)e (particular)i(domain.)971 25 y Fr(Acknowledgments.)i Fq(W)m(e)i(would)f(like)h(to)h(thank)e(our)h(colleagues)e(in)i(the)971 63 y Fl(C)r(LI)s(F)j Fq(group)12 b(for)i(fruitful)h(discussions.)c(M.)i (Strube')n(s)g(contrib)o(ution)g(has)971 101 y(been)7 b(funded)f(by)h Fp(LGFG)h(Baden\255W)1455 100 y(\250)1452 101 y(urttember)o(g)p Fq(,)d(while)j(K.)g(Markert)f(is)h(sup\255)971 138 y(ported)g(by)g(a)h(grant)f(from)h(DFG)g(within)g(the)f(Freib)o(ur) o(g)h(Uni)o(v)o(ersity)g(Graduate)971 176 y(Program)g(on)g Fp(\223Human)f(and)h(Arti\002cial)g(Intelligence\224)p Fq(.)f(W)m(e)i(also)e(gratefully)971 213 y(ackno)o(wledge)f(the)i(pro)o (vision)g(of)g(the)g(LOOM)h(system)e(from)i(USC/ISI.)971 327 y Ft(REFERENCES)984 392 y Fs([1])29 b(Roger)8 b(Chaf)o(\002n,)h (`The)g(concept)e(of)i(a)g(semantic)f(relation',)h(in)g Fo(F)n(rames,)f(F)o(ields)1052 433 y(and)d(Contrasts)p Fs(,)h(eds.,)g(A.)h(Lehrer)g(and)e(E.F)m(.)k(Kittay)n(,)e(253\226288,)t (Hillsdale,)g(N.J.:)1052 475 y(Lawrence)f(Erlbaum,)i(\(1992\).)984 516 y([2])29 b(Eugene)7 b(Charniak,)g(`)m(A)i(neat)f(theory)f(of)h (marker)f(passing',)g(in)i Fo(Pr)o(oc.)e(of)i(AAAI\255)1052 558 y(86)p Fs(,)e(v)o(olume)h(1,)g(pp.)g(584\226588,)e(\(1986\).)984 599 y([3])29 b(Herbert)7 b(H.)g(Clark,)h(`Bridging',)f(in)h Fo(Pr)o(oc.)f(of)g(the)g(Confer)o(ence)f(on)h(Theor)o(etical)1052 641 y(Issues)g(in)h(Natural)f(Language)e(Pr)o(ocessing,)i(Cambridge,)f (MA)p Fs(,)i(pp.)g(169\226174,)1052 682 y(\(1975\).)984 724 y([4])29 b(Franti)q(\020)-12 b(sek)7 b(Dane)q(\020)-12 b(s)o(,)8 b(`Functional)f(sentence)f(perspecti)o(ve)g(and)h(the)g(or)o (ganization)1052 765 y(of)e(the)h(text',)g(in)g Fo(P)m(apers)f(on)g (Functional)g(Sentence)t(P)m(erspective)p Fs(,)g(ed.,)h(F)m(.)h(Dane)q (\020)-12 b(s)o(,)1052 807 y(106\226128,)5 b(Prague:)j(Academia,)f (\(1974\).)984 848 y([5])29 b(Dan)16 b(C.)i(Fass,)f(`met)1317 837 y Fj(\003)1335 848 y Fs(:)h(A)f(method)f(for)h(discriminating)g (metonymy)e(and)1052 890 y(metaphor)i(by)h(computer',)f Fo(Computational)g(Linguistics)p Fs(,)i Fg(17)p Fs(\(1\),)f(49\22690,) 1052 931 y(\(1991\).)984 973 y([6])29 b(Barbara)7 b(J.)h(Grosz,)f(Ara)o (vind)g(K.)h(Joshi,)f(and)g(Scott)h(W)m(einstein,)g(`Centering:)g(A) 1052 1014 y(frame)o(work)h(for)i(modeling)e(the)h(local)h(coherence)d (of)j(discourse',)f Fo(Computa\255)1052 1056 y(tional)d(Linguistics)p Fs(,)i Fg(21)p Fs(\(2\),)e(203\226225,)f(\(1995\).)984 1097 y([7])29 b(Udo)8 b(Hahn,)h(`Making)e(understanders)g(out)i(of)g (parsers:)f(Semantically)h(dri)o(ven)1052 1139 y(parsing)f(as)i(a)f (key)g(concept)f(for)h(realistic)h(text)g(understanding)d (applications',)1052 1180 y Fo(International)f(J)o(ournal)h(of)h (Intelligent)g(Systems)p Fs(,)f Fg(4)p Fs(\(3\),)h(345\226393,)e (\(1989\).)984 1222 y([8])29 b(Udo)7 b(Hahn,)h(Susanne)f(Schacht,)h (and)g(Norbert)g(Br)s(\250)-14 b(oker)o(,)7 b(`Concurrent,)g (object\255)1052 1263 y(oriented)15 b(dependency)e(parsing:)j(The)h Fo(P)m(arseT)m(alk)f Fs(model.)n(',)g Fo(International)1052 1305 y(J)o(ournal)6 b(of)j(Human\255Computer)c(Studies)p Fs(,)j Fg(41)p Fs(\(1/2\),)f(179\226222,)f(\(1994\).)984 1346 y([9])29 b(Udo)11 b(Hahn,)h(Michael)f(Strube,)h(and)f(Katja)i (Markert,)e(`Bridging)g(textual)g(el\255)1052 1388 y(lipses',)d(in)g Fo(Pr)o(oc.)g(of)g(COLING\25596)p Fs(,)g(\(1996\).)967 1429 y([10])29 b(Graeme)5 b(Hirst,)i Fo(Semantic)e(Interpr)o(etation)g (and)g(the)h(Resolution)f(of)i(Ambiguity)p Fs(,)1052 1471 y(Cambridge,)g(UK:)h(Cambridge)f(Uni)o(versity)g(Press,)i(1987.) 967 1512 y([11])29 b(Jerry)9 b(R.)h(Hobbs,)e(Mark)h(E.)h(Stickel,)g (Douglas)e(E.)i(Appelt,)f(and)g(Paul)g(Martin,)1052 1554 y(`Interpretation)t(as)d(abduction',)t Fo(Arti\002cial)g(Intelligence)p Fs(,)f Fg(63)p Fs(,)h(69\226142,)t(\(1993\).)967 1595 y([12])29 b(Michael)6 b(N.)i(Huhns)f(and)f(Larry)i(M.)f(Stephens,)g (`Plausible)h(inferencing)e(using)1052 1637 y(extended)t(composition',) f(in)h Fo(Pr)o(oc.)g(of)h(IJCAI\25589)p Fs(,)f(v)o(olume)g(2,)h(pp.)f (1420\2261425)o(,)1052 1679 y(\(1989\).)967 1720 y([13])29 b(Hans)14 b(Kamp)h(and)f(Uwe)h(Reyle,)f Fo(F)n(r)o(om)h(Discourse)f(to) h(Logic)p Fs(,)g(Dordrecht:)1052 1762 y(Kluwer)o(,)7 b(1993.)967 1803 y([14])29 b(Geor)o(ge)8 b(Lakof)o(f,)g Fo(W)m(omen,)f(F)o(ir)o(e,)i(and)e(Danger)o(ous)f(Things.)i(What)g (Cate)o(gories)1052 1845 y(Reveal)f(about)g(the)h(Mind)p Fs(,)f(Chicago)g(Uni)o(versity)g(Press,)i(Chicago,)e(IL,)i(1987.)967 1886 y([15])29 b(Robert)8 b(MacGregor)e(and)h(Raymond)g(Bates.)13 b(The)8 b(LOOM)g(Kno)o(wledge)f(Rep\255)1052 1928 y(resentation)g (Language.)j(\(ISI/RS\25587\25518\))e(USC/ISI,)i(1987.)967 1969 y([16])29 b(Peter)7 b(Norvig,)g(`Marker)f(passing)g(as)h(a)h(weak) e(method)g(for)h(inferencing',)f Fo(Cog\255)1052 2011 y(nitive)i(Science)p Fs(,)f Fg(13)p Fs(\(4\),)g(569\226620,)f (\(1989\).)967 2052 y([17])29 b(Martha)6 b(S.)h(Palmer)o(,)g(Deborah)f (A.)h(Dahl,)g(Rebecca)f(J.)h(Schif)o(fman,)g(and)f(L)n(ynette)1052 2094 y(Hirschman,)h(`Recovering)f(implicit)i(information',)g(in)g Fo(Pr)o(oc.)g(of)g(A)o(CL\25586)p Fs(,)h(pp.)1052 2135 y(10\22619,)d(\(1986\).)967 2177 y([18])29 b(Phil)8 b(Resnik,)f(`Using) g(information)g(content)f(to)i(e)o(v)o(aluate)e(semantic)h(similarity) 1052 2218 y(in)h(a)g(taxonomy',)e(in)i Fo(Pr)o(oc.)g(of)g(IJCAI\25595)p Fs(,)g(v)o(olume)g(1,)g(pp.)g(448\226453,)e(\(1995\).)967 2260 y([19])29 b(Michael)5 b(Strube)g(and)g(Udo)g(Hahn)o(,)g(`)p Fo(P)m(arseT)m(alk)g Fs(abou)o(t)g(sentence)o(\255)g(and)g(te)o (xt\255le)o(ve)o(l)1052 2301 y(anaphora',)h(in)i Fo(Pr)o(oc.)g(of)g(EA) o(CL\25595)p Fs(,)h(pp.)f(237\226244,)e(\(1995\).)967 2343 y([20])29 b(Michael)5 b(Strube)i(and)f(Udo)g(Hahn,)g(`Functional)h (centering',)f(in)g Fo(Pr)o(oc.)h(of)g(A)o(CL\255)1052 2384 y(96)p Fs(,)g(\(1996\).)967 2426 y([21])29 b(Hajime)6 b(W)m(ada,)i(`)m(A)f(treatment)f(of)h(functional)f(de\002nite)g (descriptions',)g(in)h Fo(Pr)o(oc.)1052 2467 y(of)h(COLING\25594)p Fs(,)g(v)o(olume)g(2,)g(pp.)g(789\226795,)d(\(1994\).)967 2509 y([22])29 b(Morton)7 b(W)o(inston,)g(Roger)h(Chaf)o(\002n,)g(and)g (Douglas)f(Herrmann,)g(`)m(A)i(taxonomy)1052 2550 y(of)f (part\255whole\255relations',)f Fo(Cognitive)g(Science)p Fs(,)g Fg(11)p Fs(,)g(417\226444,)f(\(1987\).)967 2592 y([23])29 b(W)o(illiam)13 b(A.)g(W)m(oods)g(and)f(James)g(G.)h (Schmolze,)g(`The)f(KL\255ONE)i(family',)1052 2633 y Fo(Computers)5 b(&)g(Mathema)o(tics)g(with)g(Applications)p Fs(,)g Fg(23)o Fs(\(2\2555\),)g(13)o(3\2261)o(77)o(,)g(\(1992)o(\).) -125 2885 y Fr(Natural)k(Language)e(Pr)o(ocessing)553 b(576)448 b(U)n(.)10 b(Hahn,)f(K.)h(Markert)e(and)g(M.)i(Strube)p eop %%Page: 575 2 575 1 bop 106 14 a Fg(T)m(able)8 b(6.)33 b Fs(Potential)9 b(Elliptical)g(Antecedent)p -61 32 886 2 v -61 200 2 168 v 85 70 a(isPotentialEllipticAntecedent)e(\(y)n(,)h(x,)h(n\))f(:)p Fd(,)126 105 y Fs(y)g Fe(isa)198 111 y Fi(C)224 94 y Fj(\003)250 105 y Fs(Nominal)g Fd(^)g Fs(x)g Fe(isa)479 111 y Fi(C)504 94 y Fj(\003)531 105 y Fs(Noun)126 141 y Fd(^)g(9)g Fs(z:)g(\(x)g Fe(head)h Fs(z)f Fd(^)g Fs(z)g Fe(isa)461 147 y Fi(C)487 129 y Fj(\003)513 141 y Fs(DetDe\002nite\)) 126 177 y Fd(^)g Fs(x)g Fd(2)g Fe(U)239 181 y Fi(n)268 177 y Fd(^)g Fs(y)n(.r)g Fd(2)g Fe(C)399 183 y Fi(f)419 177 y Ff(\()p Fe(U)457 182 y Fi(n)p Fj(\000)p Fm(1)514 177 y Ff(\))p 823 200 V -61 202 886 2 v -125 255 a Fq(of)i(the)g (elliptic)g(e)o(xpression)e Fp(x)h Fq(if)o(f)i(it)g(is)f(a)f(potential) g(antecedent)f(and)g(if)j(there)-125 301 y(e)o(xists)f(no)g(alternati)o (v)o(e)g(antecedent)e Fp(z)h Fq(whose)g(conceptual)f(strength)h(relati) o(v)o(e)-125 347 y(to)h Fk(x)f Fq(e)o(xceeds)e(that)j(of)f Fk(y)i Fq(or)o(,)e(if)h(their)g(conceptual)d(strength)i(is)h(equal,)e (whose)-125 392 y(strength)j(of)h(preference)e(under)h(the)g Fp(IS)h Fq(relation)f(is)h(higher)f(than)g(that)g(of)h Fp(y)p Fq(.)-125 438 y(\223)p Fk(>)-87 448 y Fa(I)r(S)-49 438 y Fq(\224)c(de\002nes)e(\(cf.)j([20])g(for)g(an)e(in\255depth)h (treatment\))h(a)f(strict)h(order)f(on)g(the)-125 484 y(conceptual/semantic)e(items)g(of)g Fk(C)340 488 y Fi(f)364 484 y Fq(re\003ecting)g(the)g(functional)g(information)-125 529 y(structure)12 b(of)g(the)g(utterance)f Fk(U)294 533 y Fi(n)327 529 y Fq(in)h(which)f(their)i(linguistic)f (counterparts,)-125 575 y Fp(viz.)e Fk(z)g Fq(and)f Fk(y)q Fq(,)h(occur)n(.)-68 641 y Fg(T)m(able)f(7.)33 b Fs(Preferred)8 b(Conceptual)e(Bridge)i(for)g(an)g(Elliptical)h(Expression)p -125 659 1022 2 v -125 863 2 204 v -12 697 a(PreferredConceptualBridge) d(\(y)n(,)i(x,)g(n\))g(:)p Fd(,)-12 732 y Fs (isPotentialEllipticAntecedent)g(\(y)n(,)g(x,)g(n\))-12 768 y Fd(^)g(:9)g Fs(z)g(:)g(isPotentialEllipticAntecedent)g(\(z,)g(x,) g(n\))13 804 y Fd(^)g Fs(\(isStrongerThan)f(\(CP)320 808 y Fi(x:c;z)q(:c)412 804 y Fs(,)i(CP)469 808 y Fi(x:c;y)q(:c)562 804 y Fs(\))13 840 y Fd(_)f Fs(\(equallyStrongAs)f(\(CP)339 844 y Fi(x:c;z)q(:c)431 840 y Fs(,)17 b(CP)496 844 y Fi(x:c;y)q(:c)589 840 y Fs(\))8 b Fd(^)g Fs(z)g Fe(>)682 849 y Fa(I)r(S)728 840 y Fs(y)g(\))h(\))p 895 863 V -125 865 1022 2 v -125 974 a Ft(5)46 b(T)l(ext)12 b(Ellipsis)f(Resolution) -125 1025 y Fq(The)f(resolution)g(of)h(te)o(xtual)g(ellipses)e(depends) g(on)h(the)g(results)g(of)h(the)f(fore\255)-125 1071 y(going)k(resolution)h(of)f(nominal)h(anaphors)d([19])j(and)f(the)g (termination)i(of)-125 1117 y(the)d(semantic)f(interpretation)h(of)g (the)g(current)g(utterance.)f(It)i(will)g(only)e(be)-125 1162 y(triggered)f(at)f(the)g(occurrence)e(of)i(the)g(de\002nite)f (noun)g(phrase)g Fp(NP)h Fq(when)f Fp(NP)-125 1208 y Fq(is)15 b(not)g(a)f(nominal)g(anaphor)f(and)h(\(the)h(conceptual)d (referent)j(of)g(the\))g Fp(NP)-125 1254 y Fq(is)f(only)e(connected)f (via)h(certain)h(types)f(of)h(relations)g(\(e.g.,)h Fp(has\255pr)n (operty)n(,)-125 1299 y(has\255physical\255part)p Fq(\))153 1284 y Fm(4)188 1299 y Fq(to)f(referents)f(denoted)e(in)i(the)g (current)g(utterance)g(at)-125 1345 y(the)d(conceptual)f(le)o(v)o(el.) -83 1391 y(W)m(e)g(will)i(illustrate)f(our)f(approach)e(to)j(te)o(xt)g (ellipsis)f(resolution,)g(referring)-125 1436 y(to)g(the)f(already)f (introduced)h(te)o(xt)g(fragment)h(\(1\))g(\226)f(\(3\).)h(\(3\))g (contains)e(the)h(de\002\255)-125 1482 y(nite)i(noun)e(phrase)g Fp(\223die)h(Ladezeit\224)p Fq(.)f(At)i(the)f(conceptual)f(le)o(v)o (el,)h Fp(\223Ladezeit\224)-125 1528 y(\(c)o(har)o(ge)g(time\))j Fq(does)e(not)h(subsume)d(an)o(y)j(element)f(of)h(the)g (forward\255looking)-125 1573 y(centers)h(of)h(the)g(pre)o(vious)e (utterance)h(\()p Fk(C)421 1577 y Fi(f)442 1573 y Fh(\()p Fk(U)483 1577 y Fm(2)497 1573 y Fh(\))26 b(=)12 b Fq([316L)m(T)m(,)f(A) o Fn(CCUMULA)p Fq(\255)-125 1619 y Fn(T)o(OR)p Fq(,)16 b(T)p Fn(IME)p Fq(\255U)p Fn(NIT)m Fq(\255P)m Fn(AIR)p Fq(,)f(P)p Fn(O)o(WER)p Fq(]\).)g(Thus,)f(the)g(anaphora)f(test)h (fails;)h(the)-125 1665 y(conceptual)8 b(referent)h(of)g Fp(\223die)g(Ladezeit\224)e Fq(has)h(also)h(not)g(been)f(inte)o(grated) h(in)-125 1710 y(terms)k(of)g(a)f(signi\002cant)f(relation)h(into)h (the)f(conceptual)e(representation)i(of)-125 1756 y(the)e(utterance)e (as)h(a)g(result)g(of)h(its)g(semantic)e(interpretation.)i (Consequently)n(,)-125 1802 y(the)f(search)f(for)i(an)f(antecedent)e (of)i(the)g(te)o(xtual)h(ellipsis)f(is)g(triggered.)-83 1847 y(The)j(forward\255looking)h(centers)f(of)h(the)g(pre)o(vious)f (sentence)f(are)h(tested)-125 1893 y(for)k(the)g(predicate)e Fp(Pr)o(eferr)o(ed)o(Conc)o(eptua)o(lBridg)o(e)p Fq(.)f(In)i(this)h (case,)e(the)h(in\255)-125 1939 y(stance)10 b(316L)m(T)g(\(the)i (conceptual)d(referent)j(of)f(the)g(nominal)g(anaphor)f Fp(\223der)-125 1984 y(Rec)o(hner\224)d(\(the)h(computer\))p Fq(,)g(which)g(has)f(already)h(been)f(properly)h(resolv)o(ed\))-125 2030 y(is)15 b(related)f(to)h(C)p Fn(HARGE)p Fq(\255T)p Fn(IME)e Fq(\(the)i(concept)e(denoting)g Fp(\223Ladezeit\224)p Fq(\))g(via)-125 2076 y(a)f Fp(metonymic)f(path)p Fq(,)h(viz.)g Fp(\(c)o(har)o(ge\255time\255of)24 b(accumulator)o(\255of\))p Fq(.)12 b(This)f(path)-125 2121 y(corresponds)c(to)h(a)g Fp(whole\255for)o(\255part)g Fq(meton)o(ymy)n(,)g(as)g Fp(c)o(har)o(ge)e(time)j Fq(is)f(a)h(direct)-125 2167 y(property)j(of)g(an)f(accumulator)g(and)g(therefore)h(only)f(a)h (mediated)f(property)-125 2213 y(of)f(a)g(computer)f(as)f(a)i(whole.)f (In)h(contrast,)f(the)h(concept)e(A)o Fn(CCUMULA)m(T)o(OR)g Fq(is)p -125 2248 1022 4 v -125 2274 a Fm(4)-97 2286 y Fs(The)13 b(distinction)f(between)g(roles)g(and)g(their)h(in)o (verses)e(becomes)g(crucial)i(for)g(al\255)-95 2321 y(ready)6 b(established)h(relations)h(like)f Fo(has\255pr)o(operty)f Fs(\(subsuming)g Fo(char)o(ge\255time)p Fs(,)g(etc.\))-95 2357 y(or)j Fo(has\255physical\255part)e Fs(\(subsuming)h Fo(has\255accumulator)p Fs(,)g(etc.\).)i(The)f(instantiation)-95 2393 y(of)f(these)g(relations)h(does)f(not)p 212 2400 43 2 v 8 w(block)g(the)h(triggering)f(of)g(the)h(resolution)f (procedure)-95 2428 y(for)j(textual)f(ellipsis)i(\(e.g.,)g(A)o Fc(CCUMULA)m(TOR)e Fs(\226)i Fo(char)o(ge\255time)c Fs(\226)k(C)p Fc(HARGE)p Fs(\255T)p Fc(IME)p Fs(\),)-95 2464 y(whereas)7 b(instantiations)h(of)g(their)h(in)o(verses,)e(we)h(here)g(refer)h(to)f (as)h Fo(POF\255type)f(r)o(ela\255)-95 2500 y(tions)p Fs(,)f(e.g.,)h Fo(pr)o(operty\255of)e Fs(\(subsuming)g Fo(char)o(ge\255time\255of)p Fs(,)f(etc.\))j(or)g Fo (physical\255part\255of)-95 2535 y Fs(\(subsuming)d Fo(accumulator)o (\255of)p Fs(,)h(etc.\),)i(do)e(\(e.g.,)i(C)p Fc(HARGE)p Fs(\255T)p Fc(IME)g Fs(\226)f Fo(char)o(ge\255time\255of)-95 2571 y Fs(\226)g(A)o Fc(CCUMULA)m(TOR)p Fs(\).)g(This)h(is)g(simply)f (due)g(to)g(the)h(fact)f(that)g(the)h(semantic)e(interpre\255)-95 2607 y(tation)g(of)g(a)h(phrase)e(like)h Fo(\223the)h(char)o(ge)t(time) g(of)f(the)g(accumulator\224)f Fs(already)h(leads)g(to)-95 2643 y(the)i(creation)g(of)g(the)h Fo(POF)p Fs(\255type)g(relation)f (the)g(resolution)g(mechanism)f(for)i(textual)-95 2678 y(ellipsis)e(is)h(supposed)d(to)i(determine.)f(This)i(is)f(opposed)f (to)h(the)g(interpretation)f(of)h(its)-95 2714 y(ellipti\002ed)g (counterpart)f Fo(\223the)h(char)o(ge)e(time\224)j Fs(in)f(sentence)f (\(3\),)h(where)g(the)g(geniti)o(ve)-95 2750 y(object)i Fo(\223[of)i(the)e(accumulator]\224)g Fs(is)h(elided)g(and,)g(thus,)f (the)h(role)g Fo(char)o(ge\255time\255of)-95 2785 y Fs(remains)d (uninstantiated.)971 25 y Fq(related)12 b(to)h(C)p Fn(HARGE)p Fq(\255T)p Fn(IME)e Fq(via)h(a)f Fp(plausible)h(path)f Fq(\(viz.)i Fp(c)o(har)o(ge\255time\255of)p Fq(\).)971 71 y(As)f(plausible)f(paths)g(are)h(the)g(strongest)f(type)g(of)i (conceptual)d(paths,)h(none)971 117 y(of)j(the)f(items)g(follo)o(wing)g (in)h(the)f(centering)f(list)i(can)e(be)g(preferred)i(as)e(the)971 162 y(antecedent)d(of)i Fp(\223Ladezeit\224)e(\(c)o(har)o(ge)g(time\))j Fq(o)o(v)o(er)f Fp(\223Akku\224)e(\(accumulator\))971 208 y Fq(\(cf.)k(the)f(constraint)f(from)i(T)m(able)e(7\).)i(Hence,)d (the)i(remaining)g(concepts)d(in)971 254 y(the)16 b Fk(C)1060 258 y Fi(f)1096 254 y Fq(list)h(\()p Fp(viz.)f Fq(T)p Fn(IME)p Fq(\255U)p Fn(NIT)m Fq(\255P)m Fn(AIR)h Fq(and)e(P)p Fn(O)o(WER)p Fq(\))h(need)e(no)i(longer)f(be)971 299 y(considered)8 b(as)h(potential)h(antecedents.)e(An)h(appropriate)h (update)e(links)i(the)971 345 y(corresponding)g(instances)g(via)h(the)g (role)h Fp(c)o(har)o(ge\255time\255of)f Fq(and,)g(thus,)g(local)971 391 y(coherence)6 b(is)h(established)f(at)i(the)f(conceptual)f(le)o(v)o (el)i(of)g(the)f(te)o(xt)i(kno)o(wledge)971 436 y(base.)f(A)h(fully)h (worked)e(out)h(parsing)f(e)o(xample)g(together)g(with)i(a)f (discussion)971 482 y(of)h(a)f(medium\255sized)f(performance)g(e)o(v)o (aluation)g(of)i(the)f(criteria)h(considered)971 528 y(for)g(ellipsis)f(resolution)g(is)h(gi)o(v)o(en)e(in)i([9].)971 633 y Ft(6)46 b(Comparison)11 b(with)h(Related)g(A)o(ppr)o(oaches)971 685 y Fq(Searching)5 b(links)h(in)h(a)f(taxonomic)f(hierarchy)g(is)i(a) f(problem)g(which)g(has)f(often)971 731 y(been)10 b(tackled)g(by)g (spreading)g(acti)o(v)o(ation)g(or)h(marker)g(passing)e(approaches.)971 776 y(The)d(paradigm)f(of)i(path)e(\002nding)h(and)f(e)o(v)o(aluating)g (the)o(y)h(propose)f(has)g(ob)o(vious)971 822 y(parallels)13 b(to)g(our)g(approach.)e(The)h(criteria)i(used)e(in)h(spreading)e(acti) o(v)o(ation)971 868 y(models)6 b(for)h(\002nding)e(and)g(e)o(v)o (aluating)g(paths,)h(ho)o(we)o(v)o(er)o(,)g(are)g(mostly)g(based)t(on) 971 913 y(numerical)j(restrictions,)h(e.g.,)g(on)f(weights)f([2])i(or)g (path)f(lengths)f([10].)i(This)971 959 y(is)h(problematic,)f(as)g(the)g (foundation)f(and)h(deri)o(v)o(ation)g(of)g(these)f(numbers)h(is)971 1005 y(usually)f(not)g(made)f(e)o(xplicit.)1013 1050 y(The)e(abduction\255based)t(approach)g(to)h(inferencing)f(underlying)g (the)h(T)m(A)o(C\255)971 1096 y(ITUS)12 b(system)e([11])h(also)g (refers)g(to)h(weights)e(and)h(costs)f(and,)g(thus,)h(shares)971 1142 y(some)d(similarity)i(with)f(marker)g(passing)e(proposals)g([11,)i (p.)g(122].)f(The)g(cru\255)971 1187 y(cial)h(problem,)f(ho)o(we)o(v)o (er)o(,)g(still)i(unsolv)o(ed)d(in)i(this)f(logically)h(v)o(ery)f (principled)971 1233 y(frame)o(work)j(concerns)e(a)i(proper)f(choice)g (methodology)f(for)j(\002xing)e(appro\255)971 1279 y(priate)h(costs)e (for)h(speci\002c)f(assumptions)f(on)h(which,)h(among)f(other)h (factors,)971 1324 y(te)o(xtual)g(ellipsis)f(resolution)g(is)g (primarily)h(based.)1013 1370 y(A)e(pattern\255based)e(approach)f(to)j (inferencing)f(\(including)h(te)o(xtual)g(ellipsis)971 1416 y(resolution\))f(has)e(also)h(been)f(put)i(forward)f(by)g(Norvig)h ([16)o(].)h(Unlike)e(Norvig')n(s)971 1461 y(proposal)j(to)i(de\002ne)e (path)g(patterns)h(solely)g(in)g(terms)g(of)h(\223formal\224)f(link)h (cri\255)971 1507 y(teria)e(in)g(a)f(kno)o(wledge)f(base)g(whose)g (patterns)h(are)g(simply)h(matched)e(against)971 1553 y(the)13 b(links)f(being)f(passed,)g(our)h(de\002nitions)g(of)g(path)g (patterns)g(take)g(the)g(se\255)971 1598 y(mantic)c(hierarchy)g(of)g (relations)g(and)g(their)h(compositional)e(properties)g(\(like)971 1644 y(transiti)o(vity\))15 b(into)e(account.)f(This)g(allo)o(ws)h(for) g(a)g(semantically)f(moti)o(v)o(ated)971 1689 y(preference)6 b(ranking)g(of)g(the)g(p)o(aths)f(by)g(treating)h(the)g(p)o(hen)o(omen) o(a)g(o)o(f)g(granu)o(lar)o(\255)971 1735 y(ity)k(\(corresponding)c(to) j(plausible)f(paths\))g(and)f(meton)o(ymy)h(\(corresponding)971 1781 y(to)i(meton)o(ymic)f(paths\))g(in)h(a)f(uni\002ed)g(search)f (algorithm.)i(Although)f(Norvig)971 1826 y(makes)g(a)h(strong)g(point)h (concerning)d(his)j(use)e(of)i(path)f(patterns)g(\(instead)f(of)971 1872 y(marker)i(ener)o(gy\))f(to)h(guide)g(the)f(search)g(in)h(a)f(kno) o(wledge)f(base,)h(the)h(de\002ni\255)971 1918 y(tions)f(of)g(path)g (patterns)f(he)h(gi)o(v)o(es)f(are)h(not)g(restricti)o(v)o(e)h(enough.) e(Additional)971 1963 y(numerical)f(rules)h(for)g(coping)f(with)h (combinatorial)f(search)f(problems)h(\(e.g.,)971 2009 y(an)j(antipromiscuity)h(rule\))g(still)h(ha)o(v)o(e)e(to)h(be)f (supplied,)g(whereas)g(our)g(path)971 2055 y(patterns)d(are)g (complemented)f(by)h(structural)g(formal)i(criteria)f(which)f(do)g(not) 971 2100 y(rely)k(upon)d(numerical)i(restrictions)g(in)g(an)o(y)f(way)n (.)g(The)g(c)o(yclicity)i(criterion,)971 2146 y(e.g.,)d(leads)e(to)i (path)f(length)f(\(and)h(thus)g(granularity\))h(independenc)o(e)d(and)h (the)971 2192 y(inclusion)i(criterion)h(further)g(abstracts)e(from)i (node)e(counting.)1013 2237 y(As)15 b(far)h(as)e(te)o(xt\255le)o(v)o (el)j(processing)c(is)j(concerned,)d(the)i(frame)o(work)g(of)971 2283 y(DR)n(T)d([13],)h(at)g(\002rst)f(sight,)h(constitutes)e(a)h (particularly)h(strong)e(alternati)o(v)o(e)971 2329 y(to)g(our)g (approach.)e(The)h(machinery)f(of)i(DR)n(T)m(,)g(ho)o(we)o(v)o(er)o(,)f (might)h(work)f(well)971 2374 y(for)k(\(pro\)nominal)f(anaphora,)f(b)o (ut)h(faces)e(problems)h(when)g(elliptical)i(te)o(xt)971 2420 y(phenomena)9 b(are)i(to)g(be)f(interpreted)i(\(though)e([21])h (has)g(recently)f(made)g(an)971 2466 y(attempt)c(to)g(deal)g(with)g (restricted)g(forms)g(of)g(te)o(xtual)g(ellipsis)g(in)g(the)g(DR)n(T)g (con\255)971 2511 y(te)o(xt\).)j(This)f(shortcoming)e(is)i(simply)f (due)g(to)h(the)f(fact)h(that)g(DR)n(T)f(is)h(basically)971 2557 y(a)13 b(semantic)f(theory)n(,)g(not)h(a)g(full\255\003edged)f (model)g(for)i(te)o(xt)g(understanding.)971 2603 y(In)g(particular)o(,) g(it)g(lacks)e(an)o(y)h(systematic)g(connection)e(to)j(well\255de)o(v)o (eloped)971 2648 y(reasoning)5 b(systems)h(accounting)t(for)i (conceptual)t(domain)e(kno)o(wledge.)g(Ac\255)971 2694 y(tually)n(,)k(the)f(sort)g(of)h(constraints)e(we)h(consider)f(seem)g (much)g(more)i(rooted)e(in)971 2740 y(enc)o(yclopedic)e(kno)o(wledge)h (than)g(are)h(the)o(y)g(of)h(a)f(primarily)h(semantic)e(nature)971 2785 y(an)o(yway)n(.)-125 2885 y Fr(Natural)i(Language)e(Pr)o(ocessing) 553 b(575)448 b(U)n(.)10 b(Hahn,)f(K.)h(Markert)e(and)g(M.)i(Strube)p eop %%Page: 574 3 574 2 bop 2 14 a Fg(T)m(able)8 b(4.)33 b Fs(Path)8 b(Markers)f(Ordered) g(by)g(Conceptual)g(Strength)p 7 32 750 2 v 7 87 2 55 v 38 67 a(\223plausible\224)g Fe(>)223 71 y Fi(str)275 67 y Fs(\223metonymic\224)f Fe(>)489 71 y Fi(str)541 67 y Fs(\223implausible\224)p 755 87 V 7 89 750 2 v -125 142 a Fq(As)i(a)f(consequenc)o(e)e(of)i(this)h(ordering,)g(meton)o (ymic)f(paths)g(will)h(be)f(e)o(xcluded)-125 188 y(from)14 b(a)e(path)g(list)i(if)o(f)g(plausible)d(paths)h(already)f(e)o(xist,)j (while)e(implausible)-125 234 y(paths)7 b(will)i(be)e(e)o(xcluded)f(if) o(f)k(plausible)c(or)i(meton)o(ymic)g(paths)e(already)h(e)o(xist.)-125 279 y(At)k(the)f(end)f(of)i(this)f(selection)f(process,)g(only)h(paths) f(of)h(the)g(strongest)f(type)-125 325 y(are)g(retained)g(in)h(the)e (path)h(list.)-83 371 y(T)m(o)h(e)o(v)o(aluate)e(our)i(approach)e(we)i (selected)e(80)i(concept)e(pairs)h(at)i(random)-125 416 y(from)f(the)e(underlying)f(kno)o(wledge)f(base)h(\(composed)g(of)h (459)g(concepts)e(and)-125 462 y(334)k(relations\).)h(W)m(e)g (submitted)f(these)f(pairs)h(to)h(the)f(path)g(\002nder/e)o(v)o (aluator)-125 508 y(and)f(compared)f(the)h(automatically)g(generated)f (conceptual)g(paths)g(with)i(in\255)-125 553 y(trospecti)o(v)o(e)g (judgments)f(about)h(the)g(kinds)f(of)i(relations)f(linking)g(each)f (pair)n(.)-125 599 y(The)j(o)o(v)o(erall)i(error)f(rate)g(was)e(belo)o (w)h(5\045.)h(The)f(a)o(v)o(erage)g(number)f(of)i(con\255)-125 645 y(nected)7 b(paths)g(between)g(two)h(concepts)e(\(41.8\))j(was)e (further)i(reduced)d(by)i(the)-125 690 y(non\255c)o(yclicity)13 b(criterion)g(to)g(10.4)g(well\255formed)g(paths)f(and)g(by)g(the)g (inclu\255)-125 736 y(sion)g(criterion)g(\(see)f(T)m(able)g(2\))h(to)g (2.4.)f(The)g(criterion)i(in)f(T)m(able)e(4)i(leads)f(to)-125 782 y(a)h(\002nal)f(reduction)f(to)i(merely)g(1.8)f(paths.)g(Hence,)f (the)h(criteria)i(realize)e(the)-125 827 y(desired)c(discrimination.)i (W)m(e)f(plan)f(a)h(broader)f(e)o(v)o(aluation)g(of)h(our)g(approach) -125 873 y(by)g(running)g(the)g(algorithm)g(on)g(lar)o(ger)o(\255sized) g(kno)o(wledge)f(bases)f(in)i(order)h(to)-125 918 y(test)h(its)f (domain\255independence)d(and)i(scaling)g(performance.)-83 964 y(All)h(paths)f(which)g(meet)h(the)f(abo)o(v)o(e)g(criteria)h(for)h (two)e(concepts,)f Fk(x)h Fq(and)g Fk(y)q Fq(,)-125 1010 y(are)k(contained)f(in)h(a)g(list)h(denoted)e(by)h(CP)446 1014 y Fi(x;y)491 1010 y Fq(.)h(As,)f(in)g(the)g(case)f(of)i(te)o (xtual)-125 1055 y(ellipsis,)k(we)g(ha)o(v)o(e)e(to)i(deal)f(with)h (paths)f(leading)f(from)i(the)g(conceptual)-125 1101 y(referent)f(of)g(the)f(elliptical)h(e)o(xpression)e(to)i(the)f (conceptual)e(referents)j(of)-125 1147 y(se)o(v)o(eral)e(possible)f (antecedents,)f(we)i(usually)f(ha)o(v)o(e)g(to)i(compare)e(pairs)h(of) -125 1192 y(path)c(lists)h(CP)67 1196 y Fi(x;y)123 1192 y Fq(and)e(CP)233 1196 y Fi(x;z)278 1192 y Fq(,)i(where)e(x,)i(y)n(,)f (z)g Fl(2)g(F)k Fq(\()p Fk(y)g Fl(6)p Fh(=)e Fk(z)r Fq(\).)f(F)o (ortunately)n(,)-125 1238 y(the)j(same)e(criteria)i(can)f(be)g(applied) f(to)i(path)f(lists)h(as)e(those)h(we)g(used)f(for)-125 1284 y(e)o(v)o(aluating)f(paths)g(linking)h(single)g(concepts.)e(As)i (all)g(paths)f(in)h(CP)785 1288 y Fi(x;y)843 1284 y Fq(and)-125 1329 y(CP)-79 1333 y Fi(x;z)-18 1329 y Fq(were)17 b(computed)e(by)h (the)g(path)g(\002nder)o(,)f(the)o(y)i(already)e(ful\002ll)j(the)-125 1375 y(connecti)o(vity)7 b(and)g(non\255c)o(yclicity)g(condition.)g (The)g(inclusion)g(criterion)h(\(see)-125 1421 y(T)m(able)i(2\))h (cannot)f(be)g(applied)g(to)h(an)o(y)f(path)g Fk(p)486 1425 y Fm(1)512 1421 y Fl(2)h Fq(CP)595 1425 y Fi(x;y)651 1421 y Fq(and)f Fk(p)735 1425 y Fm(2)760 1421 y Fl(2)h Fq(CP)843 1425 y Fi(x;z)887 1421 y Fq(,)-125 1466 y(as)h Fk(p)-62 1470 y Fm(1)-34 1466 y Fq(and)f Fk(p)51 1470 y Fm(2)79 1466 y Fq(ha)o(v)o(e)h(dif)o(ferent)h(end)e(points,)i(by)f (de\002nition.)g(Ho)o(we)o(v)o(er)o(,)g(the)-125 1512 y(criterion)f(which)f(ranks)f(conceptual)g(paths)g(according)g(to)h (their)h(associated)-125 1558 y(path)h(markers)f(is)i(applicable,)e(as) g(all)i(paths)e(in)i(a)f(single)f(CP)h(list)h(ha)o(v)o(e)f(the)-125 1603 y(same)6 b(marker)n(.)g(A)g(function,)g Fp(P)m(athMarker)o Fq(\(CP)490 1607 y Fi(i;j)524 1603 y Fq(\),)g(yields)g(as)g(its)g(v)o (alue)g(either)-125 1649 y Fp(\223plausible\224)p Fq(,)11 b Fp(\223metonymic\224)f Fq(or)h Fp(\223implausible\224)f Fq(depending)f(on)i(the)g(type)-125 1695 y(of)i(paths)f(it)h(contains.) f(W)m(e)g(may)h(no)o(w)f(apply)f(the)i(same)e(ordering)h(of)h(path)-125 1740 y(markers)c(as)f(in)i(T)m(able)e(4)h(in)g(order)h(to)f(compare)f (two)h(CP)g(lists)h(\(cf.)g(T)m(able)e(5\).)10 1807 y Fg(T)m(able)g(5.)33 b Fs(Path)8 b(Lists)h(Compared)e(by)g(Conceptual)g (Strength)p -125 1825 1022 2 v -125 2030 2 205 v 17 1863 a(isStrongerThan)g(\(CP)281 1867 y Fi(x;y)327 1863 y Fs(,)26 b(CP)401 1867 y Fi(x;z)446 1863 y Fs(\))8 b(:)p Fd(,)84 1899 y Fs(PathMarker\(CP)293 1903 y Fi(x;y)337 1899 y Fs(\))16 b Fe(>)391 1903 y Fi(str)461 1899 y Fs(PathMarker\(CP) 670 1903 y Fi(x;z)713 1899 y Fs(\))42 1970 y(equallyStrongAs)7 b(\(CP)325 1974 y Fi(x;y)371 1970 y Fs(,)25 b(CP)444 1974 y Fi(x;z)489 1970 y Fs(\))9 b(:)p Fd(,)108 2006 y Fs(PathMarker\(CP)317 2010 y Fi(x;y)362 2006 y Fs(\))16 b Ff(=)26 b Fs(PathMarker\(CP)651 2010 y Fi(x;z)694 2006 y Fs(\))p 895 2030 V -125 2032 1022 2 v -125 2140 a Ft(3)46 b(Functional)12 b(Constraints)g(on)f(Centers)-125 2192 y Fq(Conceptual)g(criteria)i(are)g(of)f(tremendous)f(importance,)h(b)o (ut)g(the)o(y)h(are)f(not)-125 2237 y(suf)o(\002cient)i(for)g(proper)g (ellipsis)g(resolution.)g(Additional)g(criteria)h(ha)o(v)o(e)f(to)-125 2283 y(be)e(supplied)g(in)g(the)g(case)f(of)i(equal)f(strength)f(of)i (CP)f(lists)h(for)g(alternati)o(v)o(e)-125 2329 y(antecedents.)c(W)m(e) h(therefore)h(incorporate)f(into)g(our)h(model)f(criteria)h(which)-125 2374 y(relate)g(to)g(the)f(functional)g(information)h(structure)g(of)f (utterances)f(using)h(the)-125 2420 y(methodological)e(frame)o(work)h (of)h(the)f(well\255kno)o(wn)g Fp(centering)e Fq(model)i([6].)-83 2466 y(The)h(theory)h(of)g(centering)f(is)h(intended)e(to)i(model)g (the)g(local)f(coherence)-125 2511 y(of)g(discourse,)d(i.e.,)j (coherence)c(among)i(the)h(utterances)e(in)i(a)f(particular)i(dis\255) -125 2557 y(course)j(se)o(gment)h(\(say)n(,)g(a)g(paragraph)f(of)h(a)g (te)o(xt\).)i(Each)d(utterance)h Fk(U)840 2561 y Fi(i)868 2557 y Fq(in)-125 2603 y(a)h(discourse)e(se)o(gment)i(is)g(assigned)d (a)j(set)g(of)g Fp(forwar)o(d\255looking)e(centers)p Fq(,)-125 2648 y Fk(C)-98 2652 y Fi(f)-77 2648 y Fh(\()p Fk(U)-36 2652 y Fi(i)-23 2648 y Fh(\))p Fq(,)i(and)e(a)h(unique)f Fp(bac)o(kwar)o(d\255looking)e(center)p Fq(,)i Fk(C)659 2652 y Fi(b)675 2648 y Fh(\()p Fk(U)716 2652 y Fi(i)730 2648 y Fh(\))p Fq(.)h(The)g(ele\255)-125 2694 y(ments)c(of)g Fk(C)43 2698 y Fi(f)63 2694 y Fh(\()p Fk(U)104 2698 y Fi(i)118 2694 y Fh(\))g Fq(are)f(partially)i(ordered)e(to)h(re\003ect)g (relati)o(v)o(e)g(prominence)-125 2740 y(in)h Fk(U)-59 2744 y Fi(i)-46 2740 y Fq(.)f(The)g(most)f(highly)h(ranked)e(element)i (of)g Fk(C)538 2744 y Fi(f)558 2740 y Fh(\()p Fk(U)599 2744 y Fi(i)612 2740 y Fh(\))g Fq(that)g(is)g Fp(r)o(ealized)f Fq(in)-125 2785 y Fk(U)-99 2789 y Fi(i)p Fb(+)p Fm(1)-39 2785 y Fq(\(i.e.,)i(is)f(associated)e(with)i(an)f(e)o(xpression)g(that) h(has)e(a)i(v)o(alid)g(semantic)971 28 y(interpretation\))e(is)f(the)g Fk(C)1304 32 y Fi(b)1320 28 y Fh(\()p Fk(U)1361 32 y Fi(i)p Fb(+)p Fm(1)1410 28 y Fh(\))p Fq(.)h(The)e(ranking)g(imposed)g (on)h(the)g(elements)971 74 y(of)h(the)f Fk(C)1090 78 y Fi(f)1118 74 y Fq(re\003ects)g(the)g(assumption)f(that)i(the)f(most)g (highly)g(ranked)f(element)971 119 y(of)g Fk(C)1035 123 y Fi(f)1056 119 y Fh(\()p Fk(U)1097 123 y Fi(i)1110 119 y Fh(\))g Fq(is)g(the)g(most)g(preferred)g(antecedent)g(of)g(an)g(a)o (nap)o(horic)g(e)o(xpres)o(sion)971 165 y(in)h Fk(U)1033 169 y Fi(i)p Fb(+)p Fm(1)1082 165 y Fq(,)h(while)f(the)g(remaining)f (elements)g(are)h(partially)g(ordered)f(according)971 211 y(to)k(decreasing)d(preference)h(for)i(establishing)e(referential)h (links.)1013 256 y(The)d(theory)h(of)h(centering,)e(in)i(addition,)f (de\002nes)e(se)o(v)o(eral)i(transition)g(rela\255)971 302 y(tions)h(across)e(pairs)h(of)h(adjacent)e(utterances)g(\(e.g.,)j (continuation,)d(retention,)971 348 y(smooth)g(and)f(rough)g(shift\),)j (which)d(dif)o(fer)i(from)g(each)e(other)h(according)f(to)h(the)971 393 y(de)o(gree)i(by)h(which)f(successi)o(v)o(e)e(backward\255looking)h (centers)g(are)i(con\002rmed)971 439 y(or)f(rejected,)f(and,)g(if)h (the)o(y)f(are)g(con\002rmed,)f(whether)h(the)o(y)g(correspond)e(to)j (the)971 485 y(most)g(highly)f(ranked)f(element)h(of)h(the)f(current)h (forward\255looking)f(centers)f(or)971 530 y(not.)g(The)g(theory)g (claims)g(that)g(to)g(the)g(e)o(xtent)g(a)g(d)o(isco)o(urse)g(a)o(dhe)o (res)g(to)g(a)o(ll)g(these)971 576 y(centering)j(constraints)f(\(e.g.,) j(realization)e(constraints)f(on)h(pronouns,)f(pref\255)971 622 y(erences)j(among)g(types)g(of)h(center)g(transitions\),)h(its)g (local)f(coherence)d(will)971 667 y(increase)f(and)f(the)i(inference)f (load)g(placed)f(upon)h(the)g(hearer)h(will)h(decrease.)971 713 y(Therefore,)d(the)f(tremendous)f(importance)h(of)h(\003eshing)e (out)i(the)f(rele)o(v)o(ant)h(and)971 759 y(most)i(restricti)o(v)o(e,)i (though)d(still)i(general)f(centering)f(constraints.)1013 804 y(The)i(main)g(dif)o(ference)g(between)f(Grosz)h Fp(et)g(al.)-5 b(')p Fq(s)11 b(seminal)f(work)f([6)q(])i(and)971 850 y(our)e(proposal)f(\(see)g([20]\))i(concerns)c(the)j(criteria)h (for)f(ranking)g(the)f(forward\255)971 896 y(looking)k(centers.)h (While)g(Grosz)f Fp(et)h(al.)g Fq(assume)e(that)i Fp(gr)o(ammatical)f (r)n(oles)971 941 y Fq(are)g(the)f(major)g(determinant)g(for)i(the)e (ranking)f(on)h(the)h Fk(C)1746 945 y Fi(f)1766 941 y Fq(,)g(we)f(claim)g(that)971 987 y(for)g(languages)c(with)j(relati)o(v) o(ely)h(free)f(word)f(order)h(\(such)f(as)g(German\),)h(it)h(is)971 1033 y(the)f Fp(functional)g(information)f(structur)o(e)f(\(IS\))j Fq(of)f(the)g(utterance)f(in)h(terms)g(of)971 1078 y(the)d(conte)o (xt\255boundednes)o(s)t(or)g(unboundednes)o(s)t(of)g(its)g(discourse)e (elements.)971 1124 y(The)k(centering)f(data)h(structures)g(and)f(the)h (notion)g(of)h(conte)o(xt\255boundedne)o(ss)971 1170 y(can)15 b(be)g(used)f(to)h(rede\002ne)f(Danes')h([4])h(trichotomy)f (between)g Fp(given)f(in\255)971 1215 y(formation)p Fq(,)g Fp(theme)f Fq(and)g Fp(ne)o(w)g(information)g Fq(\(which)h(he)f (considers)f(equi)o(v\255)971 1261 y(alent)j(to)g Fp(rheme)p Fq(\).)g(The)f Fk(C)1334 1265 y Fi(b)1350 1261 y Fh(\()p Fk(U)1391 1265 y Fi(n)1413 1261 y Fh(\))p Fq(,)h(the)g(most)g(highly)f (ranked)g(element)g(of)971 1307 y Fk(C)998 1311 y Fi(f)1019 1307 y Fh(\()p Fk(U)1060 1311 y Fi(n)p Fj(\000)p Fm(1)1117 1307 y Fh(\))e Fq(realized)e(in)i Fk(U)1340 1311 y Fi(n)1361 1307 y Fq(,)g(corresponds)d(to)i(the)g(element)g(which)f(repre\255)971 1352 y(sents)h(the)g Fp(given)g Fq(information.)h(The)f Fp(theme)g Fq(of)g Fk(U)1644 1356 y Fi(n)1677 1352 y Fq(is)h(represented)e(by)h(the)971 1398 y(preferred)c(center)f Fk(C)1240 1402 y Fi(p)1259 1398 y Fh(\()p Fk(U)1300 1402 y Fi(n)1321 1398 y Fh(\))p Fq(,)h(the)g(most)g(highly)f(ranked)f (element)i(of)g Fk(C)1886 1402 y Fi(f)1906 1398 y Fh(\()p Fk(U)1947 1402 y Fi(n)1968 1398 y Fh(\))p Fq(.)971 1444 y(The)k Fp(theme/rheme)e(hier)o(ar)o(c)o(hy)g Fq(of)i Fk(U)1467 1448 y Fi(n)1500 1444 y Fq(is)g(determined)g(by)f(the)h Fk(C)1848 1448 y Fi(f)1868 1444 y Fh(\()p Fk(U)1909 1448 y Fi(n)p Fj(\000)p Fm(1)1967 1444 y Fh(\))p Fq(:)971 1489 y(the)d(rhematic)g(elements)f(of)i Fk(U)1371 1493 y Fi(n)1400 1489 y Fq(are)f(the)g(ones)f(not)h(contained)e(in)j Fk(C)1859 1493 y Fi(f)1879 1489 y Fh(\()p Fk(U)1920 1493 y Fi(n)p Fj(\000)p Fm(1)1978 1489 y Fh(\))971 1535 y Fq(\(unbound)f(discourse)g(elements\))h(\226)g(the)o(y)h(e)o(xpress)e (the)h Fp(ne)o(w)g(information)g Fq(in)971 1581 y Fk(U)997 1585 y Fi(n)1019 1581 y Fq(.)g(The)e(ones)g(contained)g(in)i Fk(C)1399 1585 y Fi(f)1419 1581 y Fh(\()p Fk(U)1460 1585 y Fi(n)p Fj(\000)p Fm(1)1518 1581 y Fh(\))f Fq(and)g Fk(C)1631 1585 y Fi(f)1651 1581 y Fh(\()p Fk(U)1692 1585 y Fi(n)1713 1581 y Fh(\))h Fq(\(bound)e(discourse)971 1626 y(elements\))i(are)g(thematic,)g(with)h(the)f(theme/rheme)g (hierarchy)f(correspond\255)971 1672 y(ing)h(to)h(the)f(ranking)f(in)i (the)f Fk(C)1366 1676 y Fi(f)1386 1672 y Fq(s.)971 1777 y Ft(4)46 b(Grammatical)10 b(Pr)o(edicates)j(f)o(or)f(T)l(extual)f (Ellipsis)971 1828 y Fq(The)e(grammar)g(formalism)h(we)f(use)f(\(cf.)i ([8])g(for)g(a)e(surv)o(e)o(y\))i(is)f(based)e(on)i(de\255)971 1874 y(pendenc)o(y)f(relations)h(between)f(le)o(xical)i(heads)d(and)i (modi\002ers.)g(The)g(depen\255)971 1920 y(denc)o(y)f(speci\002cations) e(allo)o(w)j(a)f(tight)i(inte)o(gration)f(of)g(linguistic)g (\(grammar\))971 1965 y(and)k(conceptual)e(kno)o(wledge)h(\(domain)h (model\),)g(thus)g(making)g(po)o(werful)971 2011 y(terminological)f (reasoning)e(facilities)i(directly)g(a)o(v)o(ailable)g(for)g(the)g (parsing)971 2057 y(process)1085 2041 y Fm(3)1098 2057 y Fq(.)i(The)g(resolution)g(of)g(te)o(xtual)h(ellipses)e(is)h(based)f (on)g(two)h(major)971 2102 y(criteria,)g(a)e(conceptual)e(and)i(a)g (structural)g(one.)g(The)g(conceptual)e(strength)971 2148 y(criterion)f(for)g(role)g(chains)d(is)j(already)e(speci\002ed)f (in)i(T)m(able)g(5.)g(The)f(structural)971 2194 y(condition)j(is)g (embodied)e(in)j(the)e(predicate)h Fp(isP)m(otentialEllipticAntecedent) 971 2239 y Fq(\(cf.)g(T)m(able)f(6\).)g(The)f(elliptical)i(phrase)e (which)h(occurs)e(in)i(the)g Fp(n\255)p Fq(th)h(utterance)971 2285 y(is)j(restricted)g(to)f(be)g(a)g(de\002nite)g(NP)g(and)g(the)g (antecedent)f(must)h(be)g(one)f(of)971 2331 y(the)d(forward\255looking) f(centers)f(of)i(the)g(preceding)e(utterance)g(\(note)i(that)g Fk(C)1958 2335 y Fi(f)1978 2331 y Fq(s)971 2376 y(contain)h(only)f (conceptual)g(referents)h(of)g(nouns)f(and)g(pronouns\).)1013 2422 y(The)h(predicate)g Fp(Pr)o(eferr)o(edCo)o(nce)o(ptualBr)o(idge)e Fq(\(cf.)k(T)m(able)e(7\))h(combines)971 2468 y(both)f(criteria.)i(A)e (le)o(xical)h(item)f Fp(y)g Fq(is)h(determined)e(as)h(the)g(proper)g (antecedent)p 971 2498 1022 4 v 971 2524 a Fm(3)994 2535 y Fs(W)m(e)g(assume)e(the)g(follo)o(wing)h(conventions)d(to)j(hold:)f Fd(C)j Fs(=)e Fd(f)p Fs(W)m(ord,)g(Nominal,)f(Noun,)1000 2571 y(PronPersonal,...)p Fd(g)k Fs(denotes)d(the)i(set)g(of)g(word)f (classes,)h(and)f Fe(isa)1780 2577 y Fj(C)1810 2571 y Fs(=)h Fd(f)p Fs(\(Nominal,)1000 2607 y(W)m(ord\),)d(\(Noun,)f (Nominal\),)g(\(PronPersonal,)g(Nominal\),...)p Fd(g)g(\032)h(C)e(\002) s(C)k Fs(denotes)c(the)1000 2643 y(subclass)j(relation)g(which)f (yields)h(a)g(hierarchical)f(ordering)g(among)g(these)h(classes.)1000 2678 y(Furthermore,)14 b Fo(object.r)g Fs(refers)g(to)h(the)f(instance) f(in)h(the)g(text)g(kno)o(wledge)f(base)1000 2714 y(denoted)t(by)6 b(the)f(linguistic)h(item)g Fo(object)f Fs(and)g Fo(object.c)g Fs(refers)g(to)h(the)g(corresponding)1000 2750 y(concept)g(class)g Fc(C)p Fs(.)h Fo(Head)f Fs(denotes)f(a)i(structural)f(relation)h (within)f(dependency)t(trees,)1000 2785 y(viz.)j Fo(x)f Fs(being)f(the)h(head)f(of)h(modi\002er)f Fo(y)p Fs(.)-125 2885 y Fr(Natural)i(Language)e(Pr)o(ocessing)553 b(574)448 b(U)n(.)10 b(Hahn,)f(K.)h(Markert)e(and)g(M.)i(Strube)p eop %%Page: 573 4 573 3 bop -125 25 a Fq(e)o(xpresses)6 b(that)j(the)f(end)f(point)h(and) g(the)g(starting)g(point)g(of)h(the)f(search)f(are)h(of)-125 71 y(a)k(similar)o(,)g(though)f(not)g(necessarily)f(of)h(a)h (semantically)e(related)i(type)f(\(for)-125 116 y(this)g(distinction)g (see,)f(e.g.,)i([18)o(]\).)h(F)o(or)e(instance,)f(the)g(path)h(\()p Fp(accumulator)o(\255)-125 162 y(of)29 b(has\255printer)p Fq(\))13 b(will)j(be)e(e)o(xcluded)e(from)j(the)f(search)f(for)i(a)f (path)g(from)-125 208 y(A)o Fn(CCUMULA)m(T)o(OR)e Fq(to)h(P)p Fn(RINTER)g Fq(as)g Fp(accumulator)o(\255of)f Fk(isa)643 212 y Fj(R)685 208 y Fp(physical\255part\255)-125 253 y(of)f Fq(and)e Fp(has\255printer)f Fk(isa)208 257 y Fj(R)247 253 y Fp(has\255physical\255part)f Fq(holds.)j(Thus,)f(the)h (e)o(xample)-125 299 y(path)i(carries)g(the)g(information)h(that)g (both,)f(accumulator)f(and)g(printer)o(,)i(are)-125 345 y(types)d(of)i(hardware,)e(b)o(ut)h(it)h(does)d(not)i(elucidate)f(an)o (y)g(special)g(relationship)-125 390 y(between)15 b(these)h(two)g(that) g(an)g(elliptical)h(e)o(xpression)e(could)g(refer)i(to.)g(A)-125 436 y(warranted)c(side)g(ef)o(fect)g(of)h(the)f(e)o(xclusion)f(of)i(c)o (yclic)f(patterns)g(is)h(that,)g(as)-125 482 y(longer)9 b(paths)f(usually)g(tend)g(to)i(get)e(c)o(yclic,)h(the)g(search)f (terminates)g(without)-125 527 y(the)h(need)f(to)i(take)e(refuge)h(to)g Fp(ad)g(hoc)f Fq(path)h(length)g(restrictions.)-83 573 y(Gi)o(v)o(en)f(the)g(set)g(of)h Fp(well\255formed)p Fq(,)f(i.e.,)i(connected)5 b(and)j(non\255c)o(yclic)f(paths,)-125 619 y(the)k(remaining)e(items)i(of)f(the)h(path)e(list)i(are)f (interpreted)h(by)f(the)g Fp(path)g(e)o(val\255)-125 664 y(uator)p Fq(.)15 b(T)m(wo)f(criteria)i(are)e(considered)f(in)i (order)g(to)g(select)f(the)h Fp(str)n(ongest)-125 710 y Fq(paths)10 b(among)f(the)i(elements)e(of)i(the)f(path)g(list.)i(One) e(considers)f(the)h(formal)-125 756 y(inclusion)h(property)h(between)e (well\255formed)i(paths,)f(the)g(other)h(introduces)-125 801 y(semantically)d(plausible)f(path)h(patterns.)-125 847 y Fr(Path)h(Inclusion.)e Fq(The)h(introduction)g(of)h(a)g Fp(r)o(elative)e(path)h(length)g Fq(condition)-125 893 y(is)e(aimed)f(at)g(constraining)f(the)i(o)o(v)o(erly)f(simplistic)h (counting)f(of)g(nodes)f(in)i(role)-125 938 y(chains.)f(A)h (well\255formed)h(path)f Fk(p)304 942 y Fm(1)325 938 y Fq(=)h Fp(\()p Fk(r)383 942 y Fm(1)405 938 y Fp(...)g Fk(r)457 942 y Fi(n)479 938 y Fp(\))f Fq(is)g Fp(conceptually)e(longer) g Fq(than)-125 984 y(another)k(well\255formed)i(path)e Fk(p)285 988 y Fm(2)310 984 y Fq(=)h Fp(\()p Fk(s)371 988 y Fm(1)396 984 y Fp(...)h Fk(s)452 988 y Fi(m)481 984 y Fp(\))g Fq(if)o(f)g Fk(p)567 988 y Fm(1)592 984 y Fq(properly)e Fp(includes)g Fk(p)882 988 y Fm(2)-125 1030 y Fq(\(see)e(T)m(able)g(2\).)h(The)e(path)h Fk(p)237 1034 y Fm(1)259 1030 y Fq(will)i(then)e(be)f(re)o(garded)h(as)f(being)h (conceptually)-125 1075 y(weaker)h(than)h Fk(p)85 1079 y Fm(2)109 1075 y Fq(and)f(thus)h(be)g(discarded)e(from)j(the)f(path)g (list.)150 1158 y Fg(T)m(able)g(2.)33 b Fs(Path)8 b(Inclusion)f (Criterion)p -125 1169 1022 2 v -125 1373 2 204 v -120 1207 a(Includes)g(\(p)29 1212 y Fm(1)43 1207 y Fs(,)h(p)76 1212 y Fm(2)99 1207 y Fs(\))g(:)p Fd(,)-109 1242 y(9)g Fs(i,)h(j)g Fd(2)f(f)p Fs(1,)f Fe(:)f(:)g(:)f Fs(,)k(n)p Fd(g)p Fs(:)24 b(i)9 b Fd(\024)g Fs(j)f Fd(^)g Fs(\(i)h Fd(6)p Ff(=)f Fs(1)g Fd(_)g Fs(j)h Fd(6)p Ff(=)f Fs(n\))-100 1278 y Fd(^)g Fs(\(\(r)-35 1283 y Fi(i)-14 1278 y Fe(:)e(:)g(:)f Fs(r)44 1283 y Fi(j)61 1278 y Fs(\))j(=)g(\(s)131 1283 y Fm(1)154 1278 y Fe(:)d(:)h(:)g Fs(s)214 1282 y Fi(m)243 1278 y Fs(\)\))-100 1314 y Fd(^)i Fs(\(\(domain)f(\(r)84 1319 y Fm(1)98 1314 y Fs(\))i Fe(isa)165 1320 y Fj(F)191 1302 y(\003)218 1314 y Fs(domain)d(\(s)349 1319 y Fm(1)364 1314 y Fs(\)\))i Fd(_)g Fs(\(domain)f(\(s)569 1319 y Fm(1)584 1314 y Fs(\))h Fe(isa)650 1320 y Fj(F)677 1302 y(\003)703 1314 y Fs(domain)f(\(r)833 1319 y Fm(1)847 1314 y Fs(\)\)\))-100 1349 y Fd(^)h Fs(\(\(range)f(\(r)58 1353 y Fi(n)79 1349 y Fs(\))h Fe(isa)145 1355 y Fj(F)172 1338 y(\003)198 1349 y Fs(range)f(\(s)304 1353 y Fi(m)334 1349 y Fs(\)\))h Fd(_)g Fs(\(range)f(\(s)513 1353 y Fi(m)542 1349 y Fs(\))i Fe(isa)609 1355 y Fj(F)635 1338 y(\003)662 1349 y Fs(range)e(\(r)766 1353 y Fi(n)787 1349 y Fs(\)\)\))p 895 1373 V -125 1375 1022 2 v -125 1461 a Fq(Accordingly)n(,)f(path)g (length)g(considerations)f(can)o(not)h(be)f(applied)h(to)g(the)g(p)o (aths)-125 1507 y Fk(p)-106 1511 y Fm(1)-77 1507 y Fq(=)14 b(\()p Fp(has\255centr)o(al\255unit)28 b(has\255motherboar)n(d)d (has\255cpu)p Fq(\))12 b(and)h Fk(p)756 1511 y Fm(2)785 1507 y Fq(=)h(\()p Fp(has\255)-125 1553 y(centr)o(al\255unit)23 b(has\255motherboar)n(d)p Fq(\))5 b(\226)i(both)g(being)g (well\255formed)h(conceptual)-125 1598 y(paths)f(from)i(N)p Fn(O)o(TEBOOK)e Fq(to)h(P)p Fn(R)o(ODUCT)p Fq(.)f(Although)g Fk(p)585 1602 y Fm(2)608 1598 y Fq(is)h(shorter)g(than)g Fk(p)845 1602 y Fm(1)868 1598 y Fq(in)-125 1644 y(the)j(absolute)f (sense)f(\(counting)i(role)g(chains)f(or)h(concept)f(nodes\),)g(it)i (is)f(not)-125 1689 y(shorter)c(in)g(the)f(relati)o(v)o(e)h(sense)e (speci\002ed)t(abo)o(v)o(e)h(and,)g(thus,)g(not)h(presumed)e(to)-125 1735 y(e)o(xpress)h(a)i(stronger)e(conceptual)g(link)h(\()p Fp(r)o(ange)g(\(has\255cpu\))f Fq(=)i(CPU)f(and)f Fp(r)o(ange)-125 1781 y(\(has\255motherboar)o(d\))12 b Fq(=)i(M)p Fn(O)o(THERBO)o(ARD)p Fq(;)f(hence,)g(the)h(last)h(constraint)f(in)-125 1826 y(T)m(able)c(2)h(is)f(violated\).)h(In)g(contrast,)f(the)h(inclusion)e (criterion)i(is)g(applicable)-125 1872 y(to)g(the)f(paths)f Fk(p)79 1876 y Fm(1)105 1872 y Fq(=)h(\()p Fp(has\255accumulator)18 b(price\255dm\255pair)p Fq(\))10 b(and)f Fk(p)738 1876 y Fm(2)763 1872 y Fq(=)i(\()p Fp(price\255)-125 1918 y(dm\255pair)p Fq(\))j(both)g(leading)e(from)j(N)p Fn(O)o(TEBOOK)e Fq(to)h(P)p Fn(RICE)p Fq(;)g(we)f(re)o(gard)h Fk(p)837 1922 y Fm(1)866 1918 y Fq(as)-125 1963 y(being)8 b(conceptually)e (weaker)h(than)h Fk(p)374 1967 y Fm(2)397 1963 y Fq(gi)o(v)o(en)g(the)g (constraint)g(from)h(T)m(able)f(2.)-125 2009 y Fr(Conceptual)g(Path)g (Patter)o(ns.)g Fq(Finally)n(,)h(we)f(introduce)g(a)g(purely)h (empirical)-125 2055 y(criterion)i(which)d(marks)h(certain)g(paths)g (as)f(being)h(preferred)g(o)o(v)o(er)h(others)f(in)-125 2100 y(terms)h(of)g(commonsense)c(semantic)j(plausibility)n(.)g(Based)f (on)h(introspecti)o(v)o(e)-125 2146 y(analyses)g(of)i(approximately)f (60)g(product)g(re)o(vie)o(ws)g(from)i(the)e(information)-125 2192 y(technology)e(domain)h(we)g(performed,)g(and)f(e)o(vidences)f (reported)i(from)h(se)o(v\255)-125 2237 y(eral)g(\(psycho\)linguistic)e (studies)g(\(e.g.,)i([1]\))g(,)g(we)e(stipulate)h(certain)g(prede\255) -125 2283 y(\002ned)e Fp(path)g(patterns)p Fq(.)g(From)h(those)e (general)h(path)g(patterns)h(and)e(by)i(virtue)g(of)-125 2329 y(the)13 b(hierarchical)f(or)o(ganization)g(of)h(conceptual)d (relations,)j(concrete)e(con\255)-125 2374 y(ceptual)16 b(role)h(chains)e(can)g(be)h(deri)o(v)o(ed)g(by)g(a)g(simple)g(pattern) h(matching)-125 2420 y(algorithm.)9 b(These)e(path)g(patterns)h(are)g (used)e(to)j(distinguish)e(between)g(a)g(sub\255)-125 2466 y(set)h Fl(P)j Fq(of)d(all)g(types)e(of)i(well\255formed)h(paths,) e(which)g(is)h(labeled)f Fp(\223plausible\224)p Fq(,)-125 2511 y(another)j(subset)e Fl(M)i Fq(which)f(is)h(labeled)f Fp(\223metonymic\224)p Fq(,)g(and)g(all)h(remaining)-125 2557 y(paths)f(which)f(are)h(labeled)g Fp(\223implausible\224)p Fq(.)-83 2603 y Fr(Plausible)f(Paths.)g Fq(An)g(important)h(assessment) d(criterion)j(for)g(character)o(\255)-125 2648 y(izing)j(relation)g (chains)e(as)h(plausible)g(ones)g(\(forming)h(the)g(set)f Fl(P)s Fq(\))h(is)g(that)g(a)-125 2694 y(plausible)d(role)i(chain)e (can)g(always)f(be)h(treated)h(as)f(a)h(single)f(relation.)i(Thus,)-125 2740 y(plausible)e(paths)g(pro)o(vide)g(a)h(handle)e(for)j(coping)d (with)i(the)g(notorious)f(prob\255)-125 2785 y(lem)h(of)g(granularity)f (in)h(kno)o(wledge)d(bases.)h(All)i(paths)f(of)g(unit)h(length)f Fp(1)g Fq(are)971 26 y(included)f(in)g Fl(P)s Fq(,)h(as)f(the)o(y)h (are)f(\223plausible\224,)f(by)h(de\002nition)g(\(the)o(y)h(refer)g(to) g(the)971 71 y(conceptual)e(roles)h(directly)g(associated)e(with)j(a)f (concept)f(de\002nition\).)h(In)h(ad\255)971 117 y(dition,)g(we)e (incorporate)g(empirical)g(observ)o(ations)f(about)g(the)i(transiti)o (vity)g(of)971 163 y(relations,)i Fp(part\255whole)e Fq(relations)h(in)g(particular)o(,)g(made)g(by)f(Chaf)o(\002n)h([1])h (and)971 208 y(W)o(inston)h Fp(et)h(al.)g Fq([22].)g(In)g(these)f (studies)f(se)o(v)o(eral)h(subtypes)f(of)i Fp(part\255whole)971 254 y Fq(relations)j(are)g(distinguished,)e(e.g.,)j(inte)o(gral)f (object\255component)e(\(corre\255)971 300 y(sponding)k(to)h(what)g(we) g(call)g Fp(has\255physical\255part)p Fq(\),)e(collection\255member)o (,)971 345 y(mass\255portion,)7 b(process\255phase,)t(e)o(v)o (ent\255feature)g(and)g(area\255place.)f(The)h(claim)971 391 y(is)12 b(made)e(that)h(an)o(y)g(of)g(these)f Fp(sub)p Fq(relations)g(are)h(transiti)o(v)o(e,)h(while)f(the)g(most)971 436 y(general)f Fp(part\255whole)f Fq(relation)i(usually)e(is)h(not.)h (In)f(other)h(words,)e(a)h(relation)971 482 y(chain)h(containing)f (only)h(relations)g(of)g(one)g(of)g(the)g(abo)o(v)o(e\255mentioned)f (sub\255)971 528 y(types)d(is)g(again)g Fp(a)g(r)o(elation)g(of)h(the)f (same)f(subtype)p Fq(,)g(whereas)h(a)g(relation)h(chain)971 573 y(containing)i(se)o(v)o(eral)g(dif)o(ferent)i(types)e(of)h Fp(part\255whole)f Fq(relations)h(is,)g(in)g(gen\255)971 619 y(eral,)g(not)e(reasonable)f(an)o(y)h(more.)h(F)o(ollo)o(wing)g (this)g(ar)o(gument,)g(we)f(ha)o(v)o(e)g(in\255)971 665 y(cluded)f(the)h(path)f(patterns)g(\()p Fp(has\255physical\255part)1613 649 y Fj(\003)1629 665 y Fq(\),)i(\()p Fp(collection\255member)1954 649 y Fj(\003)1971 665 y Fq(\),)971 710 y(\()p Fp(mass\255portion)1182 695 y Fj(\003)1199 710 y Fq(\),)20 b(\()p Fp(pr)n(ocess\255phase)1467 695 y Fj(\003)1482 710 y Fq(\),)g(\()p Fp(e)o(vent\255featur)o(e)1732 695 y Fj(\003)1748 710 y Fq(\),)g(\()p Fp(ar)o(ea\255place)1964 695 y Fj(\003)1980 710 y Fq(\))971 756 y(and)7 b(the)h(corresponding)e (in)o(v)o(erses)g(like)i(\()p Fp(physical\255part\255of)1755 740 y Fj(\003)1772 756 y Fq(\))h(in)f Fl(P)s Fq(.)g(W)m(e)g(will)971 802 y(refer)g(to)g(the)f(\002rst)g(six)g(of)g(these)f(patterns)h(as)g Fp(tr)o(ansitive)f(part\255whole)h(patterns)p Fq(,)971 847 y(in)k(short)g Fl(T)e Fq(,)j(and)d(to)i(the)g(in)o(v)o(erse)f (patterns)g(as)g Fl(T)1627 832 y Fj(\000)p Fm(1)1666 847 y Fq(.)h(Apart)g(from)g(the)g(tran\255)971 893 y(siti)o(v)o(e)h (part\255whole)g(relations)f(we)g(ha)o(v)o(e)g(included)f(\()p Fp(spatial)h(containment)1963 877 y Fj(\003)1980 893 y Fq(\))971 939 y(and)e(\()p Fp(connnection)1232 923 y Fj(\003)1248 939 y Fq(\))g(in)p Fl(P)k Fq(\(cf.)d([12]\).)1013 984 y Fr(Metonymic)c(Paths.)g Fq(F)o(ollo)o(wing)g(established)g(c)o (lassi\002c)o(ations)g(o)o(f)g(meton\255)971 1030 y(ymies)k(\(cf.)h ([14,)f(5]\),)h(we)f(ha)o(v)o(e)f(included)g(the)h(analysis)f(of)h Fp(whole\255for)o(\255part)p Fq(,)971 1076 y Fp(part\255for)o (\255whole)p Fq(,)f(and)e Fp(pr)n(oducer)o(\255for)o(\255pr)n(oduct)f Fq(meton)o(ymies)h(in)i(the)f(system.)971 1121 y(In)13 b(order)e(to)i(determine)e(path)g(patterns)h(corresponding)e(to)i (these)e(types)h(of)971 1167 y(meton)o(ymies)e(consider)g(the)g (conceptual)f(link)h(between)g(an)g(instance)f(of)i(the)971 1213 y(concept)h(C)1125 1217 y Fm(1)1152 1213 y Fq(and)h(an)g(instance) f(of)h(the)h(concept)d(C)1657 1217 y Fm(3)1672 1213 y Fq(,)j(which)f(characterizes)971 1258 y(a)h(meton)o(ymy)g(and)f(thus)g (stands)g(for)h(another)g(instance)e(of)j(a)e(concept)g(C)1969 1262 y Fm(2)1983 1258 y Fq(.)971 1304 y(A)h(corresponding)e (well\255formed)j(conceptual)d(path)i Fk(p)g Fq(=)g Fh(\()p Fk(r)1787 1308 y Fm(1)1808 1304 y Fk(:)6 b(:)g(:)g(r)1876 1308 y Fi(n)1898 1304 y Fh(\))13 b Fq(with)971 1350 y Fk(n)i Fl(2)g Fk(I)-10 b(N)t Fq(,)12 b Fk(n)j(>)g Fq(1,)e(and)e Fk(r)1320 1354 y Fi(i)1348 1350 y Fl(2)k(R)d Fp(\(i)h(=)f(1,...,n\))i Fq(must,)f(\002rst,)f(link)h(C)1885 1354 y Fm(1)1912 1350 y Fq(to)f(C)1978 1354 y Fm(2)971 1395 y Fq(via)e Fk(p)1046 1399 y Fm(1)1071 1395 y Fq(=)h Fh(\()p Fk(r)1135 1399 y Fm(1)1156 1395 y Fk(:)6 b(:)g(:)g(r)1224 1399 y Fi(j)q Fj(\000)p Fm(1)1277 1395 y Fh(\))k Fq(for)h(some)e Fk(j)j Fl(2)e(f)p Fq(2,...,n)p Fl(g)p Fq(.)i(C)1676 1399 y Fm(2)1701 1395 y Fq(is)e(then)g(linked)f(to)h(C)1978 1399 y Fm(3)971 1441 y Fq(via)j Fk(p)1049 1445 y Fm(2)1078 1441 y Fq(=)g Fh(\()p Fk(r)1144 1445 y Fi(j)1167 1441 y Fk(:)6 b(:)g(:)g(r)1235 1445 y Fi(n)1257 1441 y Fh(\))p Fq(.)13 b(W)m(e)h(restrict)g(the)f(\002rst)g(link)h Fk(p)1695 1445 y Fm(1)1723 1441 y Fq(to)f(plausible)g(paths)971 1487 y(in)g(order)f(to)h(pro)o(vide)f(reasonable)e(meton)o(ymic)i (chains)f(only)n(.)h(The)g(second)971 1532 y(link)h Fk(p)1061 1536 y Fm(2)1089 1532 y Fq(must)g(e)o(xpress)e(one)h(of)h(the)f(meton)o (ymic)h(relations)f Fl(MS)k Fq(=)d Fl(f)p Fp(has\255)971 1578 y(part,)j(part\255of,)f(pr)n(oduced\255by)p Fl(g)p Fq(,)e(depending)g(on)i(the)h(speci\002c)d(meton)o(ymy)971 1624 y(to)g(be)f(handled)1181 1608 y Fm(2)1192 1624 y Fq(.)26 b(F)o(or)13 b(a)f Fp(pr)n(oducer)o(\255for)o(\255pr)n(oduct)e Fq(meton)o(ymy)n(,)i(e.g.,)h Fk(j)i Fq(=)d Fk(n)971 1669 y Fq(and)d Fk(r)1052 1673 y Fi(n)1083 1669 y Fq(=)h Fp(pr)n (oduced\255by)d Fq(must)i(hold.)h(F)o(or)g(a)f Fp(part\255for)o (\255whole)g Fq(or)h Fp(whole\255for)o(\255)971 1715 y(part)h Fq(meton)o(ymy)n(,)g Fk(j)16 b(<)e(n)e Fq(may)f(be)g(possible) g(as)g(all)h(paths)e(in)i Fl(T)22 b Fq(and)10 b Fl(T)1954 1699 y Fj(\000)p Fm(1)971 1761 y Fq(\(e.g.,)i(\()p Fp (has\255physical\255part)1336 1745 y Fj(\003)1352 1761 y Fq(\)\))g(also)e(e)o(xpress)f(a)i(single)f Fp(has\255part)g Fq(or)h Fp(part\255of)971 1806 y Fq(relation)c(\(see)e(the)h(e)o (xplanations)f(of)i(plausible)e(paths)g(abo)o(v)o(e\).)h(F)o(or)h (notational)971 1852 y(con)o(v)o(enience,)j(we)i(no)o(w)g(consider)f (the)h(paths)f(in)i Fl(T)22 b Fq(and)11 b Fl(T)1780 1836 y Fj(\000)p Fm(1)1831 1852 y Fq(as)g(a)h(single)971 1898 y(relation)k(so)g(that)g(we)f(may)h(write)g(\()p Fp (has\255physical\255part)1733 1882 y Fj(\003)1749 1898 y Fq(\))h Fp(isa)1822 1902 y Fj(R)1866 1898 y Fp(has\255part)971 1943 y Fq(or)d(\()p Fp(e)o(vent\255featur)o(e)1225 1927 y Fj(\003)1242 1943 y Fq(\))g Fl(2)f(MS)s Fq(.)h(Thus,)f(we)g(may)g (restrict)i(the)e(abo)o(v)o(e)g(cases)971 1989 y(of)h(well\255formed)f (meton)o(ymic)g(paths)f(to)h(the)g(pattern)g(in)g(T)m(able)f(3.)i (Special)971 2035 y(path)i(patterns)f(for)i(speci\002c)e(meton)o(ymies) g(and)g(meton)o(ymic)h(chains)f(can)971 2080 y(be)d(deri)o(v)o(ed)g (from)i(this)e(general)g(pattern)g(by)g(either)h(instantiating)f (speci\002c)971 2126 y(meton)o(ymic)d(relations)g(or)h(by)e(a)h (recursi)o(v)o(e)g(application)f(of)i(the)f(predicate.)1238 2201 y Fg(T)m(able)g(3.)33 b Fs(Metonymic)6 b(Path)i(Patterns)p 1016 2219 923 2 v 1016 2390 2 172 v 1072 2256 a(Metonymic\255Path)e(\() p Ff(\()p Fe(r)1344 2261 y Fm(1)1364 2256 y Fe(:)f(:)h(:)g(r)1427 2260 y Fi(n)1448 2256 y Ff(\))p Fs(\))i(:)p Fd(,)1138 2292 y Fs(\()p Fe(r)1165 2297 y Fm(1)1186 2292 y Fe(:)d(:)h(:)g(r)1249 2296 y Fi(n)1270 2292 y Fs(\))12 b Fe(=)-22 b Fd(2)8 b(P)1147 2328 y(^)g Fs(\(\()p Fe(n)i(>)g Fs(1)e Fd(^)g Ff(\()p Fe(r)1356 2333 y Fm(1)1370 2328 y Fe(;)e(r)1402 2333 y Fm(2)1416 2328 y Fe(;)g(:)g(:)f(:)h(;)g(r)1511 2333 y Fi(n)p Fj(\000)p Fm(1)1568 2328 y Ff(\))k Fd(2)f(P)i(^)d Fe(r)1709 2332 y Fi(n)1738 2328 y Fd(2)g(MS)s Fs(\))1163 2367 y Fd(_)g Fs(\()p Fe(n)i(>)h Fs(1)d Fd(^)f Ff(\()p Fe(r)1361 2372 y Fm(2)1376 2367 y Fe(;)e(r)1407 2372 y Fm(3)1422 2367 y Fe(;)g(:)h(:)g(:)f(;)h(r)1516 2371 y Fi(n)1537 2367 y Ff(\))k Fd(2)f(P)i(^)d Fe(r)1678 2372 y Fm(1)1700 2367 y Fd(2)g(MS)1797 2355 y Fj(\000)p Fm(1)1837 2367 y Fs(\)\))p 1938 2390 V 1016 2392 923 2 v 1013 2451 a Fq(The)g(markers)g Fp(\223plausible\224)p Fq(,)f Fp (\223metonymic\224)g Fq(and)h Fp(\223implausible\224)g Fq(are)g(\002\255)971 2497 y(nally)h(ranked)d(\(cf.)k(T)m(able)d(4\))i (according)e(to)h(their)h(inherent)f(le)o(v)o(el)h(of)f(concep\255)971 2543 y(tual)k(strength)f(denoted)g(by)g(the)g(relation)h(\223)p Fk(>)1581 2547 y Fi(str)1624 2543 y Fq(\224)g(\(conceptually)e Fp(str)n(onger)971 2588 y(than)p Fq(\).)p 971 2637 1022 4 v 971 2662 a Fm(2)998 2674 y Fs(If)j(the)f(direction)f(of)h(search)g (is)g(re)o(versed)f(\(searching)f(from)i(C)1761 2679 y Fm(3)1788 2674 y Fs(to)h(C)1849 2679 y Fm(1)1863 2674 y Fs(\))g(the)f(cor)o(\255)1000 2710 y(responding)7 b(in)o(verse)h (relations)h(must)g(be)f(considered.)g(W)m(e)i(refer)f(to)g(these)f(in) o(verse)1000 2750 y(relations)e(as)h Fd(MS)1221 2738 y Fj(\000)p Fm(1)1267 2750 y Fs(=)f Fd(f)p Fo(part\255of,)f (has\255part,)h(pr)o(oduces)p Fd(g)p Fs(.)t(This)g(list)h(of)g (metonymic)1000 2785 y(relations)h(is,)h(of)f(course,)f(incomplete)g (and)g(can)h(be)f(augmented)f(on)i(demand.)-125 2885 y Fr(Natural)h(Language)e(Pr)o(ocessing)553 b(573)448 b(U)n(.)10 b(Hahn,)f(K.)h(Markert)e(and)g(M.)i(Strube)p eop %%Page: 572 5 572 4 bop -18 133 a Fu(A)21 b(Conceptual)f(Reasoning)g(A)n(ppr)o(oach)f (to)h(T)-8 b(extual)20 b(Ellipsis)478 249 y Ft(Udo)12 b(Hahn,)g(Katja)f(Markert)h(and)g(Michael)g(Strube)1388 232 y Fs(1)-125 387 y Fr(Abstract.)26 b Fs(W)m(e)15 b(present)e(a)h (hybrid)f(text)g(understanding)f(methodology)f(for)j(the)-125 423 y(resolution)d(of)h(textual)f(ellipsis.)i(It)f(integrates)f (conceptual)f(criteria)i(\(based)f(on)g(the)-125 458 y(well\255formedness)f(and)h(conceptual)e(strength)h(of)h(role)g (chains)g(in)g(a)g(terminological)-125 494 y(kno)o(wledge)5 b(base\))g(and)h(functional)f(constraints)g(re\003ecting)h(the)g (utterances')f(informa\255)-125 530 y(tion)10 b(structure)f(\(based)f (on)h(the)g(distinction)g(between)f(context\255bound)e(and)i(unbound) -125 565 y(discourse)h(elements\).)h(The)f(methodological)f(frame)o (work)h(for)h(text)f(ellipsis)h(resolu\255)-125 601 y(tion)e(is)h(the)f (centering)f(model)g(that)h(has)g(been)f(adapted)f(to)i(these)g (constraints.)-125 686 y Ft(1)46 b(Intr)o(oduction)-125 742 y Fq(T)m(e)o(xtual)14 b(forms)h(of)f(ellipsis)g(and)f(anaphora)f (are)h(a)h(challenging)e(issue)h(for)-125 788 y(the)g(design)e(of)i (parsers)f(for)i(te)o(xt)f(understanding)d(systems,)i(since)g(lacking) -125 833 y(recognition)i(facilities)g(either)g(result)g(in)g (referentially)h(incoherent)e(or)h(in\255)-125 879 y(v)o(alid)9 b(te)o(xt)f(kno)o(wledge)f(representations.)g(At)h(the)g(conceptual)f (le)o(v)o(el,)i(te)o(xtual)-125 925 y(ellipsis)14 b(\(also)f(called)f (functional)h(or)h(partial)g(anaphora\))d(relates)i(a)g(quasi\255)-125 970 y(anaphoric)c(e)o(xpression)g(to)i(its)g(e)o(xtrasentential)f (antecedent)e(by)i(conceptual)-125 1016 y(attrib)o(utes)h(\(or)f (roles\))g(associated)d(with)k(that)f(antecedent)d(\(see,)j(e.g.,)g (the)f(re\255)-125 1062 y(lation)h(between)f Fp(\223Ladezeit\224)f(\(c) o(har)o(ge)f(time\))k Fq(and)e Fp(\223Akku\224)f(\(accumulator\))-125 1107 y Fq(in)14 b(\(3\))g(and)e(\(2\)\).)j(Thus,)d(it)i(complements)e (the)g(phenomenon)f(of)i(nominal)-125 1153 y(anaphora,)c(where)g(an)h (anaphoric)e(e)o(xpression)g(is)i(related)g(to)g(its)h(antecedent)-125 1199 y(in)d(terms)f(of)g(conceptual)e(generalization)h(\(as,)h(e.g.,)g Fp(\223Rec)o(hner\224)e(\(computer\))-125 1244 y Fq(refers)k(to)g Fp(\223316L)o(T\224)p Fq(,)f(a)g(particular)h(notebook,)f(in)h(\(2\))g (and)f(\(1\)\).)i(The)e(resolu\255)-125 1290 y(tion)k(of)f(te)o (xt\255le)o(v)o(el)h(nominal)e(\(and)h(pronominal\))f(anaphora)f (contrib)o(utes)i(to)-125 1336 y(the)c(construction)f(of)i (referentially)g(v)o(alid)f(te)o(xt)h(kno)o(wledge)d(bases,)h(while)h (the)-125 1381 y(resolution)i(of)g(te)o(xtual)g(ellipsis)g(yields)g (referentially)g(coherent)f(te)o(xt)i(kno)o(wl\255)-125 1427 y(edge)j(bases.)e(Both)j(phenomena)d(tend)i(to)g(interact,)h(as)f (e)o(videnced)e(by)i(the)-125 1473 y(e)o(xample)f(belo)o(w)n(.)f Fp(\223Akku\224)g(\(accumulator\))g Fq(in)h(\(2\))h(is)g(a)f(nominal)f (anaphor)-125 1518 y(referring)6 b(to)g Fp(\223Nic)o (kel\255Metall\255Hydride\255Akku\224)g(\(nic)o (kel\255metal\255hydride)g(ac)o(\255)-125 1564 y(cumulator\))h Fq(in)h(\(1\),)g(which,)g(when)e(resolv)o(ed,)h(pro)o(vides)g(the)g (proper)g(referent)-125 1610 y(for)j(relating)g Fp(\223Ladezeit\224)d (\(c)o(har)o(ge)h(time\))i Fq(in)f(\(3\))h(to)f(it.)-129 1673 y Fs(1.)21 b(Der)8 b Fo(316L)o(T)g Fs(wird)h(mit)f(einem)g Fo(Nic)o(kel\255Metall\255Hydride\255Akku)e Fs(best)s(\250)-14 b(uckt.)-83 1708 y(\(The)8 b Fo(316L)o(T)g Fs(is)h(\226)f(with)g(a)g Fo(nic)o(kel\255metal\255hydride)e(accumulator)g Fs(\226)i(equipped.\)) -129 1744 y(2.)21 b(Der)9 b Fo(Rechner)e Fs(wird)j(durch)e(diesen)g (neuartigen)f Fo(Akku)i Fs(f)s(\250)-14 b(ur)9 b(4)g(Stunden)f(mit)h (Strom)-83 1780 y(versor)o(gt.)-83 1816 y(\(The)f Fo(computer)f Fs(is)i(\226)f(because)e(of)j(this)f(ne)o(w)g(type)g(of)g Fo(accumulator)e Fs(\226)j(for)f(4)g(hours)-83 1851 y(\226)g(with)g(po) o(wer)g(\226)g(provided.\))-129 1887 y(3.)21 b(Dar)s(\250)-14 b(uberhinaus)6 b(ist)i(die)g Fo(Ladezeit)g Fs(mit)h(1,5)f(Stunden)f (sehr)g(kurz.)-83 1923 y(\(Also)h(\226)g(is)g(\226)g(the)g Fo(char)o(ge)e(time)i Fs(of)g(1.5)g(hours)f(quite)h(short.\))-125 1996 y Fq(In)f(the)f(case)f(of)h(te)o(xtual)h(ellipsis,)g(the)f (missing)f(conceptual)g(link)h(between)f(two)-125 2041 y(discourse)j(elements)g(occurring)g(in)h(adjacent)f(utterances)f(must) i(be)f(inferred)-125 2087 y(in)16 b(order)g(to)g(establish)f(the)g (local)h(coherence)d(of)j(the)g(discourse)d(\(for)k(an)-125 2133 y(early)9 b(statement)f(of)h(that)g(idea,)f(cf.)h([3]\).)h(In)f (sentence)e(\(3\),)i(e.g.,)g Fp(\223Ladezeit\224)-125 2178 y(\(c)o(har)o(ge)j(time\))i Fq(must)g(be)f(linked)g(up)g(with)h Fp(\223Akku\224)e(\(accumulator\))g Fq(from)-125 2224 y(sentence)f(\(2\).)j(This)e(relation)h(can)f(only)g(be)g(made)g(e)o (xplicit)h(if)h(conceptual)-125 2270 y(kno)o(wledge)5 b(about)h(the)g(domain,)g Fp(viz.)h Fq(the)f(relation)h Fp(c)o(har)o(ge\255time\255of)e Fq(between)-125 2315 y(the)k(concepts)f(C)p Fn(HARGE)p Fq(\255T)p Fn(IME)g Fq(and)g(A)o Fn(CCUMULA)m(T)o(OR)p Fq(,)g(is)h(a)o(v)o(ailable.)-83 2361 y(The)g(solution)g(we)g(propose)f(is)i(embedded)d(within)j(the)g (centering)e(model)-125 2407 y([6)q(],)h(in)f(which)g(te)o(xtual)g (ellipsis)g(has)f(only)h(been)f(gi)o(v)o(en)h(an)f(insuf)o(\002cient)h (treat\255)-125 2452 y(ment)e(so)g(far)n(.)h(Our)f(approach)t(combines) f(domain)g(and)g(discourse)g(kno)o(wledge)-125 2498 y(as)j(well)i(as)e (results)g(from)h(the)g(functional)f(interpretation)h(of)g(the)g (utterances.)p -125 2538 1022 4 v -125 2564 a Fm(1)-102 2575 y Fs(Freib)o(ur)o(g)f(Uni)o(versity)n(,)e(CLIF)j(\226)e (Computational)g(Linguistics)g(Lab,)h(Europaplatz)e(1,)-95 2611 y(D\25579085)g(Freib)o(ur)o(g,)j(Germany)23 b([http://www)n (.coling.uni\255freib)o(ur)o(g.de])971 387 y Fq(On)8 b(the)g(one)f(hand,)g(language\255independe)o(nt)f(conceptual)g (criteria)j(are)e(based)971 432 y(on)12 b(the)g(well\255formedness)f (and)g(conceptual)f(strength)i(of)h(role)f(chains)f(in)h(a)971 478 y(terminological)h(kno)o(wledge)d(base.)i(On)g(the)g(other)h(hand,) e(we)h(incorporate)971 524 y(language\255depende)o(nt)e(information)j (structure)g(constraints)f(re\003ecting)g(the)971 569 y(conte)o(xt\255boundedness)t(or)7 b(unboundedne)o(ss)t(of)g(discourse) f(elements)g(within)971 615 y(the)j(considered)f(utterances.)971 729 y Ft(2)46 b(Constraints)12 b(on)f(Conceptual)i(Linkage)971 781 y Fq(In)7 b(this)g(section,)f(we)g(will)i(introduce)e(formal)i(and) d(heuristic)i(criteria)g(to)g(deter)o(\255)971 826 y(mine)h(conceptual) e(links,)i(thus)f(clarifying)h(the)g(notions)f(of)h Fp (well\255formedness)971 872 y Fq(and)f Fp(str)o(ength)f Fq(of)h(conceptual)f(chains)g(underlying)g(the)i(resolution)f(of)g(te)o (xtual)971 918 y(ellipses.)i(W)m(e)g(assume)f(the)h(follo)o(wing)g(con) o(v)o(entions)e(to)i(hold)g(in)h(our)f(kno)o(wl\255)971 963 y(edge)c(base:)h(The)f(concept)g(hierarchy)g(consists)g(of)h(a)g (set)g(of)h(concept)t(names)e Fl(F)971 1009 y Fq(=)12 b Fl(f)p Fq(C)p Fn(OMPUTER)p Fq(\255S)p Fn(YSTEM)p Fq(,)e(N)p Fn(O)o(TEBOOK)p Fq(,)h(A)o Fn(CCUMULA)m(T)o(OR)p Fq(,...)p Fl(g)g Fq(and)f(a)h(sub\255)971 1055 y(class)j(relation)i Fk(isa)1240 1059 y Fj(F)1282 1055 y Fq(=)f Fl(f)p Fq(\(N)p Fn(O)o(TEBOOK)p Fq(,)g(C)p Fn(OMPUTER)p Fq(\255S)p Fn(YSTEM)p Fq(\),)g(\(N)p Fn(IMH)p Fq(\255)971 1100 y(A)o Fn(CCUMULA)m(T)o(OR)p Fq(,)c(A)o Fn(CCUMULA)m(T)o(OR)p Fq(\),...)p Fl(g)g(\032)j(F)f(\002)d (F)t Fq(.)i(The)e(set)i(of)f(relation)971 1146 y(names)d Fl(R)h Fq(=)g Fl(f)p Fp(has\255physical\255part,)e(has\255accumulator)l (,)g(c)o(har)o(ge\255time\255of,...)p Fl(g)971 1192 y Fq(contains)f(the)g(labels)g(of)h(all)g(possible)e(conceptual)g(roles.) i(The)f(roles)g(are)h(or)o(ga\255)971 1237 y(nized)f(into)i(a)f (hierarchy)f(by)g(the)h(relation)h Fk(isa)1567 1241 y Fj(R)1603 1237 y Fq(=)f Fl(f)p Fp(\(has\255accumulator)l(,)e(has\255) 971 1283 y(physical\255part\),)h(\(c)o(har)o(ge\255time\255of,)h(pr)n (operty\255of\),...)p Fl(g)g(\032)k(R)s(\002)s(R)p Fq(.)c(Through\255) 971 1329 y(out)i(the)g(paper)o(,)f(we)h(assume)f(a)g(terminological)i (kno)o(wledge)d(representation)971 1374 y(and)i(reasoning)e(frame)o (work)i(\(cf.)h([23])g(for)g(a)f(surv)o(e)o(y\).)1013 1420 y(F)o(or)i(the)f(identi\002cation)h(and)e(e)o(v)o(aluation)h(of)h (suitable)f(conceptual)f(links,)971 1466 y(the)d(ellipsis)g(resolution) g(mechanism)g(is)g(supplied)g(with)g(a)g Fp(pa)o(th)g(\002nde)o(r)p Fq(,)g(which)971 1511 y(performs)k(an)f(e)o(xtensi)o(v)o(e)f(search)g (in)i(the)f(domain)g(kno)o(wledge)e(base)h(looking)971 1557 y(for)h(\223well\255formed\224)f(paths)f(between)f(two)i (concepts,)e(and)h(a)g Fp(path)h(e)o(valuator)p Fq(,)971 1603 y(which)j(selects)f(the)g(\223strongests\224)f(of)i(the)g(ensuing) e(paths.)i(The)f(path)g(\002nder)971 1648 y(applies)f(two)g(basic)f (criteria:)1013 1694 y(Gi)o(v)o(en)14 b(two)h(concepts)d Fk(x;)6 b(y)20 b Fl(2)e(F)t Fq(,)c(a)h(series)e(of)i(conceptual)e (relations)971 1740 y Fk(r)988 1744 y Fi(i)1017 1740 y Fl(2)h(R)e Fp(\(i)h(=)g(1,...,n\))g Fq(and)f(concepts)e Fk(c)1510 1744 y Fi(j)1540 1740 y Fl(2)15 b(F)g Fp(\(j)e(=)g(0,...,n\)) g Fh(\()p Fk(n)i Fl(2)g Fk(I)-10 b(N)s Fh(\))13 b Fq(is)971 1785 y(admitted)6 b(as)g(a)g(conc)o(eptua)o(l)g(path)f(from)h Fk(x)g Fq(to)g Fk(y)t Fq(if)o(f)g(the)g(follo)o(wing)g Fp(connectivity)971 1831 y(condition)j Fq(holds:)973 1893 y Fl(\017)21 b Fk(r)1030 1897 y Fi(i)1052 1893 y Fq(is)8 b(a)f(\(possibly)h(inherited\))g(conceptual)e(role)i(of)h Fk(c)1701 1897 y Fi(i)p Fj(\000)p Fm(1)1758 1893 y Fq(with)g Fk(r)q(ang)q(e)p Fh(\()p Fk(r)1963 1897 y Fi(i)1978 1893 y Fh(\))1013 1939 y Fq(=)g Fk(c)1060 1943 y Fi(i)1082 1939 y Fq(for)h(all)g Fp(i)g(=)f(\(1,...,n\))p Fq(;)973 1984 y Fl(\017)21 b Fk(c)1030 1988 y Fm(0)1055 1984 y Fq(=)11 b Fk(x)g Fl(^)g Fq(\()g Fk(c)1197 1988 y Fi(n)1229 1984 y Fk(isa)1280 1988 y Fj(F)1307 1968 y(\003)1336 1984 y Fk(y)h Fl(_)f Fk(y)h(isa)1486 1988 y Fj(F)1513 1968 y(\003)1542 1984 y Fk(c)1559 1988 y Fi(n)1580 1984 y Fq(\),)g(where)e Fk(isa)1766 1988 y Fj(F)1793 1968 y(\003)1822 1984 y Fq(denotes)f(the)1013 2030 y(re\003e)o(xi)o(v)o(e)g (and)f(transiti)o(v)o(e)i(closure)e(of)i Fk(isa)1570 2034 y Fj(F)1597 2030 y Fq(.)971 2092 y(Note)i(that)f(no)g(conceptual)f (specialization)g(is)i(allo)o(wed)f(at)g(an)o(y)g(step)g(of)h(the)971 2138 y(search)e(e)o(xcept)h(of)h(the)f(end)g(point,)h(thus)f(reducing)f (the)i(comple)o(xity)f(of)h(the)971 2183 y(search.)g(In)i(the)f(follo)o (wing,)g(a)g Fp(connected)e(conceptual)g(path)i Fq(like)g(the)g(one)971 2229 y(abo)o(v)o(e)c(will)h(be)f(denoted)e(by)i Fh(\()p Fk(r)1387 2233 y Fm(1)1408 2229 y Fk(:)d(:)h(:)f(r)1477 2233 y Fi(n)1498 2229 y Fh(\))p Fq(.)1013 2275 y(Apart)j(from)h(being)e (connecti)o(v)o(e,)f(we)i(require)g(a)f(well\255formed)i(path)e(to)h (be)971 2320 y Fp(non\255cyclic)f Fq(\(cf.)i(T)m(able)f(1;)g Fk(r)1344 2305 y Fj(\000)p Fm(1)1393 2320 y Fq(denotes)e(the)i(in)o(v)o (erse)f(of)i(relation)f Fk(r)q Fq(\).)1265 2388 y Fg(T)m(able)f(1.)33 b Fs(Cyclic)8 b(Path)g(Criterion)p 971 2406 1022 2 v 971 2506 2 100 v 982 2443 a(Cyclic)h(\()p Ff(\()p Fe(r)1119 2448 y Fm(1)1139 2443 y Fe(:)c(:)h(:)g(r)1202 2447 y Fi(n)1223 2443 y Ff(\))p Fs(\))i(:)p Fd(,)1032 2483 y(9)g Fs(i,)h(j)g Fd(2)e(f)p Fs(1,)h Fe(:)e(:)g(:)f Fs(,)k(n)p Fd(g)p Fs(:)f Fe(i)g Fd(6)p Ff(=)h Fe(j)h Fd(^)e(9)g Fs(s)g Fd(2)i(R)p Fs(:)e(\(r)1566 2488 y Fi(i)1588 2483 y Fe(isa)1635 2489 y Fj(R)1663 2471 y(\003)1690 2483 y Fs(s\))g Fd(^)g Fs(\(r)1776 2488 y Fi(j)1800 2483 y Fe(isa)1847 2489 y Fj(R)1876 2471 y(\003)1902 2483 y Fs(s)1915 2471 y Fj(\000)p Fm(1)1954 2483 y Fs(\))p 1991 2506 V 971 2508 1022 2 v 1013 2565 a Fq(This)e(criterion)h(fa)o(v)o (ors)e(a)h Fp(unidir)o(ectional)f(sear)o(c)o(h)t Fq(in)h(the)g(kno)o (wledge)f(base.)971 2611 y(A)10 b(c)o(yclic)f(connected)e(conceptual)h (path)g(lacks)h(speci\002city)n(,)f(as)g(it)j(often)e(only)-114 2681 y Fs(c)-125 2682 y Fd(\015)g Fs(1996)e(U.)h(Hahn,)g(K.)g(Markert)f (and)h(M.)g(Strube)-125 2718 y(ECAI)h(96.)f Fo(12th)f(Eur)o(opean)f (Confer)o(ence)g(on)i(Arti\002cial)g(Intelligence)-125 2754 y Fs(Edited)g(by)g(W)m(.)h(W)m(ahlster)-125 2790 y(Published)f(in)g(1996)f(by)g(John)g(W)o(iley)h(&)g(Sons,)g(Ltd.)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF