%!PS-Adobe-2.0 %%Creator: dvipsk 5.58f Copyright 1986, 1994 Radical Eye Software %%Title: paper.dvi %%Pages: 12 %%PageOrder: Ascend %%BoundingBox: 0 0 596 842 %%DocumentPaperSizes: a4 %%EndComments %DVIPSCommandLine: dvips -o paper.ps paper.dvi %DVIPSParameters: dpi=300, compressed, comments removed %DVIPSSource: TeX output 1996.05.07:1130 %%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 TeXDict begin 39158280 55380996 1000 300 300 (paper.dvi) @start /Fa 3 84 df<1470EB01F0EB03C0EB0780EB0E005B5B5BA213F05BB3AC485AA3 485A48C7FC1206120E12385A12C012707E120E120612076C7E6C7EA36C7EB3AC7F1370A2 7F7F7FEB0780EB03C0EB01F0EB007014637B811F>26 D80 D<00E0141CB3AD00701438A26C1470A26C14E0001E1301390F8007C03907E01F803901FF FE0038007FF8EB1FE01E2A7E7F23>83 D E /Fb 1 49 df<1218A31230A31260A312C0A2 050B7E8B09>48 D E /Fc 4 53 df<121812F81218AA12FF080D7D8C0E>49 D<123EEA4180EA80C012C01200A2EA0180EA03001204EA08401230EA7F8012FF0A0D7E8C 0E>I<123E1241EA61801201EA0300121EEA0180EA00C0A212C0A2EA4180EA3E000A0D7E 8C0E>I<12035AA2120B12131223126312C3EAFFC0EA0300A3EA0FC00A0D7E8C0E>I E /Fd 6 116 df<1208A21200A41270129812B01230A21260126412681270060F7D8E0B> 105 D<13C013801300A41207EA19801211EA0300A41206A4128C12F00A137F8E0C>I112 DII<123E124312421270123C120612C212 84127808097D880E>I E /Fe 37 124 df12 D<127812FCA4127806067D850D>46 D48 D<1360EA01E0120F12FF12F31203B3A2387FFF80A2111B7D9A18>IIII<38380180383FFF005B5B5B13C00030C7FCA4EA31F8EA 361E38380F80EA3007000013C014E0A3127812F8A214C012F038600F8038381F00EA1FFE EA07F0131B7E9A18>I<137EEA03FF38078180380F03C0EA1E07123C387C03800078C7FC A212F813F8EAFB0E38FA0780EAFC0314C000F813E0A41278A214C0123CEB0780381E0F00 EA07FEEA03F8131B7E9A18>I<1260387FFFE0A214C01480A238E00300EAC0065B5BC65A A25B13E0A212015B1203A41207A66C5A131C7D9B18>III<1278 12FCA412781200A6127812FCA4127806127D910D>I<90381FE0209038FFF8E03803F80F 3807C003380F800148C7FC123E1560127E127C00FC1400A8007C1460127E123E15C07E39 0F8001803907C003003803F80E3800FFFCEB1FE01B1C7D9B22>67 DI76 D79 DI<007FB512E0A238781F81007013800060146000E0147000C014 30A400001400B03807FFFEA21C1C7E9B21>84 D97 D99 D101 D104 D<121E123FA4121EC7FC A6127FA2121FAEEAFFC0A20A1E7F9D0E>I<137813FCA413781300A6EA03FCA2EA007CB2 127012F8137813F0EA70E0EA1F800E26839D0F>I108 D<39FF0FC07E903831E18F3A1F40F20780D980FC13C0A2EB00F8AB3AFFE7FF3F F8A225127F9128>I<38FF0FC0EB31E0381F40F0EB80F8A21300AB38FFE7FFA218127F91 1B>II<38FF3F80EBE1E0381F80F0EB0078147C 143C143EA6143C147C1478EB80F0EBC1E0EB3F0090C7FCA6EAFFE0A2171A7F911B>I<38 03F060380F0CE0EA1E07EA3C03127C127812F8A61278127C123CEA1C07EA0E0FEA03F3EA 0003A6EB1FFCA2161A7E9119>III<1203A45AA25AA2EA3FFC12FF EA1F00A9130CA4EA0F08EA0798EA03F00E1A7F9913>I<38FF07F8A2EA1F00AC1301120F 380786FFEA01F818127F911B>I<38FFC1FCA2381F00601380000F13C0A23807C180A238 03E300A213F7EA01F613FE6C5AA21378A21330A25B1270EAF8E05BEAF9800073C7FC123E 161A7F9119>121 D123 D E /Ff 6 107 df0 D<1204A3EAC460EAF5E0EA3F80EA0E00EA3F80EAF5E0EAC460EA0400A30B0D7E8D 11>3 D<1203B1EA8304EAE31CEA7B78EA1FE0EA0FC0EA0780EA0300A27E0E1A7F9311> 35 D<1204120EA2121CA31238A212301270A21260A212C0A2070F7F8F0A>48 D<1303A21306A2130C1318A21330A2136013C0A2EA0180A2EA0300A212065AA25AA25A5A A25A1240101A7C9300>54 D<12C0B3AB021D7D950A>106 D E /Fg 45 122 df<903801F03C9038071C47010C13C7EC19C690381C0180140313181338A2EC07 00A20003B512F03900700700A3140EA213E0A35CA2EA01C0A35CA2EA0380A21430EB0070 A248136038C630E038E638C038CC3180D8781EC7FC2025819C19>11 D<14FE90380301801306EB0C03EB1C0191C7FC13181338A43803FFFE3800700EA35CA213 E0A25CA3EA01C01472A438038034141891C7FC90C8FCA25A12C612E65A12781925819C17 >I<903801FEE0EB0707130E010C13C0EB1C01A213189038380380A40003B51200380070 07A3140EA213E0A25CA3EA01C01439A43803801A140C91C7FC90C8FCA25A12C612E65A12 781B25819C18>I<13031306130813181330136013C0A2EA0180EA0300A21206A25AA212 1C1218A212381230A21270A21260A412E0A51260A51220123012107EA2102A7B9E11>40 D<1310A21308130C13041306A51307A51306A4130EA2130CA2131C1318A213381330A213 60A213C0A2EA0180EA0300A212065A5A121012605A102A809E11>I<1218123812781238 1208A21210A212201240A21280050C7D830D>44 DI<12301278 12F0126005047C830D>I<1304130C131813381378EA07B8EA0070A413E0A4EA01C0A4EA 0380A4EA0700A45AEAFFF00E1C7B9B15>49 D<133EEB4180EB80C0EA0100000213E0EA04 40A21208A3381081C0A238110380000E1300EA00065B5B136013800003C7FC1204481340 4813805AEB0100EA7F07EA43FEEA81FCEA8078131D7D9B15>I<131FEB60C01380380100 6012021340000413E0A3EB81C0EA030138000380EB070013FC131C1306A21307A41270EA E00E12805BEA40185BEA20E0EA1F80131D7D9B15>II<1206120FA212061200AA1230127812 F0126008127C910D>58 D<48B512F038003C00013813301520A35BA214081500495AA214 30EBFFF03801C020A439038040801400A2EC0100EA07005C14021406000E133CB512FC1C 1C7E9B1C>69 D<48B512F038003C00013813301520A35BA214081500495AA21430EBFFF0 3801C020A448485A91C7FCA348C8FCA45AEAFFF01C1C7E9B1B>I<3A01FFC3FF803A003C 00780001381370A4495BA449485AA390B5FC3901C00380A4484848C7FCA43807000EA448 131E39FFE1FFC0211C7E9B1F>72 DI<3801FFC038003C001338A45BA45BA4485AA4 38038002A31404EA0700140C14181438000E13F0B5FC171C7E9B1A>76 DI<3801FFFE39003C038090383801C0EC00 E0A3EB7001A315C0EBE0031580EC0700141C3801FFF001C0C7FCA3485AA448C8FCA45AEA FFE01B1C7E9B1C>80 D83 D<001FB512C0381C070138300E0000201480126012 405B1280A2000014005BA45BA45BA4485AA41203EA7FFE1A1C799B1E>I97 D<123F1207A2120EA45AA4EA39E0EA3A18EA3C0C12381270130EA3EAE01CA31318133813 301360EA60C0EA3180EA1E000F1D7C9C13>I<13F8EA0304120EEA1C0EEA181CEA300012 70A25AA51304EA60081310EA3060EA0F800F127C9113>II<13F8EA0704120CEA1802EA38041230EA7008EA7FF0EAE000A5EA6004 1308EA30101360EA0F800F127C9113>IIIII108 D<391C1E078039266318C0394683A0E0384703 C0008E1380A2120EA2391C0701C0A3EC0380D8380E1388A2EC0708151039701C03203930 0C01C01D127C9122>II<13F8EA030CEA0E06487E121812 3000701380A238E00700A3130EA25BEA60185BEA30E0EA0F8011127C9115>I<38038780 3804C860EBD03013E0EA09C014381201A238038070A31460380700E014C0EB0180EB8300 EA0E86137890C7FCA25AA45AB4FC151A809115>III< EA01F0EA0608120C131CEA1818EA1C00121F13C0EA0FF01207EA00781338EA603012E012 C0EA8060EA60C0EA1F000E127D9111>I<12035AA3120EA4EAFFE0EA1C00A35AA45AA4EA E080A2EAE100A2126612380B1A7C990E>I<381C0180EA2E03124EA2388E0700A2121CA2 EA380EA438301C80A3EA383C38184D00EA0F8611127C9116>II<381E 0183382703871247148338870701A2120EA2381C0E02A31404EA180C131C1408EA1C1E38 0C26303807C3C018127C911C>I<38038780380CC840380870E012103820E0C014001200 A2485AA4EA03811263EAE38212C5EA8584EA787813127E9113>I<381C0180EA2E03124E A2388E0700A2121CA2EA380EA4EA301CA3EA383CEA1878EA0FB8EA003813301370EAE060 5BEA81800043C7FC123C111A7C9114>I E /Fh 22 122 df<3807FFFCEB801C0003130C 13C01201EBE0081200EBF0001370A213301320EB401038018020EA020048136048134038 3001C0EA7FFFB5128016147E931A>6 D11 D<133C13C2EA01031202120413 02EA080613FCA21304EA1006A4EA200CA2EA30181310EA4860EA47C0EA4000A25AA4101A 7F9313>I<124012E012601220A31240A2128003097D820A>59 D<3807FFFC3800E01C38 01C00CA31408EA03811400138313FFEA0702A21408EB0010120EA214201460381C01E0B5 12C016147F9318>69 D<3907E01FC00000EB060038017004A21338A238021C08A2130EA2 486C5AA2EB0390A2380801E0A21300A20018134012FE1A147F931A>78 D97 D<123C120C5AA45AEA3380EA3C60EA3020EA6030A4EAC060A2EA40C0EA6080EA2300121E 0C147F930F>II<133C130C1318A41330EA07B0EA0C701210EA30601260A3EAC0C013C8 A21241EA62D0EA3C700E147E9311>I<1206120712061200A41238124CA2128C12981218 A212301232A21264A2123808147F930C>105 D<1330133813301300A4EA01C0EA0260EA 0430136012081200A213C0A4EA0180A4EA630012E312C612780D1A81930E>I<121E1206 5AA45A1338135C139CEA3118EA36001238EA3F80EA61C0EA60C8A3EAC0D013600E147F93 12>I<123C120C1218A41230A41260A412C012C8A312D0126006147F930A>I<3830F87C38 590C86384E0D06EA9C0EEA980C1218A248485A15801418A23960301900140E190D7F8C1D >II< EA0C78EA168CEA1304EA2606A21206A2EA0C0CA213081310EA1A20EA19C0EA1800A25AA3 12FC0F13818C11>112 DII<1207EA1880EA19C0EA3180EA3800121E7EEA0380124112 E1EAC1001282127C0A0D7E8C10>I120 DI E /Fi 24 111 df0 D<0040132000C01360006013C038300180 38180300EA0C066C5A6C5AEA01B0EA00E0A2EA01B0EA0318EA060C487E487E3830018038 6000C04813600040132013147A9320>2 D<1203A4EAC30CEAE31CEA7338EA1FE0EA0780 A2EA1FE0EA7338EAE31CEAC30CEA0300A40E127D9215>I14 D<90387FFF8048B5FCD80780C7FC000EC8FC12185AA25AA25AA71260A27EA27E120E6C7E 0001B512806C7E90C8FCA7007FB51280A219227D9920>18 D20 D<12C012F0123C120FEA03C0EA00F0133C130FEB03C0EB00F0143C140FEC0380EC0F 00143C14F0EB03C0010FC7FC133C13F0EA03C0000FC8FC123C127012C0C9FCA7007FB5FC B6128019227D9920>I<90387FFF800003B5FCD80780C7FC000CC8FC5A5AA25AA25AA812 60A27EA27E120E6C7E0001B512806C7E191A7D9620>26 D<13C0485AA348C9FCA212065A 121C1230B712F0A20030C9FC121C120C7E7EA26C7EA36C7E24167D942A>32 D<153081A381A281811680ED00C0B712F8A2C912C0ED0380160015065DA25DA35D25167E 942A>I<13C0B3A700C013C0EAF0C33838C700EA0CCCEA06D8EA03F06C5AA26C5AA31340 12257F9C15>35 D<1403A26E7E8114001560007FB512F0B67EC8120E81ED01E0ED0078ED 01E0ED0380ED06005DB612F86C5CC812605D4A5AA24AC7FCA225187E952A>41 D<01181330497FA2497FA2497F48B6FC4815800006C812C04815600038153800F0151E00 78153C001C15706C15E00003EC01806CB612006C5C9038C0000601605B6D5BA26D5BA227 187F952A>44 D50 D<1460A214C0A2EB0180 A3EB0300A21306A25BA25BA35BA25BA25BA2485AA248C7FCA31206A25AA25AA25AA35AA2 5A124013287A9D00>54 D<12C0A612E0A212C0A6030E7E9000>I57 D<1304130CEA03CCEA0C38EA1818EA301C133CEA70 3EEA60361366A2EAE067A213C7A3EAE187A3EAE307A312E6A3EA6606126CEA7C0EEA3C0C 1238EA1818EA1C30EA33C0EA3000A210237E9F15>59 D<0040130200C01306B20060130C A26C1318001C1370380F01E03803FF803800FE00171A7E981C>91 D<13FE3803FF80380F01E0381C00700030131848130CA2481306B200401302171A7E981C >I<133C13E0EA01C013801203AD13005A121C12F0121C12077E1380AD120113C0EA00E0 133C0E297D9E15>102 D<12F0121C12077E1380AD120113C0EA00E0133C13E0EA01C013 801203AD13005A121C12F00E297D9E15>I<12C0B3B3A502297B9E0C>106 D<12C0A21260A37EA37EA37EA37EA27EA3EA0180A3EA00C0A31360A21330A31318A3130C A31306A31303130110297E9E15>110 D E /Fj 38 123 df<48B512FE9038E0003E0000 140E6D13041370A213781338133C011C1300A2131E130E130F130613045B5B4913205B5B 48C71240000214C0120C0010EB018048130F007FB51200B6FC1F1C7E9B20>6 D<13F8EA030C380E0604EA1C07383803080030138800701390A200E013A0A214C01480A3 EA6007EB0B8838307190380F80E016127E911B>11 DI<3807 8010EA1FC0383FE020EA7FF038603040EAC0183880088012001304EB0500A21306A31304 A3130CA35BA45BA21320141B7F9115>I<1338137FEB87803801030090C7FC7FA27F1200 7FA2137013F8EA03B8EA063CEA0C1C121812381270A212E0A413181338EA6030EA70606C 5AEA0F80111E7F9D12>I21 D<007E1360000E13E0A3381C01C0A2EB03801400485A130E130C 5B485A5BEA71C00073C7FC12FC12F013127E9115>23 D<3801FFF85A120F381E1E00EA18 0EEA38061270A2EAE00EA3130C131C13185BEA60606C5A001FC7FC15127E9118>27 D<380FFFE05A5A3860C0001240485A12001201A348C7FCA35AA3120E120613127E9112> I<126012F0A2126004047C830C>58 D<126012F0A212701210A41220A212401280040C7C 830C>II<12 E01278121EEA0780EA01E0EA0078131EEB0780EB01E0EB0078141EEC0780A2EC1E001478 EB01E0EB0780011EC7FC1378EA01E0EA0780001EC8FC127812E019187D9520>62 D<48B512F038003C00013813301520A35BA214081500495AA21430EBFFF03801C020A448 485A91C7FCA348C8FCA45AEAFFF01C1C7E9B1B>70 D<3801FFE038003C001338A45BA45B A4485AA438038002A31404EA0700140C14181438000E13F0B5FC171C7E9B1C>76 D<39FFC00FF0391C00038015001402A25C5C121E000E5B143014205CA25C49C7FC120FEA 07025BA25BA25B5BEA03A013C05BA290C8FCA21C1D7D9B18>86 D97 D<123F1207A2120EA45AA4EA39E0EA3A30EA3C1812381270131CA3EAE038A31330137013 6013C01261EA2300121E0E1D7E9C12>III102 DIII<1307130FA213061300 A61378139CEA010C1202131C12041200A21338A41370A413E0A4EA01C01261EAF180EAF3 0012E6127C1024809B11>III<39381F81F0394E20C618394640E81CEB80F0EA8F00008E13E0120EA2391C01C0 38A315703938038071A215E115E23970070064D83003133820127E9124>II<380787803809C8603808D03013E0EA11C014381201A23803 8070A31460380700E014C0EB0180EB8300EA0E86137890C7FCA25AA4123CB4FC151A8191 15>112 DII<001C13C0EA27011247A238870380 A2120EA2381C0700A438180E20A3EA1C1E380C26403807C38013127E9118>117 DI<001CEBC080392701C1C0124714C03987038040A2120EA2391C0700 80A3EC0100EA1806A2381C0E02EB0F04380E13083803E1F01A127E911E>I<3807878038 08C8403810F0C03820F1E0EBE3C03840E1803800E000A2485AA43863808012F3EB810012 E5EA84C6EA787813127E9118>I<001C13C0EA27011247A238870380A2120EA2381C0700 A4EA180EA3EA1C1EEA0C3CEA07DCEA001C1318EA6038EAF0305B485AEA4180003EC7FC12 1A7E9114>II E /Fk 37 122 df12 D<13181378EA01F812FFA21201B3A7387F FFE0A213207C9F1C>49 DI<13FE3807FFC0380F07E0381E 03F0123FEB81F8A3EA1F0314F0120014E0EB07C0EB1F803801FE007F380007C0EB01F014 F8EB00FCA2003C13FE127EB4FCA314FCEA7E01007813F8381E07F0380FFFC03801FE0017 207E9F1C>I<14E013011303A21307130F131FA21337137713E7EA01C71387EA03071207 120E120C12181238127012E0B6FCA2380007E0A790B5FCA218207E9F1C>I<0030132038 3E01E0383FFFC0148014005B13F8EA33C00030C7FCA4EA31FCEA37FF383E0FC0383807E0 EA3003000013F0A214F8A21238127C12FEA200FC13F0A2387007E0003013C0383C1F8038 0FFF00EA03F815207D9F1C>II66 D68 DII73 D78 D80 D82 D<007FB61280A2397E03F80F00781407007014030060140100E015C0A200C01400A40000 1500B3A248B512F0A222227EA127>84 D86 DI97 DIII< 13FE3807FF80380F87C0381E01E0003E13F0EA7C0014F812FCA2B5FCA200FCC7FCA3127C A2127E003E13186C1330380FC0703803FFC0C6130015167E951A>II<12 1C123E127FA3123E121CC7FCA7B4FCA2121FB2EAFFE0A20B247EA310>105 D107 DI<3AFF07F007F090391FFC1FFC3A1F303E303E01401340496C487EA2 01001300AE3BFFE0FFE0FFE0A22B167E9530>I<38FF07E0EB1FF8381F307CEB403CEB80 3EA21300AE39FFE1FFC0A21A167E951F>I<13FE3807FFC0380F83E0381E00F0003E13F8 48137CA300FC137EA7007C137CA26C13F8381F01F0380F83E03807FFC03800FE0017167E 951C>I113 DII<487EA41203A2 1207A2120F123FB5FCA2EA0F80ABEB8180A5EB8300EA07C3EA03FEEA00F811207F9F16> I<38FF01FEA2381F003EAF147E14FE380F81BE3907FF3FC0EA01FC1A167E951F>I<39FF E01FE0A2391F800700000F1306EBC00E0007130C13E000035BA26C6C5AA26C6C5AA2EB7C C0A2137F6D5AA26DC7FCA2130EA21B167F951E>I<39FFE01FE0A2391F800700000F1306 EBC00E0007130C13E000035BA26C6C5AA26C6C5AA2EB7CC0A2137F6D5AA26DC7FCA2130E A2130CA25B1278EAFC3813305BEA69C0EA7F80001FC8FC1B207F951E>121 D E /Fl 32 122 df45 D<1230127812F0126005047C830C >I<137CEA0186EA020300041380138312081210A3381107001212EA0C0EC65A13305BEA 01800002C7FC120CEA10011220EA3C06EA67FEEAC1FCEA80F011187D9714>50 D<1420146014E0A2130114F0EB0270A213041308A21310A213201340A2EB8038EBFFF838 0100381202A25AA25A121838FE01FF181A7E991D>65 D<3803FFF83800700E1406140713 E0A43801C00E141C143814703803FFE0EB80781438141CEA0700A4000E1338A2147014E0 381C03C0B51200181A7D991B>II<0003B5FC380070071403140113E0A43801C080A313C13803FF001381A3EA 0702EB0004A21408120E1418141014304813E0B5FC181A7D991A>69 D 73 DI76 DI<3803FFF83800701C1406140713E0A43801C0 0EA2141C143838038060EBFF80EB8000A248C7FCA4120EA45AB47E181A7D991A>80 D83 D<383FFFFC38381C0C00201304124013381280A338007000A45BA4485AA4485AA41207EA FFF8161A79991B>I97 D99 DII<1307EB0980131BEB3B00133813301370A4EA07FFEA00E0A5485AA5485AA490 C7FC5AA21206126612E412CC1270112181990C>I<13F338038B8038060700120E120C12 1CEA380EA4EA301CA3EA183C5BEA07B8EA0038A25B1260EAE0E0EAC1C0007FC7FC11177E 8F12>II<1203120712061200A61238124C124E 128E129CA2121C1238A212701272A212E212E41264123808197C980C>I<121F1207A312 0EA4121CA41238A41270A412E4A412E81230081A7D990A>108 D<38307C1E3859866339 9E0783801403129CA239380E0700A3140ED8701C1340A2141C158038E0380C3960180700 1A107C8F1F>IIII114 DI<1206120EA45AA2EAFFC0EA1C005AA45AA412E1A312E212E4 12380A177C960D>II121 D E /Fm 16 117 df<127812FCA4127806067D850C>46 D48 DIII<130613 0E131E133E137E13DEEA019E131E12031206120C12181230126012C0B512E0A238001E00 A53801FFE0A213187F9716>II<126038 7FFFC0A214801400EAE00612C05B5BC65A5B13E0A212015B1203A31207A66C5A12197E98 16>55 D57 D<1303497EA2497EA3EB1BE0A2EB3BF01331A2EB60F8A2EBE0FCEBC07CA248487EEBFFFE 487FEB001F4814800006130FA248EB07C039FF803FFCA21E1A7F9921>65 D97 D<12FCA2123CA713FE383F8780383E01C0003C13E0EB00F0A214F8 A514F0A2EB01E0003E13C0383B07803830FE00151A7E9919>II114 DI<1206A4120EA2121EEA3FF012FFEA1E00A81318A5 EA0F30EA03E00D187F9711>I E /Fn 73 128 df<121CA2123C1270126012C012800607 789913>19 D<1380EA010012025A120C120812185AA35AA412E0AA1260A47EA37E120812 0C12047E7EEA008009267D9B0F>40 D<7E12407E7E12181208120C7EA37EA41380AA1300 A41206A35A1208121812105A5A5A09267E9B0F>I<126012F0A212701210A31220A21240 A2040B7D830B>44 DI<126012F0A2126004047D830B>I48 D<12035AB4FC1207B3A2EA7FF80D187D9713>III<1318A21338137813F813B8EA01381202A212041208 121812101220124012C0B5FCEA0038A6EA03FF10187F9713>III<1240EA7FFF13FEA2EA4004EA80081310A2EA00201340A21380120113005AA25A 1206A2120EA5120410197E9813>III<126012F0A212601200A8126012F0A2126004107D8F0B>I<126012F0A212601200 A8126012F0A212701210A31220A21240A204177D8F0B>I<137F380180C0380600300008 1308487F38203E0213E13841C081384380710083EB7080EA8700A6EA838012433941C0F1 003820E131EB3E1E6CC8FC7E0006EB03803901803E0038007FE0191A7E991E>64 D<130CA3131EA2132F1327A2EB4380A3EB81C0A200017F1300A248B47E38020070A2487F A3487FA2003C131EB4EBFFC01A1A7F991D>III IIII<39FFE1FFC0390E001C00AB380F FFFC380E001CAC39FFE1FFC01A1A7F991D>II< EA0FFEEA0070B3124012E0A2EA40E0EA61C0EA1F000F1A7E9914>I<39FFE01FC0390E00 0F00140C14085C5C5C495A0102C7FC5B130C131C132E1347EB8380EA0F03380E01C06D7E A2147080A280141E141F39FFE07FC01A1A7F991E>III<00FEEB7FC0000FEB0E001404EA0B80EA09C0A2EA08E01370A21338131CA213 0E1307EB0384A2EB01C4EB00E4A21474143CA2141C140C121C38FF80041A1A7F991D>I< 137F3801C1C038070070000E7F487F003C131E0038130E0078130F00707F00F01480A800 78EB0F00A20038130E003C131E001C131C6C5B6C5B3801C1C0D8007FC7FC191A7E991E> II82 DI<007FB5FC38 701C0700401301A200C0148000801300A300001400B13803FFE0191A7F991C>I<39FFE0 7FC0390E000E001404B200065B12076C5B6C6C5A3800E0C0013FC7FC1A1A7F991D>I<39 FF801FC0391C00070014066C1304A36C5BA26C6C5AA36C6C5AA26C6C5AA3EB7080A21379 0139C7FCA2131EA3130CA21A1A7F991D>I<3AFF81FF07F03A3C007801C0001CEC0080A3 6C90389C0100A33907010E02A33903830F04EB8207A2150C3901C40388A33900E801D0A3 90387000E0A301305B01201340241A7F9927>I<39FFC0FF80390F003C0014106C5BEA03 806D5A00015BEA00E101F1C7FC137A133E131C131EA21317EB27801343EB41C0EB81E0EA 010048137000021378481338000C7F001E133EB4EB7FC01A1A7F991D>I<39FF801FE039 1E00070014066C13046C130CEB800800035BEA01C06D5A00001360EB7040EB7880133801 1DC7FC131F130EAAEBFFC01B1A7F991D>II<12FEA212C0B3AF12FEA207257D9B0B>I<12FEA21206B3AF12FEA20725809B 0B>93 D97 D<12FC121CA913FCEA1D07381E0380381C01C0130014E0A6 EB01C01480381E0300EA1906EA10F8131A809915>II<133F1307A9EA03E7EA0C17EA180F48 7E127012E0A6126012706C5AEA1C373807C7E0131A7F9915>IIII<12FC121CA9137CEA1D87381E0380A2121CAB 38FF9FF0141A809915>I<1218123CA212181200A612FC121CAE12FF081A80990A>II<12FC 121CA9EB1FC0EB0F00130C5B13205B13E0121DEA1E70EA1C7813387F131E7F148038FF9F E0131A809914>I<12FC121CB3A6EAFF80091A80990A>I<38FC7C1F391D8E6380391E0781 C0A2001C1301AB39FF9FE7F81D107F8F20>IIIIIII<1208A412 18A21238EAFFC0EA3800A81320A41218EA1C40EA07800B177F960F>I<38FC1F80EA1C03 AB1307120CEA0E0B3803F3F01410808F15>I<38FF0F80383C0700EA1C061304A26C5AA2 6C5AA3EA03A0A2EA01C0A36C5A11107F8F14>I<39FE7F1F8039381C0700003C1306381C 0C04130E380E16081317A238072310149013A33803C1A014E0380180C0A319107F8F1C> I<38FE3F80383C1E00EA1C086C5AEA0F306C5A6C5A12017F1203EA0270487E1208EA181C EA381E38FC3FC012107F8F14>I<38FF0F80383C0700EA1C061304A26C5AA26C5AA3EA03 A0A2EA01C0A36C5AA248C7FCA212E112E212E4127811177F8F14>I 123 D127 D E /Fo 4 66 df<13C0A9B51280A23800C000A911 147E8F17>43 D<1218127812981218AC12FF08107D8F0F>49 D<121FEA6180EA40C0EA80 6012C01200A213C0EA0180EA030012065AEA10201220EA7FC012FF0B107F8F0F>I<13C0 A2487E1360A2EA0230A3487EA2487EEA0FFCEA080C487EA2EA300738FC1FC012117F9016 >65 D E /Fp 10 62 df<120212041208121812101230122012601240A212C0AA1240A2 12601220123012101218120812041202071E7D950D>40 D<128012401220123012101218 1208120C1204A21206AA1204A2120C1208121812101230122012401280071E7E950D>I< 1360AAB512F0A238006000AA14167E9119>43 D<120FEA30C0EA6060A2EA4020EAC030A9 EA4020EA6060A2EA30C0EA0F000C137E9211>48 D<120C121C12EC120CAFEAFFC00A137D 9211>I<121FEA60C01360EAF07013301260EA0070A2136013C012011380EA02005AEA08 101210EA2020EA7FE012FF0C137E9211>II<136013E0 A2EA016012021206120C120812101220126012C0EAFFFCEA0060A5EA03FC0E137F9211> I54 D<387FFFE0B512F0C8FCA6B512F06C13E0140A7E 8B19>61 D E /Fq 80 128 df11 D<137E3801C180EA03013807 03C0120EEB018090C7FCA5B512C0EA0E01B0387F87F8151D809C17>II<90383F07E03901C09C1838 0380F0D80701133C000E13E00100131892C7FCA5B612FC390E00E01CB03A7FC7FCFF8021 1D809C23>I<120EA2121E1238127012E012800707779C15>19 D34 D<1380EA0100120212065AA25AA25AA35AA412E0AC1260A47EA37EA27EA27E12027EEA00 80092A7C9E10>40 D<7E12407E12307EA27EA27EA37EA41380AC1300A41206A35AA25AA2 5A12205A5A092A7E9E10>I<1306ADB612E0A2D80006C7FCAD1B1C7E9720>43 D<126012F0A212701210A41220A212401280040C7C830C>II<12 6012F0A2126004047C830C>I48 D<5A1207123F12C71207B3A5EAFFF80D1C7C9B15>III<130CA2131C133CA2135C13DC139CEA011C12 0312021204120C1208121012301220124012C0B512C038001C00A73801FFC0121C7F9B15 >II<13F0EA030CEA0404 EA0C0EEA181E1230130CEA7000A21260EAE3E0EAE430EAE818EAF00C130EEAE0061307A5 1260A2EA7006EA300E130CEA1818EA0C30EA03E0101D7E9B15>I<1240387FFF801400A2 EA4002485AA25B485AA25B1360134013C0A212015BA21203A41207A66CC7FC111D7E9B15 >III<126012F0A212601200AA126012F0A2126004127C910C>I<126012F0A212601200 AA126012F0A212701210A41220A212401280041A7C910C>I<007FB512C0B612E0C9FCA8 B612E06C14C01B0C7E8F20>61 D63 D<1306A3130FA3EB1780A2EB37C01323A2EB43E01341A2EB80F0A338010078A2EBFFF838 02003CA3487FA2000C131F80001E5BB4EBFFF01C1D7F9C1F>65 DI<90381F8080EBE0613801801938070007000E13035A14015A00781300A212 7000F01400A8007014801278A212386CEB0100A26C13026C5B380180083800E030EB1FC0 191E7E9C1E>IIII<90381F8080EBE0613801801938070007000E13035A14015A007813 00A2127000F01400A6ECFFF0EC0F80007013071278A212387EA27E6C130B380180113800 E06090381F80001C1E7E9C21>I<39FFF0FFF0390F000F00AC90B5FCEB000FAD39FFF0FF F01C1C7F9B1F>II<3807FF8038007C00133CB3 127012F8A21338EA7078EA4070EA30E0EA0F80111D7F9B15>I<39FFF01FE0390F000780 EC060014045C5C5C5C5C49C7FC13021306130FEB17801327EB43C0EB81E013016D7E1478 A280143E141E80158015C039FFF03FF01C1C7F9B20>IIIIII82 D<3807E080EA1C19EA30051303EA600112E01300 A36C13007E127CEA7FC0EA3FF8EA1FFEEA07FFC61380130FEB07C0130313011280A300C0 1380A238E00300EAD002EACC0CEA83F8121E7E9C17>I<007FB512C038700F0100601300 00401440A200C014201280A300001400B1497E3803FFFC1B1C7F9B1E>I<39FFF01FF039 0F000380EC0100B3A26C1302138000035BEA01C03800E018EB7060EB0F801C1D7F9B1F> I<3AFFE1FFC0FF3A1F003E003C001E013C13186C6D1310A32607801F1320A33A03C02780 40A33A01E043C080A33A00F081E100A39038F900F3017913F2A2017E137E013E137CA201 3C133C011C1338A20118131801081310281D7F9B2B>87 D<39FFF003FC390F8001E00007 EB00C06D13800003EB01006D5A000113026C6C5A13F8EB7808EB7C18EB3C10EB3E20131F 6D5A14C06D5AABEB7FF81E1C809B1F>89 D<12FEA212C0B3B312FEA207297C9E0C>91 D I<12FEA21206B3B312FEA20729809E0C>I<120C12121221EA4080EA80400A057B9B15>I< EA1FC0EA3070EA78387F12301200A2EA01FCEA0F1C12381270126000E01340A3EA603C38 304E80381F870012127E9115>97 D<12FC121CAA137CEA1D87381E0180381C00C014E014 601470A6146014E014C0381E018038190700EA10FC141D7F9C17>IIII<13F8EA018CEA071E1206EA 0E0C1300A6EAFFE0EA0E00B0EA7FE00F1D809C0D>II<12FC121CAA13 7C1387EA1D03001E1380121CAD38FF9FF0141D7F9C17>I<1218123CA21218C7FCA712FC 121CB0EAFF80091D7F9C0C>I<13C0EA01E0A2EA00C01300A7EA07E01200B3A21260EAF0 C012F1EA6180EA3E000B25839C0D>I<12FC121CAAEB0FE0EB0780EB06005B13105B5B13 E0121DEA1E70EA1C781338133C131C7F130F148038FF9FE0131D7F9C16>I<12FC121CB3 A9EAFF80091D7F9C0C>I<39FC7E07E0391C838838391D019018001EEBE01C001C13C0AD 3AFF8FF8FF8021127F9124>IIII<3803E0 80EA0E19EA1805EA3807EA7003A212E0A61270A2EA38071218EA0E1BEA03E3EA0003A7EB 1FF0141A7F9116>III<1204A4120CA2121C123CEAFFE0EA1C00A91310A5 120CEA0E20EA03C00C1A7F9910>I<38FC1F80EA1C03AD1307120CEA0E1B3803E3F01412 7F9117>I<38FF07E0383C0380381C0100A2EA0E02A2EA0F06EA0704A2EA0388A213C8EA 01D0A2EA00E0A3134013127F9116>I<39FF3FC7E0393C0703C0001CEB01801500130B00 0E1382A21311000713C4A213203803A0E8A2EBC06800011370A2EB8030000013201B127F 911E>I<38FF0FE0381E0700EA1C06EA0E046C5AEA039013B0EA01E012007F12011338EA 021C1204EA0C0E487E003C138038FE1FF014127F9116>I<38FF07E0383C0380381C0100 A2EA0E02A2EA0F06EA0704A2EA0388A213C8EA01D0A2EA00E0A31340A25BA212F000F1C7 FC12F312661238131A7F9116>III127 D E /Fr 14 121 df<13401380EA01005A12061204120C5AA212381230A212701260A412E0AC1260A4 12701230A212381218A27E120412067E7EEA008013400A2E7BA112>40 D<7E12407E12307E1208120C7EA212077EA213801201A413C0AC1380A412031300A25A12 06A25A120812185A12205A5A0A2E7EA112>I<5B497EA3497EA3EB09E0A3EB10F0A3EB20 78A3497EA2EBC03EEB801EA248B5FCEB000FA20002EB0780A348EB03C0A2120C001E14E0 39FF801FFE1F207F9F22>65 D69 D97 D<121C12FC121CAA137CEA1D87381E01 80EB00C0001C13E01470A21478A6147014F014E0001E13C0381A018038198700EA107C15 207E9F19>IIII110 D114 DI<1202A31206A2120EA2123EEAFFF8EA 0E00AB1304A5EA07081203EA01F00E1C7F9B12>I<38FF87F8381E03C0380E0180EB0300 EA0702EA0384EA01C813D8EA00F01370137813F8139CEA010E1202EA060738040380000C 13C0003C13E038FE07FC16147F9318>120 D E /Fs 23 119 df 45 D69 D76 D79 DI<3803FF80000F13F0381F 01FC383F80FE147F801580EA1F00C7FCA4EB3FFF3801FC3FEA0FE0EA1F80EA3F00127E5A A4145F007E13DF393F839FFC381FFE0F3803FC031E1B7E9A21>97 DII101 DI<9038FF80F000 03EBE3F8390FC1FE1C391F007C7C48137E003EEB3E10007EEB3F00A6003E133E003F137E 6C137C380FC1F8380BFFE00018138090C8FC1238A2123C383FFFF814FF6C14C06C14E06C 14F0121F383C0007007CEB01F8481300A4007CEB01F0A2003FEB07E0390FC01F806CB512 0038007FF01E287E9A22>II<1207EA0F80EA1FC0EA3FE0 A3EA1FC0EA0F80EA0700C7FCA7EAFFE0A3120FB3A3EAFFFEA30F2B7EAA12>I108 D<26FFC07FEB1FC0903AC1FFC07FF0903AC307E0 C1F8D80FC49038F101FC9039C803F20001D801FE7F01D05BA201E05BB03CFFFE3FFF8FFF E0A3331B7D9A38>I<38FFC07E9038C1FF809038C30FC0D80FC413E0EBC80701D813F013 D0A213E0B039FFFE3FFFA3201B7D9A25>II<90383F80703901FFE0F03803 F079380FE01D381F800F123FEB00075AA2127E12FEA8127FA27E1380001F130F380FC01F 3807F0773801FFE738007F87EB0007A9EC7FFFA320277E9A23>113 D<38FFC1F0EBC7FCEBC63E380FCC7F13D813D0A2EBF03EEBE000B0B5FCA3181B7F9A1B> I<3803FE30380FFFF0EA3E03EA7800127000F01370A27E00FE1300EAFFE06CB4FC14C06C 13E06C13F0000713F8C6FCEB07FC130000E0137C143C7E14387E6C137038FF01E038E7FF C000C11300161B7E9A1B>I<13E0A41201A31203A21207120F381FFFE0B5FCA2380FE000 AD1470A73807F0E0000313C03801FF8038007F0014267FA51A>I<39FFE07FF0A3000F13 07B2140FA2000713173903F067FF3801FFC738007F87201B7D9A25>I<39FFFC03FFA339 0FF000F0000714E07F0003EB01C0A2EBFC0300011480EBFE070000140013FFEB7F0EA214 9EEB3F9C14FC6D5AA26D5AA36D5AA26D5AA2201B7F9A23>I E end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%PaperSize: a4 %%BeginPaperSize: a4 a4 %%EndPaperSize %%EndSetup %%Page: 1 1 1 0 bop 271 194 a Fs(On)22 b(the)h(Equiv)l(alence)i(Problem)e(for)f (E-P)n(attern)751 263 y(Languages)697 369 y Fr(\(Extended)15 b(Abstract\))559 513 y Fq(Enno)f(Ohlebusc)o(h)855 498 y Fp(1)889 513 y Fq(and)f(Esk)o(o)h(Ukk)o(onen)1228 498 y Fp(2)514 584 y Fo(1)550 600 y Fn(T)m(ec)o(hnisc)o(he)h(F)m(akult\177) -19 b(at,)14 b(Univ)o(ersit)o(y)g(of)f(Bielefeld,)536 646 y(P)m(.O.)f(Bo)o(x)i(100131,)f(33501)h(Bielefeld,)h(German)o(y)575 691 y(email:)f(enno@T)m(ec)o(hF)m(ak.Uni-Bielefel)q(d.DE)406 721 y Fo(2)442 737 y Fn(Departmen)o(t)g(of)f(Computer)g(Science,)i (Univ)o(ersit)o(y)f(of)f(Helsinki,)551 783 y(P)m(.O.)f(Bo)o(x)h(26,)g (FIN-00014)h(Helsinki,)h(Finland)599 828 y(email:)f(Esk)o(o.Ukk)o (onen@cs.Helsink)q(i.FI)301 951 y Fm(Abstract.)22 b Fn(On)14 b(the)g(one)g(hand,)g(the)g(inclusion)j(problem)e(for)f(nonerasing)i (and)301 996 y(erasing)k(pattern)e(languages)j(is)e(undecidable;)i(see) d([JSSY95)q(].)f(On)h(the)h(other)301 1042 y(hand,)10 b(the)g(language)h(equiv)n(alence)i(problem)e(for)e(NE-pattern)h (languages)i(is)e(triv-)301 1088 y(ially)i(decidable)h(\(see)d([Ang80a) q(]\))f(but)i(the)f(question)i(of)e(whether)g(the)g(same)h(holds)301 1133 y(for)k(E-pattern)h(languages)i(is)e(still)h(op)q(en.)g(It)e(has)h (b)q(een)g(conjectured)g(b)o(y)g(Jiang)301 1179 y Fl(et)11 b(al.)g Fn([JSSY95])g(that)g(the)h(language)h(equiv)n(alence)h(problem) f(for)e(E-pattern)g(lan-)301 1225 y(guages)j(is)f(also)h(decidable.)h (In)e(this)h(pap)q(er,)f(w)o(e)f(in)o(tro)q(duce)j(a)e(new)f(normal)j (form)301 1270 y(for)c(patterns)i(and)f(sho)o(w,)g(using)h(the)f (normal)h(form,)e(that)h(the)g(language)i(equiv)n(a-)301 1316 y(lence)d(problem)h(for)e(E-pattern)h(languages)i(is)e(decidable)i (in)e(man)o(y)g(sp)q(ecial)h(cases.)301 1362 y(W)m(e)j(conjecture)h (that)g(our)f(normal)i(form)e(pro)q(cedure)h(decides)h(the)f(problem)g (in)301 1407 y(the)c(general)i(case,)f(to)q(o.)f(If)g(the)g(conjecture) h(holds)h(true,)e(then)h(the)g(normal)h(form)301 1453 y(is)f(the)h(shortest)f(pattern)h(generating)h(a)e(giv)o(en)h (E-pattern)f(language.)183 1590 y Fk(1)56 b(In)n(tro)r(duction)183 1685 y Fq(A)11 b(pattern)i Fj(\013)e Fq(is)h(a)g(w)o(ord)f(o)o(v)o(er)h (t)o(w)o(o)f(disjoin)o(t)g(alphab)q(ets)h Fj(\006)c Fi([)d Fj(V)k Fq(,)i(where)i Fj(\006)h Fq(is)e(an)g(alphab)q(et)183 1734 y(of)f(terminals)g(and)h Fj(V)22 b Fq(is)12 b(an)g(alphab)q(et)h (of)e(v)n(ariables.)g(The)i(language)e Fj(L)1311 1740 y Fh(E)r(;\006)1377 1734 y Fq(\()p Fj(\013)p Fq(\))h(generated)183 1784 y(b)o(y)j(the)g(pattern)h Fj(\013)f Fq(is)g(obtained)g(in)g(the)h (ob)o(vious)e(w)o(a)o(y:)g(One)i(tak)o(es)f(all)f(w)o(ords)i(obtained) 183 1834 y(b)o(y)f(substituting)g(w)o(ords)h(o)o(v)o(er)f Fj(\006)j Fq(for)d(the)h(v)n(ariables)e(in)h Fj(\013)p Fq(.)f(In)i(the)f(same)g(w)o(a)o(y)m(,)e(one)j(gets)183 1884 y(the)h(language)f Fj(L)461 1890 y Fh(N)s(E)r(;\006)556 1884 y Fq(\()p Fj(\013)p Fq(\))g({)h(only)e(in)i(this)f(case)i(the)f (replacemen)o(t)g(of)f(a)g(v)n(ariable)g(with)183 1934 y(the)h(empt)o(y)e(w)o(ord)h Fj(\025)g Fq(is)g(forbidden.)g(Here)h(E)g (stands)g(for)f(erasing,)g(whereas)h(NE)g(stands)183 1983 y(for)c(nonerasing)h(pattern)h(language.)245 2033 y(It)f(is)h(kno)o(wn)f(that)g(the)h(inclusion)f(problem)f(\(is)h(the)h (language)f(generated)i(b)o(y)e(a)g(pat-)183 2083 y(tern)20 b(included)f(in)g(the)h(language)e(generated)j(b)o(y)e(another)h (pattern?\))g(for)f(nonerasing)183 2133 y(and)d(erasing)g(pattern)i (languages)e(is)g(undecidable;)g(see)i([JSSY95].)d(Ho)o(w)o(ev)o(er,)h (the)h(lan-)183 2183 y(guage)f(equiv)n(alence)h(problem)e(\(do)h(t)o(w) o(o)g(patterns)i(generate)g(the)f(same)f(language?\))f(for)183 2232 y(nonerasing)i(patterns)h(is)f(trivially)e(decidable:)i(Tw)o(o)f (patterns)i Fj(\013)f Fq(and)g Fj(\014)j Fq(generate)e(the)183 2282 y(same)c(NE-language)h(if)g(and)g(only)g(if)g(they)h(are)g(iden)o (tical)f(up)g(to)h(v)n(ariable)e(renaming.)f(It)183 2332 y(is)h(v)o(ery)g(easy)h(to)f(see)i(that)e(this)h(do)q(es)g(not)f(hold)g (for)g(E-patterns.)h(Jiang)e Fg(et)j(al.)d Fq([JSSY95])183 2382 y(conjectured)g(that)e(the)h(language)e(equiv)n(alence)h(problem)f (for)h(erasing)g(pattern)h(languages)183 2432 y(is)h(decidable)h(\(cf.) g(also)f([Sal94)n(]\).)g(Ho)o(w)o(ev)o(er,)h(they)g(did)g(not)f(state)i (a)e(decision)h(pro)q(cedure.)p eop %%Page: 2 2 2 1 bop 403 194 a Fq(In)15 b(this)g(pap)q(er,)h(w)o(e)f(in)o(v)o (estigate)g(the)h(E-language)e(equiv)n(alence)h(problem)f(and)h(sho)o (w)340 244 y(that)f(the)g(conjecture)h(is)f(true)g(in)f(man)o(y)f (cases.)i(Our)g(\\decision)g(pro)q(cedure")h(is)e(based)i(on)340 293 y(a)d(decidable)f(and)h(length-decreasing)g(reduction)h(relation)e Fi(!)h(\032)24 b Fq(\()p Fj(\006)7 b Fi([)e Fj(V)k Fq(\))1536 278 y Fp(+)1568 293 y Fi(\002)c Fq(\()p Fj(\006)i Fi([)e Fj(V)k Fq(\))1742 278 y Fp(+)1770 293 y Fq(.)340 343 y(Roughly)15 b(sp)q(eaking,)h(pattern)h Fj(\013)f Fq(reduces)i(to)f (another)f(pattern)h Fj(\013)1421 328 y Ff(0)1449 343 y Fq(\(whic)o(h)f(will)f(b)q(e)i(de-)340 393 y(noted)f(b)o(y)e Fj(\013)f Fi(!)g Fj(\013)637 378 y Ff(0)648 393 y Fq(\))i(if)g Fj(\013)746 378 y Ff(0)772 393 y Fq(can)g(b)q(e)g(obtained)g(from)e (the)j(pattern)g Fj(\013)e Fq(b)o(y)h(deleting)g(certain)340 443 y(v)n(ariables)g(from)f Fj(\013)h Fq(and)h Fj(\013)e Fq(=)h Fj(\033)q Fq(\()p Fj(\013)895 428 y Ff(0)907 443 y Fq(\),)g(where)i Fj(\033)f Fq(is)g(a)f(\(linear\))h(substitution.)f (Since)h Fi(!)f Fq(is)340 493 y(length-decreasing,)f(ev)o(ery)g (reduction)g(sequence)h(starting)e(from)e(a)i(pattern)h Fj(\013)f Fq(m)o(ust)f(end)340 542 y(in)19 b(an)f(irreducible)h (pattern,)g(a)g(so-called)f(normal)f(form.)f(Moreo)o(v)o(er,)j Fi(!)f Fq(is)g(language-)340 592 y(preserving,)g(that)g(is,)e(if)h Fj(\013)g Fi(!)g Fj(\013)877 577 y Ff(0)888 592 y Fq(,)g(then)h Fj(L)1043 598 y Fh(E)r(;\006)1108 592 y Fq(\()p Fj(\013)p Fq(\))g(=)f Fj(L)1262 598 y Fh(E)r(;\006)1328 592 y Fq(\()p Fj(\013)1371 577 y Ff(0)1382 592 y Fq(\).)g(W)m(e)g(conjecture)i(that) 340 642 y(reduction)c(to)f(normal)e(form)g(yields)h(a)h(decision)g(pro) q(cedure:)340 742 y Fe(Conjecture)j(1:)f Fq(Tw)o(o)g(E-patterns)h (de\014ne)g(the)g(same)e(language)g(o)o(v)o(er)h(an)g(alphab)q(et)g Fj(\006)340 791 y Fq(with)e Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))e Fi(\025)h Fq(3)g(if)h(and)g(only)f(if)g(their)i(normal)d(forms) g(with)i(resp)q(ect)i(to)e Fi(!)g Fq(are)g(iden-)340 841 y(tical,)f(up)h(to)g(renaming)e(of)h(v)n(ariables.)340 941 y(Note)21 b(that)g(in)f(Conjecture)i(1,)d(the)j(restriction)f Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))i Fi(\025)g Fq(3)d(is)h(essen)o (tial.)f(This)g(is)340 991 y(witnessed)c(b)o(y)d(the)i(follo)o(wing)c (example.)340 1065 y Fg(Example)d(1.)21 b Fq(Let)c Fj(\006)j Fq(=)d Fi(f)p Fq(0)p Fj(;)7 b Fq(1)p Fi(g)p Fq(,)16 b Fj(\013)g Fq(=)i Fj(x)p Fq(01)p Fj(y)q Fq(0)p Fj(z)r Fq(,)e(and)h Fj(\014)j Fq(=)d Fj(x)p Fq(0)p Fj(y)q Fq(10)p Fj(z)r Fq(.)g(Both)g Fj(\013)g Fq(and)g Fj(\014)j Fq(are)340 1114 y(in)g(normal)e(form)h(w.r.t.)g Fi(!)p Fq(;)g(see)j(Section)f(4.)e (Moreo)o(v)o(er,)i Fj(L)1344 1120 y Fh(E)r(;\006)1409 1114 y Fq(\()p Fj(\013)p Fq(\))h(=)h Fj(L)1573 1120 y Fh(E)r(;\006)1638 1114 y Fq(\()p Fj(\014)r Fq(\);)e(see)340 1164 y([JKS)428 1149 y Fp(+)456 1164 y Fq(94].)13 b(Ho)o(w)o(ev)o(er,)g Fj(\013)h Fq(and)g Fj(\014)i Fq(are)e(not)g(iden)o(tical)f(up)h(to)g (renaming)e(of)i(v)n(ariables.)340 1238 y(W)m(e)g(will)e(pro)o(v)o(e)h (in)g(Section)h(4)f(that)h(the)g(conjecture)h(can)f(b)q(e)g (paraphrased)h(as)e(follo)o(ws:)f(If)340 1288 y Fj(\013;)7 b(\014)14 b Fi(2)d Fq(\()p Fj(\006)g Fi([)d Fj(V)i Fq(\))607 1273 y Fp(+)648 1288 y Fq(are)k(patterns)g(and)g Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))e Fi(\025)f Fq(3,)i(then)h Fj(L)1332 1294 y Fh(E)r(;\006)1398 1288 y Fq(\()p Fj(\013)p Fq(\))d(=)h Fj(L)1540 1294 y Fh(E)r(;\006)1605 1288 y Fq(\()p Fj(\014)r Fq(\))j(if)d(and)340 1338 y(only)j(if)f(there)i(are)g(substitutions)f Fj(f)k Fq(:)13 b Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))h Fi(!)f Fj(v)q(ar)q Fq(\()p Fj(\014)r Fq(\))1273 1323 y Ff(\003)1308 1338 y Fq(and)i Fj(g)g Fq(:)e Fj(v)q(ar)q Fq(\()p Fj(\014)r Fq(\))i Fi(!)e Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))1762 1323 y Ff(\003)340 1387 y Fq(suc)o(h)i(that)f Fj(f)t Fq(\()p Fj(\013)p Fq(\))e(=)g Fj(\014)17 b Fq(and)c Fj(g)q Fq(\()p Fj(\014)r Fq(\))g(=)f Fj(\013)p Fq(.)403 1437 y(Also)e(note)h(that)f(if)g(Conjecture)i(1)e(holds)g(true,)h(then) g(the)g(normal)e(form)f(is)j(the)g Fg(shortest)340 1487 y Fq(pattern)h(that)e(generates)i(a)e(giv)o(en)g(E-pattern)i(language.) d(This)h(is)g(b)q(ecause)i Fi(!)e Fq(is)g(a)g(length-)340 1537 y(decreasing)i(reduction)g(relation.)d(Hence)k(w)o(e)d (conjecture,)i(in)f(fact,)f(that)h(our)f(normal)f(form)340 1587 y(is)14 b(a)g(minim)o(al)c(description)15 b(of)e(the)h(corresp)q (onding)h(language.)403 1636 y(W)m(e)c(will)g(pro)o(v)o(e)h(in)f (Sections)i(3)f(and)g(5)f(that)h(the)h(equiv)n(alence)f(problem)f(for)g (E-pattern)340 1686 y(languages)f(can)g(in)g(man)o(y)e(cases)k(b)q(e)f (decided)g(b)o(y)f(this)g(pro)q(cedure,)i(for)d(instance)i(whenev)o (er:)366 1760 y Fe({)21 b Fq(the)15 b(underlying)f(alphab)q(et)h Fj(\006)i Fq(con)o(tains)d(t)o(w)o(o)g(constan)o(ts)i(that)e(do)h(not)f (o)q(ccur)i(in)e(the)411 1810 y(patterns)h(\(this)f(is)g(alw)o(a)o(ys)f (true)h(if)g Fj(\006)i Fq(is)e(in\014nite\),)366 1860 y Fe({)21 b Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\),)15 b(the)h(cardinalit)o(y)e(of)g Fj(\006)r Fq(,)h(exceeds)j(the)d(n)o(um)o (b)q(er)g(of)f(terminal)g(segmen)o(ts)h(in)411 1910 y(one)f(pattern)h (b)o(y)e(at)h(least)g(t)o(w)o(o,)366 1959 y Fe({)21 b Fq(the)14 b(normal)e(form)g(of)i(one)g(pattern)g(has)g(indep)q(enden)o (t)i(v)n(ariable)c(segmen)o(ts,)366 2009 y Fe({)21 b Fq(the)14 b(normal)e(form)g(of)i(one)g(pattern)g(is)g(linear,)366 2059 y Fe({)21 b Fq(the)14 b(normal)e(form)g(of)i(one)g(pattern)g(is)g (a)g(one-v)n(ariable)f(pattern,)366 2109 y Fe({)21 b Fq(the)14 b(normal)e(form)g(of)i(one)g(pattern)g(do)q(es)h(not)f(con)o (tain)f(consecutiv)o(e)j(v)n(ariables.)340 2183 y(It)d(is)g(in)o (teresting)g(to)g(note)g(that)g(the)g(\014rst)h(t)o(w)o(o)e(sp)q(ecial) h(cases)i(can)e(already)f(b)q(e)i(pro)o(v)o(ed)f(b)o(y)340 2232 y(further)j(dev)o(eloping)e(a)h(pro)q(of)f(tec)o(hnique)i(used)g (in)e([JSSY95];)g(see)i(Section)f(3.)f(Ho)o(w)o(ev)o(er,)340 2282 y(w)o(e)j(will)f(indicate)g(wh)o(y)h(this)f(tec)o(hnique)i(is)f (not)f(su\016cien)o(t)h(to)g(pro)o(v)o(e)g(the)g(general)g(case.)340 2332 y(F)m(urthermore,)e(w)o(e)f(will)g(p)q(ose)h(t)o(w)o(o)f(op)q(en)i (questions.)f(An)f(a\016rmativ)o(e)f(answ)o(er)i(to)g(one)g(of)340 2382 y(them)g(w)o(ould)g(pro)o(v)o(e)g(decidabilit)o(y)g(of)g (E-language)f(equiv)n(alence.)i(Due)f(to)h(space)g(limita-)340 2432 y(tions,)f(some)f(of)g(the)h(pro)q(ofs)g(had)g(to)g(b)q(e)g (omitted)f(in)g(this)h(extended)i(abstract.)e(The)h(full)p eop %%Page: 3 3 3 2 bop 183 194 a Fq(v)o(ersion)12 b(of)g(the)h(pap)q(er)g(can)g(b)q(e) g(found)f(in)g([OU95].)f(F)m(or)i(a)f(nice)h(in)o(tro)q(duction)f(to)g (patterns)183 244 y(and)17 b(reasons)i(wh)o(y)f(they)g(are)g(of)f(in)o (terest)i(in)f(formal)d(language)i(theory)m(,)g(the)i(reader)g(is)183 293 y(referred)14 b(to)e([Sal94)n(,)g(Sal95)n(].)g(Asp)q(ects)i(of)d (inductiv)o(e)h(inference)i(and)e(the)h(theory)f(of)g(learn-)183 343 y(ing)i({)g(although)g(closely)g(related)h(to)g(patterns)h({)e (will)f(not)i(b)q(e)g(discussed)h(in)f(this)f(pap)q(er,)183 393 y(details)f(can)h(b)q(e)h(found)e(in)h([Ang80b)o(,)f(IJ91,)g (KMU95],)g(for)h(instance.)245 444 y(The)g(pap)q(er)g(is)f(organized)g (as)h(follo)o(ws.)d(In)i(Section)h(2,)f(basic)g(de\014nitions)g(are)h (recalled)183 494 y(and)9 b(in)g(Section)g(3)h(our)f(\014rst)h(results) h(are)e(presen)o(ted.)i(Section)f(4)f(explains)g(the)h(normal)d(form) 183 543 y(approac)o(h,)15 b(while)g(Section)h(5)f(con)o(tains)h (decidabilit)o(y)e(results)j(based)f(on)g(normal)d(forms.)183 593 y(Finally)m(,)h(in)i(Section)h(6)f(it)h(is)f(sho)o(wn)h(that)g(in)f (con)o(trast)h(to)g(what)f(has)h(b)q(een)h(claimed)d(in)183 643 y([DF96)n(],)e(the)i(recen)o(t)g(approac)o(h)f(of)g(D\023)-21 b(an)o(yi)12 b(and)i(F)q(\177)-22 b(ul\177)h(op)13 b(do)q(es)i(not)f (solv)o(e)f(the)i(problem.)183 782 y Fk(2)56 b(Basic)18 b(De\014nitions)183 887 y Fq(In)d(the)h(sequel,)g(w)o(e)g(use)g (standard)g(terminology)d(and)i(assume)g(that)h Fj(\006)i Fq(and)d Fj(V)25 b Fq(are)16 b(t)o(w)o(o)183 936 y(disjoin)o(t)g (alphab)q(ets.)i(Elemen)o(ts)f(of)g Fj(\006)j Fq(are)e(called)f Fg(terminals)g Fq(\(or)h Fg(c)n(onstants)p Fq(\))g(and)f(ele-)183 986 y(men)o(ts)9 b(of)h Fj(V)19 b Fq(are)11 b(called)f Fg(variables)p Fq(.)f(Usually)m(,)g(0)p Fj(;)e Fq(1)p Fj(;)g(a;)g(b;)g(c)g Fq(will)i(denote)i(constan)o(ts,)f(whereas)183 1036 y Fj(x;)d(y)q(;)g(z)r(;)g(x)330 1042 y Fp(1)347 1036 y Fj(;)g(:)g(:)g(:)12 b Fq(will)h(stand)i(for)f(v)n(ariables.)f (An)o(y)i(w)o(ord)f Fj(\013)g Fq(o)o(v)o(er)g(the)h(union)f Fj(\006)f Fi([)c Fj(V)24 b Fq(is)14 b(said)183 1086 y(to)g(b)q(e)h(a)g Fg(p)n(attern)p Fq(.)f(The)h(set)g(of)f(v)n(ariables)g(app)q(earing)h (in)f Fj(\013)g Fq(will)f(b)q(e)j(denoted)f(b)o(y)g Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\).)183 1136 y(A)j Fg(substitution)f Fj(\033)i Fq(is)f(a)f(mapping)f(from)g Fj(V)27 b Fq(to)18 b(\()p Fj(\006)d Fi([)c Fj(V)f Fq(\))1120 1121 y Ff(\003)1139 1136 y Fq(.)17 b(Ev)o(ery)h(substitution)g Fj(\033)h Fq(ex-)183 1185 y(tends)f(uniquely)e(to)h(a)g Fg(morphism)g Fj(h)f Fq(:)h(\()p Fj(\006)d Fi([)d Fj(V)e Fq(\))975 1170 y Ff(\003)1011 1185 y Fi(!)16 b Fq(\()p Fj(\006)f Fi([)c Fj(V)e Fq(\))1220 1170 y Ff(\003)1239 1185 y Fq(,)17 b(where)h Fj(h)p Fq(\()p Fj(a)p Fq(\))f(=)g Fj(a)g Fq(for)183 1235 y(ev)o(ery)i Fj(a)g Fi(2)f Fj(\006)j Fq(and)d Fj(h)p Fq(\()p Fj(x)p Fq(\))h(=)g Fj(\033)q Fq(\()p Fj(x)p Fq(\))g(for)f(ev)o (ery)h Fj(x)g Fi(2)f Fj(V)10 b Fq(.)18 b(Con)o(v)o(ersely)m(,)f(ev)o (ery)i(morphism)183 1285 y Fj(h)d Fq(:)g(\()p Fj(\006)e Fi([)c Fj(V)g Fq(\))401 1270 y Ff(\003)436 1285 y Fi(!)16 b Fq(\()p Fj(\006)e Fi([)d Fj(V)e Fq(\))644 1270 y Ff(\003)680 1285 y Fq(with)17 b Fj(h)p Fq(\()p Fj(a)p Fq(\))f(=)h Fj(a)f Fq(for)h(ev)o(ery)g Fj(a)f Fi(2)g Fj(\006)k Fq(can)d(b)q(e)g (view)o(ed)g(as)g(a)183 1335 y(substitution.)11 b(In)h(the)h(sequel,)f (w)o(e)g(will)e(iden)o(tify)h(a)h(substitution)g(with)g(its)g(corresp)q (onding)183 1385 y(morphism)k(that)k(k)o(eeps)h(terminals)d(\014xed.)i (Henceforth)h Fj(\033)o(;)7 b(\027;)g(f)r(;)g(g)q(;)g(h)18 b Fq(will)g(denote)i(sub-)183 1434 y(stitutions.)e(A)g(bijectiv)o(e)g (substitution)h Fj(\033)h Fq(:)f Fj(V)28 b Fi(!)18 b Fj(V)28 b Fq(is)18 b(called)g(a)g Fg(variable)h(r)n(enaming)p Fq(.)183 1484 y(Tw)o(o)d(patterns)i Fj(\013)f Fq(and)f Fj(\014)k Fq(are)d(said)g(to)f(b)q(e)i Fg(identic)n(al)f(up)h(to)g (variable)f(r)n(enaming)g Fq(if)f(and)183 1534 y(only)g(if)h(there)i (is)f(a)f(v)n(ariable)f(renaming)g Fj(\033)j Fq(suc)o(h)f(that)g Fj(\013)f Fq(=)h Fj(\033)q Fq(\()p Fj(\014)r Fq(\).)h(A)e(pattern)i Fj(\013)e Fq(with)183 1584 y Fj(car)q(d)p Fq(\()p Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\)\))h(=)g Fj(k)13 b Fq(+)f(1)17 b(is)h(in)f Fg(c)n(anonic)n(al)i(form)e Fq(if)g(the)h(v)n(ariables)f(o) q(ccurring)h(in)g Fj(\013)f Fq(are)183 1634 y(precisely)e Fi(f)p Fj(x)398 1640 y Fp(0)416 1634 y Fj(;)7 b(x)459 1640 y Fp(1)476 1634 y Fj(;)g(x)519 1640 y Fp(2)537 1634 y Fj(;)g(:)g(:)g(:)e(;)i(x)654 1640 y Fh(k)674 1634 y Fi(g)13 b Fq(and)h(for)g(ev)o(ery)g Fj(i)h Fq(with)e(0)e Fi(\024)h Fj(i)g(<)g(k)q Fq(,)i(the)g(leftmost)f(o)q(ccur-)183 1684 y(rence)18 b(of)d Fj(x)367 1690 y Fh(i)397 1684 y Fq(in)h Fj(\013)g Fq(is)h(to)f(the)h(left)f(of)g(the)h(leftmost)e(o)q (ccurrence)k(of)d Fj(x)1308 1690 y Fh(i)p Fp(+1)1380 1684 y Fq(in)g Fj(\013)p Fq(.)f(Clearly)m(,)183 1733 y(ev)o(ery)e(pattern)h Fj(\013)e Fq(has)h(a)f(canonical)g(form)f Fj(\013)888 1718 y Ff(0)900 1733 y Fq(,)h(and)g(furthermore)h Fj(\013)g Fq(and)f Fj(\013)1378 1718 y Ff(0)1402 1733 y Fq(are)h(iden)o(tical)183 1783 y(up)f(to)h(v)n(ariable)f(renaming.)e (Moreo)o(v)o(er,)j(the)h(canonical)e(form)f(of)h(a)g(pattern)i(can)f(b) q(e)g(com-)183 1833 y(puted)j(in)g(linear)g(time.)e(Th)o(us,)i(it)g (can)g(b)q(e)h(tested)g(in)f(linear)g(time)e(whether)k(or)e(not)g(t)o (w)o(o)183 1883 y(patterns)g(are)g(iden)o(tical)e(up)i(to)f(v)n (ariable)f(renaming.)f(Giv)o(en)i(t)o(w)o(o)g(E-patterns)h Fj(\013)f Fq(and)g Fj(\014)r Fq(,)183 1933 y(it)g(is)g(not)g (di\016cult)f(to)h(pro)o(v)o(e)h(that)f(if)g(there)h(is)f(a)g (substitution)h Fj(h)f Fq(with)g Fj(h)p Fq(\()p Fj(\014)r Fq(\))f(=)g Fj(\013)p Fq(,)h(then)183 1982 y Fj(L)211 1988 y Fh(E)r(;\006)276 1982 y Fq(\()p Fj(\013)p Fq(\))d Fi(\022)f Fj(L)418 1988 y Fh(E)r(;\006)484 1982 y Fq(\()p Fj(\014)r Fq(\).)245 2033 y(Let)j Fj(\013)f Fq(b)q(e)h(a)f(pattern.)h Fj(\013)f Fq(has)g(a)g(unique)h(represen)o(tation)h Fj(\013)1188 2039 y Fp(0)1206 2033 y Fj(u)1230 2039 y Fp(1)1248 2033 y Fj(\013)1275 2039 y Fp(1)1293 2033 y Fj(u)1317 2039 y Fp(2)1343 2033 y Fj(:)7 b(:)g(:)e(\013)1425 2039 y Fh(m)p Ff(\000)p Fp(1)1499 2033 y Fj(u)1523 2039 y Fh(m)1554 2033 y Fj(\013)1581 2039 y Fh(m)1612 2033 y Fq(,)183 2083 y(where)19 b Fj(\013)334 2089 y Fp(0)352 2083 y Fj(;)7 b(\013)398 2089 y Fh(m)447 2083 y Fi(2)18 b Fj(V)527 2068 y Ff(\003)546 2083 y Fq(,)f Fj(\013)602 2089 y Fh(i)634 2083 y Fi(2)h Fj(V)714 2068 y Fp(+)759 2083 y Fq(for)g(0)g Fj(<)h(i)g(<)g(m)p Fq(,)f(and)g Fj(u)1176 2089 y Fh(i)1208 2083 y Fi(2)g Fj(\006)1288 2068 y Fp(+)1334 2083 y Fq(for)g(1)g Fi(\024)h Fj(i)g Fi(\024)g Fj(m)p Fq(,)183 2133 y Fj(m)c Fi(\025)g Fq(0.)g(W)m(e)h(call)f(the)h(sub)o(w)o(ords)h Fj(u)761 2139 y Fh(i)790 2133 y Fq(the)f Fg(terminal)g(se)n(gments)g Fq(of)g Fj(\013)p Fq(.)f(F)m(urthermore,)g(the)183 2183 y Fj(\013)210 2189 y Fh(i)239 2183 y Fq(are)i(called)e(the)i Fg(variable)g(se)n(gments)f Fq(of)f Fj(\013)p Fq(.)h(By)g(imp)q(osing)e (syn)o(tatic)i(restrictions,)h(w)o(e)183 2232 y(obtain)c(sp)q(ecial)i (patterns.)g(W)m(e)f(sa)o(y)g(that)h Fj(\013)f Fq(has)g Fg(indep)n(endent)j(variable)e(se)n(gments)f Fq(if)g(for)183 2282 y(all)g(1)g Fi(\024)h Fj(i)g(<)g(j)i Fi(\024)d Fj(m)i Fq(w)o(e)g(ha)o(v)o(e)g Fj(v)q(ar)q Fq(\()p Fj(\013)799 2288 y Fh(i)813 2282 y Fq(\))10 b Fi(\\)g Fj(v)q(ar)q Fq(\()p Fj(\013)983 2288 y Fh(j)1001 2282 y Fq(\))15 b(=)f Fi(;)p Fq(.)h(P)o(attern)i Fj(\013)e Fq(is)h Fg(line)n(ar)j Fq(if)c(ev)o(ery)183 2332 y(v)n(ariable)f Fj(x)g Fi(2)h Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))h(o)q(ccurs)h(exactly)e(once)i(in)e Fj(\013)p Fq(.)g(P)o(attern)h Fj(\013)g Fq(is)f(said)h(to)f(b)q(e)h Fg(terminal)183 2382 y(fr)n(e)n(e)d Fq(if)g(no)g(terminal)f(o)q(ccurs)j (in)f(it.)f(P)o(attern)h Fj(\013)g Fq(is)f(a)h Fg(one-variable)h(p)n (attern)e Fq(if)g(it)h(con)o(tains)183 2432 y(o)q(ccurrences)j(of)c (one)h(v)n(ariable)f(only)m(.)p eop %%Page: 4 4 4 3 bop 340 194 a Fk(3)56 b(Preliminary)16 b(Results)340 281 y Fq(On)11 b(the)f(one)h(hand,)e(Jiang)h Fg(et)h(al.)f Fq([JSSY95)o(])g(ha)o(v)o(e)g(sho)o(wn)g(that)g(the)h(inclusion)e (problem)g(for)340 331 y(E-pattern)i(languages)f(is)g(in)f(general)i (undecidable.)f(On)g(the)h(other)f(hand,)g(this)g(problem)e(is)340 381 y(decidable)k(for)g(terminal)e(free)i(patterns;)g(see)h([JSSY95].)e (Consequen)o(tly)m(,)g(the)h(E-language)340 430 y(equiv)n(alence)g (problem)e(for)h(terminal)f(free)i(patterns)g(is)g(decidable.)f (Despite)h(the)g(fact)f(that)340 480 y(the)h(inclusion)e(problem)f(for) h(general)h(E-pattern)h(languages)e(is)g(undecidable,)h(it)f(migh)o(t)f (b)q(e)340 530 y(the)16 b(case)g(that)g(the)f(decidabilit)o(y)f(of)h (the)h(equiv)n(alence)f(problem)f(for)h(general)g(E-pattern)340 580 y(languages)i(can)g(b)q(e)g(pro)o(v)o(ed)g(b)o(y)g(sho)o(wing)f (the)i(decidabilit)o(y)e(of)g(the)h(inclusion)g(problem)340 630 y(for)e(certain)h(E-patterns.)h(This)e(follo)o(ws)f(from)f(the)j (follo)o(wing)d(theorem)i(o)o(wing)g(to)g(Jiang)340 679 y Fg(et)g(al.)f Fq([JKS)535 664 y Fp(+)562 679 y Fq(94,)f(JSSY95].)340 750 y Fe(Theorem)7 b(1.)21 b Fg(L)n(et)15 b Fj(\013;)7 b(\014)14 b Fi(2)f Fq(\()p Fj(\006)f Fi([)d Fj(V)h Fq(\))936 735 y Fp(+)963 750 y Fg(.)16 b(Mor)n(e)n(over,)e(let)h Fj(\013)d Fq(=)h Fj(\013)1357 756 y Fp(0)1375 750 y Fj(u)1399 756 y Fp(1)1418 750 y Fj(\013)1445 756 y Fp(1)1463 750 y Fj(u)1487 756 y Fp(2)1512 750 y Fj(:)7 b(:)g(:)e(\013)1594 756 y Fh(m)p Ff(\000)p Fp(1)1668 750 y Fj(u)1692 756 y Fh(m)1723 750 y Fj(\013)1750 756 y Fh(m)340 800 y Fg(and)19 b Fj(\014)h Fq(=)e Fj(\014)540 806 y Fp(0)559 800 y Fj(v)579 806 y Fp(1)597 800 y Fj(\014)620 806 y Fp(1)640 800 y Fj(v)660 806 y Fp(2)685 800 y Fj(:)7 b(:)g(:)f(\014)764 806 y Fh(n)p Ff(\000)p Fp(1)829 800 y Fj(v)849 806 y Fh(n)872 800 y Fj(\014)895 806 y Fh(n)936 800 y Fg(b)n(e)18 b(their)f(unique)i(r)n(epr)n(esentations.)f(If)f Fj(L)1607 806 y Fh(E)r(;\006)1673 800 y Fq(\()p Fj(\013)p Fq(\))g(=)340 850 y Fj(L)368 856 y Fh(E)r(;\006)434 850 y Fq(\()p Fj(\014)r Fq(\))d Fg(and)g Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))e Fi(\025)g Fq(3)p Fg(,)h(then)g Fj(m)f Fq(=)g Fj(n)h Fg(and)h Fj(u)1158 856 y Fh(i)1183 850 y Fq(=)e Fj(v)1247 856 y Fh(i)1274 850 y Fg(for)h Fq(1)e Fi(\024)h Fj(i)g Fi(\024)g Fj(m)p Fg(.)h(If)g Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))f Fi(\025)340 899 y Fq(4)p Fg(,)j(then)g(it)f(further)g(fol)r(lows)g Fj(L)827 905 y Fh(E)r(;\006)893 899 y Fq(\()p Fj(\013)936 905 y Fh(i)949 899 y Fq(\))e(=)g Fj(L)1049 905 y Fh(E)r(;\006)1114 899 y Fq(\()p Fj(\014)1153 905 y Fh(i)1168 899 y Fq(\))j Fg(for)f Fq(0)d Fi(\024)h Fj(i)g Fi(\024)g Fj(m)p Fg(.)340 970 y Fq(Again,)k(the)i(assumption)f Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))g Fi(\025)h Fq(3)f(is)g(crucial;)g(see)i(Example)d(1.)g (In)i(view)f(of)g(the)340 1020 y(ab)q(o)o(v)o(e)d(theorem,)f(w)o(e)h (in)o(tro)q(duce)h(the)f(follo)o(wing)e(notion.)340 1091 y Fe(De\014nition)t(2.)21 b Fq(Tw)o(o)c(patterns)h Fj(\013)f Fq(and)g Fj(\014)i Fq(are)f(called)f Fg(similar)f Fq(if)g(and)h(only)f (if)g(in)h(their)340 1140 y(unique)c(represen)o(tations)i(the)f(resp)q (ectiv)o(e)h(terminal)d(segmen)o(ts)h(coincide,)f(that)i(is)e(to)h(sa)o (y)m(,)340 1190 y Fj(\013)f Fq(=)f Fj(\013)449 1196 y Fp(0)468 1190 y Fj(u)492 1196 y Fp(1)510 1190 y Fj(\013)537 1196 y Fp(1)555 1190 y Fj(u)579 1196 y Fp(2)604 1190 y Fj(:)c(:)g(:)f(\013)687 1196 y Fh(m)p Ff(\000)p Fp(1)760 1190 y Fj(u)784 1196 y Fh(m)816 1190 y Fj(\013)843 1196 y Fh(m)888 1190 y Fq(and)13 b Fj(\014)i Fq(=)c Fj(\014)1072 1196 y Fp(0)1091 1190 y Fj(u)1115 1196 y Fp(1)1134 1190 y Fj(\014)1157 1196 y Fp(1)1176 1190 y Fj(u)1200 1196 y Fp(2)1225 1190 y Fj(:)c(:)g(:)f(\014)1304 1196 y Fh(m)p Ff(\000)p Fp(1)1378 1190 y Fj(u)1402 1196 y Fh(m)1433 1190 y Fj(\014)1456 1196 y Fh(m)1488 1190 y Fq(.)340 1311 y Fe(Op)q(en)15 b(question)f(1:)g Fq(Is)g(the)h(inclusion)e (problem)f(decidable)j(for)e(similar)e(E-patterns?)340 1410 y(If)19 b(the)g(answ)o(er)h(w)o(as)f(p)q(ositiv)o(e)f(in)h(case)g Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))i Fi(\025)f Fq(3,)e(then)h(the)h (decidabilit)o(y)d(of)i(the)340 1460 y(equiv)n(alence)f(problem)d(for)i (general)g(E-pattern)h(languages)e(w)o(ould)h(follo)o(w:)d(Giv)o(en)j (pat-)340 1510 y(terns)g Fj(\013)d Fq(=)g Fj(\013)560 1516 y Fp(0)578 1510 y Fj(u)602 1516 y Fp(1)621 1510 y Fj(\013)648 1516 y Fp(1)666 1510 y Fj(u)690 1516 y Fp(2)715 1510 y Fj(:)7 b(:)g(:)e(\013)797 1516 y Fh(m)p Ff(\000)p Fp(1)871 1510 y Fj(u)895 1516 y Fh(m)926 1510 y Fj(\013)953 1516 y Fh(m)1000 1510 y Fq(and)15 b Fj(\014)i Fq(=)d Fj(\014)1191 1516 y Fp(0)1210 1510 y Fj(v)1230 1516 y Fp(1)1249 1510 y Fj(\014)1272 1516 y Fp(1)1291 1510 y Fj(v)1311 1516 y Fp(2)1337 1510 y Fj(:)7 b(:)g(:)e(\014)1415 1516 y Fh(n)p Ff(\000)p Fp(1)1480 1510 y Fj(v)1500 1516 y Fh(n)1523 1510 y Fj(\014)1546 1516 y Fh(n)1569 1510 y Fq(,)15 b(\014rst)h(c)o(hec)o(k)340 1560 y(whether)h Fj(m)c Fq(=)g Fj(n)i Fq(and)g Fj(u)741 1566 y Fh(i)767 1560 y Fq(=)f Fj(v)833 1566 y Fh(i)862 1560 y Fq(for)g(1)f Fi(\024)g Fj(i)h Fi(\024)f Fj(m)p Fq(.)i(If)f(not,)g(then)i Fj(L)1393 1566 y Fh(E)r(;\006)1458 1560 y Fq(\()p Fj(\013)p Fq(\))e Fi(6)p Fq(=)f Fj(L)1604 1566 y Fh(E)r(;\006)1669 1560 y Fq(\()p Fj(\014)r Fq(\).)j(If)340 1609 y(so,)e(then)g(decide)h Fj(L)652 1615 y Fh(E)r(;\006)718 1609 y Fq(\()p Fj(\013)p Fq(\))c(=)h Fj(L)860 1615 y Fh(E)r(;\006)926 1609 y Fq(\()p Fj(\014)r Fq(\))i(b)o(y)g(testing)g(inclusion)g(in)f(b)q(oth)h (directions.)403 1659 y(It)h(is)g(imp)q(ortan)o(t)f(to)h(note)h(that)g (the)g(undecidabilit)o(y)e(of)h(the)h(inclusion)f(problem)f(for)340 1709 y(general)i(E-pattern)g(languages)e(do)q(es,)h Fg(a)i(priori)p Fq(,)c(not)i(imply)e(the)i(undecidabilit)o(y)f(of)h(the)340 1759 y(inclusion)i(problem)e(for)i(similar)d(E-patterns.)k(This)f(is)g (b)q(ecause)h(the)g(patterns)g(used)g(in)340 1809 y(the)d (undecidabilit)o(y)f(pro)q(of)g(of)g([JSSY95)o(])g(are)h(not)g (similar.)c(And)k(in)f(fact,)g(w)o(e)h(can)f(pro)o(v)o(e)340 1859 y(that)g(the)g(inclusion)f(problem)f(for)h(similar)f(E-patterns)i (is)g(decidable)g(pro)o(vided)f(that)h(the)340 1908 y(alphab)q(et)g Fj(\006)j Fq(con)o(tains)d(t)o(w)o(o)f(constan)o(ts)i(not)f(o)q (ccurring)g(in)g(the)g(patterns.)340 1979 y Fe(De\014nition)t(3.)21 b Fq(Let)14 b Fj(V)21 b Fq(=)12 b Fi(f)p Fj(x)821 1985 y Fp(1)839 1979 y Fj(;)7 b(:)g(:)g(:)e(;)i(x)956 1985 y Fh(n)977 1979 y Fi(g)13 b Fq(b)q(e)h(a)f(set)h(of)e(v)n(ariables)h (and)g Fj(\006)j Fq(b)q(e)d(an)g(alphab)q(et)340 2029 y(with)e Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))h Fi(\025)g Fq(2.)f(F)m(or)g(ev)o(ery)h(pair)f(of)g(letters)h Fj(a;)7 b(b)k Fq(in)g Fj(\006)r Fq(,)h Fj(a)f Fi(6)p Fq(=)h Fj(b)p Fq(,)f(and)g(an)g(in)o(teger)h Fj(k)g(>)g Fq(0,)340 2079 y(w)o(e)j(de\014ne)f(a)g(substitution)g Fj(\034)805 2085 y Fh(k)q(;a;b)890 2079 y Fq(:)d Fj(V)21 b Fi(!)11 b(f)p Fj(a;)c(b)p Fi(g)1112 2064 y Ff(\003)1143 2079 y Fq(b)o(y)568 2157 y Fj(\034)586 2163 y Fh(k)q(;a;b)658 2157 y Fq(\()p Fj(x)698 2163 y Fh(i)712 2157 y Fq(\))12 b(=)g Fj(ab)824 2139 y Fh(k)q Ff(\003)p Fh(i)p Fp(+1)915 2157 y Fj(aab)977 2139 y Fh(k)q Ff(\003)p Fh(i)p Fp(+2)1067 2157 y Fj(a)7 b(:)g(:)g(:)f(ab)1192 2139 y Fh(k)q Ff(\003)p Fp(\()p Fh(i)p Fp(+1\))1309 2157 y Fj(a;)29 b Fq(1)11 b Fi(\024)h Fj(i)g Fi(\024)g Fj(n:)340 2232 y Fe(Lemma)c(4.)21 b Fg(L)n(et)c Fj(\006)k Fg(b)n(e)d(an)g(alphab)n(et)g(and)h(let)e Fj(\013;)7 b(\014)18 b Fi(2)f Fq(\()p Fj(\006)d Fi([)d Fj(V)f Fq(\))1394 2217 y Fp(+)1439 2232 y Fg(b)n(e)18 b(similar)f(p)n(atterns)340 2282 y(of)g(the)f(form)f Fj(\013)f Fq(=)g Fj(\013)676 2288 y Fp(0)694 2282 y Fj(u)718 2288 y Fp(1)737 2282 y Fj(\013)764 2288 y Fp(1)782 2282 y Fj(u)806 2288 y Fp(2)831 2282 y Fj(:)7 b(:)g(:)f(\013)914 2288 y Fh(m)p Ff(\000)p Fp(1)987 2282 y Fj(u)1011 2288 y Fh(m)1043 2282 y Fj(\013)1070 2288 y Fh(m)1117 2282 y Fg(and)17 b Fj(\014)f Fq(=)f Fj(\014)1308 2288 y Fp(0)1327 2282 y Fj(u)1351 2288 y Fp(1)1369 2282 y Fj(\014)1392 2288 y Fp(1)1411 2282 y Fj(u)1435 2288 y Fp(2)1461 2282 y Fj(:)7 b(:)g(:)e(\014)1539 2288 y Fh(m)p Ff(\000)p Fp(1)1613 2282 y Fj(u)1637 2288 y Fh(m)1669 2282 y Fj(\014)1692 2288 y Fh(m)1724 2282 y Fg(.)16 b(If)340 2332 y Fj(\006)22 b Fg(c)n(ontains)d(two)g(distinct)f(letters)g Fj(a)h Fg(and)h Fj(b)e Fg(which)h(do)g(not)h(o)n(c)n(cur)e(in)h Fj(\013)g Fg(and)h Fj(\014)r Fg(,)f(then)340 2382 y Fj(\034)358 2389 y Ff(j)p Fh(\014)q Ff(j)p Fh(;a;b)453 2382 y Fq(\()p Fj(\013)p Fq(\))i Fi(2)f Fj(L)609 2388 y Fh(E)r(;\006)674 2382 y Fq(\()p Fj(\014)r Fq(\))h Fg(if)f(and)g(only)h(if)e(ther)n(e)g (exists)h(a)g(substitution)g Fj(h)h Fq(:)f Fj(v)q(ar)q Fq(\()p Fj(\014)r Fq(\))i Fi(!)340 2432 y Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))462 2417 y Ff(\003)497 2432 y Fg(such)15 b(that)g Fj(h)p Fq(\()p Fj(\014)r Fq(\))d(=)g Fj(\013)p Fg(.)p eop %%Page: 5 5 5 4 bop 183 194 a Fg(Pr)n(o)n(of.)20 b Fq(The)e Fg(if)f Fq(part)h(is)f(trivially)f(true.)i(The)g Fg(only)h(if)e Fq(part)h(can)f(b)q(e)i(pro)o(v)o(ed)f(similar)d(to)183 244 y(Lemma)9 b(7.1)j(of)g([JSSY95])g(as)g(follo)o(ws.)f(Let)i Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))f(=)g Fi(f)p Fj(x)1109 250 y Fp(1)1127 244 y Fj(;)7 b(:)g(:)g(:)e(;)i(x)1244 250 y Fh(n)1265 244 y Fi(g)13 b Fq(and)f Fj(k)g Fq(=)g Fi(j)p Fj(\014)r Fi(j)p Fq(.)g(Since)183 293 y Fj(\034)201 299 y Fh(k)q(;a;b)274 293 y Fq(\()p Fj(\013)p Fq(\))g Fi(2)g Fj(L)413 299 y Fh(E)r(;\006)479 293 y Fq(\()p Fj(\014)r Fq(\),)j(there)h(is)e(a)g Fj(\027)h Fq(:)d Fj(v)q(ar)q Fq(\()p Fj(\014)r Fq(\))i Fi(!)e Fj(\006)1029 278 y Ff(\003)1064 293 y Fq(suc)o(h)j(that)f Fj(\027)s Fq(\()p Fj(\014)r Fq(\))f(=)g Fj(\034)1405 299 y Fh(k)q(;a;b)1478 293 y Fq(\()p Fj(\013)p Fq(\).)h(F)m(or)183 343 y(ev)o(ery)j Fj(x)g Fi(2)f Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\),)h Fj(\034)549 349 y Fh(k)q(;a;b)622 343 y Fq(\()p Fj(x)p Fq(\))g(consists)h(of)e Fj(k)i Fq(segmen)o(ts)f(of)f(the)h(form)f Fj(ab)1387 328 y Fh(j)1404 343 y Fj(a)p Fq(.)g(Th)o(us,)h(for)183 393 y(ev)o(ery)c Fj(x)315 399 y Fh(i)340 393 y Fi(2)e Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\),)i(there)g(is)g(at)f(least)h(one)g (segmen)o(t)f Fj(ab)1090 378 y Fh(j)1104 382 y Fd(i)1118 393 y Fj(a)p Fq(,)g Fj(k)c Fi(\003)e Fj(i)g Fq(+)g(1)13 b Fi(\024)f Fj(j)1374 399 y Fh(i)1399 393 y Fi(\024)g Fj(k)7 b Fi(\003)f Fq(\()p Fj(i)g Fq(+)g(1\),)183 443 y(suc)o(h)20 b(that)g(none)g(of)g(the)g(app)q(earance\(s\))i(of)d(this) h(segmen)o(t)g(in)f Fj(\027)s Fq(\()p Fj(\014)r Fq(\))h(is)g(split)f(b) o(y)h(an)o(y)183 493 y(partition)15 b(of)g Fj(\027)s Fq(\()p Fj(\014)r Fq(\))h(in)o(to)f Fj(\027)s Fq(\()p Fj(\014)655 478 y Ff(0)667 493 y Fq(\))h(and)f Fj(\027)s Fq(\()p Fj(\014)846 478 y Ff(00)867 493 y Fq(\))h(where)h Fj(\014)h Fq(=)d Fj(\014)1134 478 y Ff(0)1146 493 y Fj(\014)1171 478 y Ff(00)1193 493 y Fq(.)h(F)m(or)f(ev)o(ery)i Fj(x)d Fi(2)h Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\),)183 542 y(w)o(e)f(c)o(ho)q (ose)g(one)g(suc)o(h)h(segmen)o(t)e(to)h(b)q(e)g(the)h(anc)o(hor)f (segmen)o(t)f(of)g Fj(x)h Fq(in)f Fj(\034)1330 548 y Fh(k)q(;a;b)1403 542 y Fq(\()p Fj(\013)p Fq(\))h(w.r.t.)e Fj(\014)r Fq(.)183 592 y(W)m(e)h(also)g(sa)o(y)h(that)g(this)g(segmen)o (t)g(anc)o(hors)g Fj(x)p Fq(.)245 642 y(Supp)q(ose)k(there)g(is)f(a)g (v)n(ariable)f Fj(y)j Fi(2)d Fj(v)q(ar)q Fq(\()p Fj(\014)r Fq(\))i(suc)o(h)g(that)f Fj(\027)s Fq(\()p Fj(y)q Fq(\))h(con)o(tains)f (a)f(terminal)183 692 y(di\013eren)o(t)h(from)d Fj(a)i Fq(and)g Fj(b)p Fq(,)g(sa)o(y)g Fj(c)p Fq(,)g(o)q(ccurring)g(in)g Fj(\014)r Fq(.)g(Let)h Fj(c)f Fq(o)q(ccur)i Fj(l)q Fq(-times)d(in)h Fj(\014)r Fq(.)g(Then)h Fj(c)183 742 y Fq(app)q(ears)12 b(more)f(than)h Fj(l)q Fq(-times)f(in)h Fj(\027)s Fq(\()p Fj(\014)r Fq(\).)f(Apparen)o(tly)m(,)g Fj(c)h Fq(also)f(o)q(ccurs)j Fj(l)q Fq(-times)d(in)g Fj(\034)1480 748 y Fh(k)q(;a;b)1553 742 y Fq(\()p Fj(\013)p Fq(\).)183 791 y(This,)18 b(ho)o(w)o(ev)o(er,)i (con)o(tradicts)g(the)g(equalit)o(y)e Fj(\027)s Fq(\()p Fj(\014)r Fq(\))j(=)g Fj(\034)1103 797 y Fh(k)q(;a;b)1176 791 y Fq(\()p Fj(\013)p Fq(\).)e(So)g(for)g(an)o(y)g(v)n(ariable)183 841 y Fj(y)e Fi(2)f Fj(v)q(ar)q Fq(\()p Fj(\014)r Fq(\),)h(it)g(follo)o (ws)d Fj(\027)s Fq(\()p Fj(y)q Fq(\))j Fi(2)e(f)p Fj(a;)7 b(b)p Fi(g)834 826 y Ff(\003)852 841 y Fq(.)16 b(Supp)q(ose)i(that)e Fj(y)i Fq(o)q(ccurs)g(in)f Fj(\014)1382 847 y Fh(i)1396 841 y Fq(,)f(0)f Fj(<)i(i)f(<)g(m)183 891 y Fq(\(the)g(cases)g Fj(i)e Fq(=)g(0)h(and)g Fj(i)f Fq(=)g Fj(m)h Fq(are)h(similar)c(and)j (simpler\).)f(Let)i Fj(c)f Fq(b)q(e)g(the)h(last)f(letter)h(of)183 941 y Fj(u)207 947 y Fh(i)236 941 y Fq(and)f Fj(d)h Fq(the)g(\014rst)h (letter)f(of)f Fj(u)702 947 y Fh(i)p Fp(+1)774 941 y Fq(\()p Fj(c)f Fq(=)h Fj(d)h Fq(is)f(p)q(ossible\).)h(Let)g(the)g(last) g(letter)h(of)e Fj(u)1552 947 y Fh(i)1581 941 y Fq(b)q(e)183 991 y(the)g Fj(p)p Fq(th)h(app)q(earance)g(of)f Fj(c)g Fq(and)g(the)h(\014rst)g(letter)g(of)e Fj(u)1058 997 y Fh(i)p Fp(+1)1129 991 y Fq(b)q(e)i(the)g Fj(q)q Fq(th)f(app)q (earance)h(of)f Fj(d)183 1041 y Fq(in)i Fj(\014)r Fq(.)g(Since)h Fj(\027)s Fq(\()p Fj(y)q Fq(\))g(do)q(es)g(not)f(con)o(tain)g(an)o(y)g (letter)h(from)e(a)h(terminal)f(segmen)o(t,)g Fj(\027)s Fq(\()p Fj(y)q Fq(\))i(is)183 1090 y(in)d(b)q(et)o(w)o(een)i(the)f Fj(p)p Fq(th)g(app)q(earance)h(of)e Fj(c)h Fq(and)f(the)i Fj(q)q Fq(th)f(app)q(earance)h(of)e Fj(d)g Fq(in)g Fj(\027)s Fq(\()p Fj(\014)r Fq(\).)h(This)183 1140 y(observ)n(ation)d(pla)o(ys)h (a)f(k)o(ey)h(r^)-21 b(ole)14 b(in)f(the)i(pro)q(of.)245 1190 y(W)m(e)k(de\014ne)h(a)f(substitution)h Fj(h)g Fq(:)g Fj(v)q(ar)q Fq(\()p Fj(\014)r Fq(\))i Fi(!)e Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))1126 1175 y Ff(\003)1165 1190 y Fq(as)g(follo)o(ws.)d(F)m(or)i(eac)o(h)h Fj(y)i Fi(2)183 1240 y Fj(v)q(ar)q Fq(\()p Fj(\014)r Fq(\),)14 b(let)637 1288 y Fj(ab)677 1271 y Fh(j)691 1275 y Fd(i)702 1281 y Fc(1)722 1288 y Fj(aab)784 1271 y Fh(j)798 1275 y Fd(i)809 1281 y Fc(2)829 1288 y Fj(a)7 b(:)g(:)g(:)e(ab)953 1271 y Fh(j)967 1275 y Fd(i)978 1279 y(r)998 1288 y Fj(a;)30 b(r)12 b Fi(\025)g Fq(0)p Fj(;)183 1359 y Fq(b)q(e)19 b(the)f(w)o(ord)h(obtained)f(from)e Fj(\027)s Fq(\()p Fj(y)q Fq(\))j(b)o(y)f(deleting)g(all)f(the)i(incomplete)e(segmen)o(ts) i(and)183 1409 y(segmen)o(ts)d(that)h(are)g(not)g(anc)o(hor)g(segmen)o (ts.)f(Note)h(that)g(the)g(indices)g Fj(i)1356 1415 y Fp(1)1375 1409 y Fj(;)7 b(i)1408 1415 y Fp(2)1427 1409 y Fj(;)g(:)g(:)g(:)t(;)g(i)1533 1415 y Fh(r)1568 1409 y Fq(are)183 1459 y(not)j(necessarily)h(distinct.)e(Hereb)o(y)i(a)f (segmen)o(t)g Fj(ab)979 1444 y Fh(j)993 1448 y Fd(i)1004 1452 y(s)1023 1459 y Fj(a)g Fq(anc)o(hors)h(a)e(v)n(ariable)g Fj(x)1409 1465 y Fh(i)1421 1469 y Fd(s)1450 1459 y Fi(2)j Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\),)183 1509 y(1)f Fi(\024)h Fj(i)273 1515 y Fh(s)302 1509 y Fi(\024)g Fj(n)p Fq(.)g(Then)i(w)o(e)f (de\014ne)h Fj(h)p Fq(\()p Fj(y)q Fq(\))e(=)g Fj(x)839 1515 y Fh(i)851 1519 y Fc(1)869 1509 y Fj(x)893 1515 y Fh(i)905 1519 y Fc(2)930 1509 y Fj(:)7 b(:)g(:)e(x)1009 1515 y Fh(i)1021 1519 y Fd(r)1039 1509 y Fq(.)12 b(Clearly)m(,)g Fj(h)p Fq(\()p Fj(\014)r Fq(\))g(=)g Fj(\013)g Fq(b)q(ecause)j(eac)o(h) 183 1558 y(app)q(earance)g(of)e Fj(x)h Fq(in)f Fj(\013)h Fq(has)g(exactly)g(one)g(anc)o(hor)g(segmen)o(t)f(w.r.t.)g Fj(\014)r Fq(.)183 1646 y Fe(Theorem)6 b(5.)21 b Fg(L)n(et)15 b Fj(\006)i Fg(b)n(e)e(an)g(alphab)n(et)g(and)h(let)e Fj(\013;)7 b(\014)13 b Fi(2)f Fq(\()p Fj(\006)f Fi([)e Fj(V)g Fq(\))1232 1631 y Fp(+)1275 1646 y Fg(b)n(e)15 b(similar)e(p)n(atterns.)183 1696 y(If)h Fj(\006)j Fg(c)n(ontains)f (two)e(distinct)g(c)n(onstants)h Fj(a)g Fg(and)g Fj(b)g Fg(not)g(o)n(c)n(curring)f(in)h Fj(\013)f Fg(and)h Fj(\014)r Fg(,)g(then)g(the)183 1746 y(fol)r(lowing)f(statements)h(ar)n(e)f(e)n (quivalent:)199 1826 y(1.)20 b Fj(L)281 1832 y Fh(E)r(;\006)347 1826 y Fq(\()p Fj(\013)p Fq(\))11 b Fi(\022)h Fj(L)489 1832 y Fh(E)r(;\006)555 1826 y Fq(\()p Fj(\014)r Fq(\))p Fg(.)199 1876 y(2.)20 b Fj(\034)271 1883 y Ff(j)p Fh(\014)q Ff(j)p Fh(;a;b)366 1876 y Fq(\()p Fj(\013)p Fq(\))11 b Fi(2)h Fj(L)504 1882 y Fh(E)r(;\006)569 1876 y Fq(\()p Fj(\014)r Fq(\))p Fg(.)199 1926 y(3.)20 b(Ther)n(e)15 b(exists)f(a)h(substitution)g Fj(h)d Fq(:)f Fj(v)q(ar)q Fq(\()p Fj(\014)r Fq(\))i Fi(!)e Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))1113 1911 y Ff(\003)1147 1926 y Fg(such)k(that)g Fj(h)p Fq(\()p Fj(\014)r Fq(\))e(=)e Fj(\013)p Fg(.)183 2014 y(Pr)n(o)n(of.)20 b Fq(The)d(implications)c(\(1\))j Fi(\))g Fq(\(2\))g(and)g(\(3\))g Fi(\))g Fq(\(1\))g(are)h(trivially)d (true.)j(\(2\))f Fi(\))g Fq(\(3\))183 2064 y(has)e(b)q(een)h(pro)o(v)o (ed)f(in)f(Lemma)e(4.)183 2152 y(Since)18 b(the)h(mem)o(b)q(ership)e (problem)g(is)h(decidable)g(\(see)i([Ang80a)o(,)d(JKS)1349 2137 y Fp(+)1377 2152 y Fq(94]\),)g(it)h(is)g(de-)183 2202 y(cidable)d(whether)i Fj(L)514 2208 y Fh(E)r(;\006)579 2202 y Fq(\()p Fj(\013)p Fq(\))d Fi(\022)h Fj(L)727 2208 y Fh(E)r(;\006)792 2202 y Fq(\()p Fj(\014)r Fq(\))h(for)f(t)o(w)o(o)g (similar)e(patterns)k Fj(a)e Fq(and)g Fj(b)h Fq(pro)o(vided)183 2252 y(there)f(are)f Fj(a;)7 b(b)k Fi(2)g Fj(\006)17 b Fq(whic)o(h)c(do)h(not)g(app)q(ear)g(in)g Fj(\013)f Fq(and)h Fj(\014)r Fq(.)183 2332 y Fe(Corollary)6 b(6.)21 b Fg(If)c Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))g Fi(\025)f Fq(3)p Fg(,)h(then)g(the)h(e)n(quivalenc)n(e)g(pr)n(oblem)f(for)f(E-p)n (attern)i(lan-)183 2382 y(guages)f(is)e(de)n(cidable)i(whenever)f(the)g (underlying)h(alphab)n(et)f Fj(\006)j Fg(c)n(ontains)e(two)e(terminals) 183 2432 y(that)g(do)g(not)g(o)n(c)n(cur)g(in)g(the)g(p)n(atterns.)p eop %%Page: 6 6 6 5 bop 340 194 a Fq(Notice)17 b(that)g(the)g(inclusion)f(problem)f (\(and)h(hence)i(the)f(equiv)n(alence)g(problem\))e(for)h(E-)340 244 y(pattern)f(languages)e(is)h(particularly)f(decidable)h(if)g Fj(\006)i Fq(is)e(in\014nite.)403 293 y(W)m(e)h(next)i(discuss)g(the)f (limits)e(of)h(the)h(ab)q(o)o(v)o(e)g(pro)q(of)f(tec)o(hnique.)i (Clearly)m(,)d(w)o(e)i(w)o(ould)340 343 y(lik)o(e)11 b(to)g(get)g(rid)g(of)g(the)h(anno)o(ying)e(condition)g(\\)p Fj(\006)k Fq(has)d(to)g(con)o(tain)g(t)o(w)o(o)g(distinct)g(constan)o (ts)340 393 y Fj(a)k Fq(and)f Fj(b)g Fq(that)h(do)f(not)g(o)q(ccur)i (in)e Fj(\013)g Fq(and)g Fj(\014)r Fq(".)g(The)h(crucial)g(p)q(oin)o(t) f(is)g(that)g(this)h(condition)340 443 y(enabled)g(us)f(to)g(infer)f (the)i(second)g(implication)c(b)q(elo)o(w)i(\(cf.)h(Lemma)d(4\))501 523 y Fj(L)529 529 y Fh(E)r(;\006)595 523 y Fq(\()p Fj(\013)p Fq(\))g Fi(\022)h Fj(L)737 529 y Fh(E)r(;\006)803 523 y Fq(\()p Fj(\014)r Fq(\))g Fi(\))f Fj(\034)943 530 y Ff(j)p Fh(\014)q Ff(j)p Fh(;a;b)1038 523 y Fq(\()p Fj(\013)p Fq(\))g Fi(2)g Fj(L)1175 529 y Fh(E)r(;\006)1241 523 y Fq(\()p Fj(\014)r Fq(\))h Fi(\))f(9)p Fj(h)h Fq(:)f Fj(h)p Fq(\()p Fj(\014)r Fq(\))h(=)g Fj(\013:)340 604 y Fq(Ho)o(w)o(ev)o(er,)f(if)f(there)h(are)g(no)g(extra)g(constan)o(ts,) g(then)g(it)f(is)h(not)f(clear)h(at)f(all)g(whic)o(h)g(enco)q(ding)340 654 y Fj(\034)358 661 y Ff(j)p Fh(\014)q Ff(j)p Fh(;l)418 665 y Fc(1)435 661 y Fh(;l)455 665 y Fc(2)474 654 y Fq(\()p Fj(\013)p Fq(\))16 b(should)g(b)q(e)h(tak)o(en,)e(i.e.,)g(whic)o(h)h (constan)o(ts)h Fj(l)1268 660 y Fp(1)1287 654 y Fj(;)7 b(l)1318 660 y Fp(2)1352 654 y Fi(2)15 b Fj(\006)r(;)23 b(l)1476 660 y Fp(1)1510 654 y Fi(6)p Fq(=)16 b Fj(l)1570 660 y Fp(2)1605 654 y Fq(should)g(b)q(e)340 703 y(c)o(hosen)g(to)f (enco)q(de)h(the)f(v)n(ariables)f(in)h Fj(\013)p Fq(.)f(A)h(p)q (ossible)g(solution)f(w)o(ould)g(b)q(e)h(to)g(generalize)340 753 y(the)h(ab)q(o)o(v)o(e)g(metho)q(d:)e(Find)h(a)g(\014nite)h(test)g (set)g Fj(F)k Fi(\032)14 b Fj(L)1210 759 y Fh(E)r(;\006)1276 753 y Fq(\()p Fj(\013)p Fq(\))h(suc)o(h)h(that)g Fj(F)j Fi(\032)c Fj(L)1658 759 y Fh(E)r(;\006)1723 753 y Fq(\()p Fj(\014)r Fq(\))340 803 y(implies)h(the)j(existence)g(of)f(a)f (substitution)h Fj(h)g Fq(suc)o(h)g(that)g Fj(h)p Fq(\()p Fj(\014)r Fq(\))h(=)g Fj(\013)p Fq(.)e(A)h(v)o(ery)g(natural)340 853 y(candidate)c(w)o(ould)g(b)q(e)g(the)h(set)f(of)g(all)e(enco)q (dings,)i(i.e.,)f(the)h(set)719 933 y Fj(F)j Fq(=)12 b Fi(f)p Fj(\034)846 940 y Ff(j)p Fh(\014)q Ff(j)p Fh(;l)906 944 y Fc(1)923 940 y Fh(;l)943 944 y Fc(2)961 933 y Fq(\()p Fj(\013)p Fq(\))h Fi(j)f Fj(l)1069 939 y Fp(1)1088 933 y Fj(;)7 b(l)1119 939 y Fp(2)1149 933 y Fi(2)k Fj(\006)r(;)19 b(l)1265 939 y Fp(1)1295 933 y Fi(6)p Fq(=)12 b Fj(l)1351 939 y Fp(2)1370 933 y Fi(g)p Fj(:)340 1014 y Fq(But)18 b(the)g(next)g(example)e(sho)o(ws)i(that)f(this)h(set)g(is)f(not)h (su\016cien)o(t)f(when)h Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))g(=)g(3)340 1064 y(\(the)d(situation)e(migh)o(t)f(b)q(e)i (di\013eren)o(t)h(for)f Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))e Fi(\025)g Fq(4\).)340 1142 y Fg(Example)c(2.)21 b Fq(Let)16 b Fj(\006)h Fq(=)f Fi(f)p Fj(a;)7 b(b;)g(c)p Fi(g)p Fq(,)13 b Fj(\013)h Fq(=)h Fj(y)1000 1148 y Fp(1)1026 1142 y Fj(a)7 b(y)1075 1148 y Fp(2)1101 1142 y Fj(b)g(y)1146 1148 y Fp(3)1165 1142 y Fj(y)1185 1148 y Fp(2)1204 1142 y Fj(y)1224 1148 y Fp(4)1259 1142 y Fq(and)15 b Fj(\014)j Fq(=)d Fj(z)1448 1148 y Fp(1)1474 1142 y Fj(a)7 b(z)1522 1148 y Fp(2)1547 1142 y Fj(b)g(z)1591 1148 y Fp(3)1610 1142 y Fj(z)1629 1148 y Fp(2)1648 1142 y Fq(.)15 b(There)340 1192 y(is)h(a)g(substitution)g Fj(f)k Fq(:)14 b Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))i Fi(!)e Fj(v)q(ar)q Fq(\()p Fj(\014)r Fq(\))1034 1177 y Ff(\003)1070 1192 y Fq(suc)o(h)j(that)f Fj(f)t Fq(\()p Fj(\013)p Fq(\))g(=)f Fj(\014)r Fq(.)h(Hence)i Fj(L)1611 1198 y Fh(E)r(;\006)1676 1192 y Fq(\()p Fj(\014)r Fq(\))e Fi(\022)340 1242 y Fj(L)368 1248 y Fh(E)r(;\006)434 1242 y Fq(\()p Fj(\013)p Fq(\).)g(The)h(opp)q(osite)g(inclusion)f(do)q (es)i(not)f(hold)f(b)q(ecause)i Fj(cacbcb)e Fi(2)g Fj(L)1578 1248 y Fh(E)r(;\006)1643 1242 y Fq(\()p Fj(\013)p Fq(\))h(but)340 1292 y Fj(cacbcb)f Fi(62)g Fj(L)540 1298 y Fh(E)r(;\006)605 1292 y Fq(\()p Fj(\014)r Fq(\).)i(And)f(indeed,)f(there)i(is)f(no)f (substitution)h Fj(g)h Fq(:)d Fj(v)q(ar)q Fq(\()p Fj(\014)r Fq(\))j Fi(!)e Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))1762 1276 y Ff(\003)340 1341 y Fq(suc)o(h)j(that)g Fj(g)q Fq(\()p Fj(\014)r Fq(\))h(=)f Fj(\013)p Fq(.)f(Despite)h(this)f(fact,)g (w)o(e)h(ha)o(v)o(e)f Fj(\034)1260 1348 y Ff(j)p Fh(\014)q Ff(j)p Fh(;l)1320 1352 y Fc(1)1337 1348 y Fh(;l)1357 1352 y Fc(2)1375 1341 y Fq(\()p Fj(\013)p Fq(\))h Fi(2)g Fj(L)1528 1347 y Fh(E)r(;\006)1593 1341 y Fq(\()p Fj(\014)r Fq(\))h(for)e(all)340 1391 y Fj(l)352 1397 y Fp(1)371 1391 y Fj(;)7 b(l)402 1397 y Fp(2)435 1391 y Fi(2)14 b Fj(\006)r(;)22 b(l)557 1397 y Fp(1)590 1391 y Fi(6)p Fq(=)15 b Fj(l)649 1397 y Fp(2)668 1391 y Fq(.)g(W)m(e)g(exemplify)f (this)i(b)o(y)f(sho)o(wing)g(\(i\))g Fj(\034)1337 1398 y Ff(j)p Fh(\014)q Ff(j)p Fh(;a;b)1432 1391 y Fq(\()p Fj(\013)p Fq(\))f Fi(2)g Fj(L)1575 1397 y Fh(E)r(;\006)1641 1391 y Fq(\()p Fj(\014)r Fq(\))i(and)340 1441 y(\(ii\))f Fj(\034)429 1448 y Ff(j)p Fh(\014)q Ff(j)p Fh(;c;a)524 1441 y Fq(\()p Fj(\013)p Fq(\))f Fi(2)g Fj(L)667 1447 y Fh(E)r(;\006)732 1441 y Fq(\()p Fj(\014)r Fq(\).)i(First)g(of)f(all)f (note)i(that)g Fj(\034)1232 1448 y Ff(j)p Fh(\014)q Ff(j)p Fh(;l)1292 1452 y Fc(1)1308 1448 y Fh(;l)1328 1452 y Fc(2)1347 1441 y Fq(\()p Fj(y)1383 1447 y Fh(i)1397 1441 y Fq(\))g(starts)g(with)f(a)h(pre\014x)340 1491 y Fj(l)352 1497 y Fp(1)371 1491 y Fj(l)383 1497 y Fp(2)413 1491 y Fq(and)11 b(ends)h(with)e(a)h(su\016x)g Fj(l)825 1497 y Fp(2)844 1491 y Fj(l)856 1497 y Fp(1)875 1491 y Fq(.)f(Hence)j Fj(\034)1036 1498 y Ff(j)p Fh(\014)q Ff(j)p Fh(;l)1096 1502 y Fc(1)1112 1498 y Fh(;l)1132 1502 y Fc(2)1151 1491 y Fq(\()p Fj(y)1187 1497 y Fh(i)1201 1491 y Fq(\))f(=)g Fj(l)1285 1497 y Fp(1)1304 1491 y Fj(l)1316 1497 y Fp(2)1335 1491 y Fj(w)1365 1497 y Fh(y)1382 1501 y Fd(i)1397 1491 y Fj(l)1409 1497 y Fp(2)1428 1491 y Fj(l)1440 1497 y Fp(1)1469 1491 y Fq(for)f(some)f(sub)o(w)o(ord)340 1541 y Fj(w)370 1547 y Fh(y)387 1551 y Fd(i)416 1541 y Fq(of)j Fj(\034)481 1548 y Ff(j)p Fh(\014)q Ff(j)p Fh(;l)541 1552 y Fc(1)558 1548 y Fh(;l)578 1552 y Fc(2)597 1541 y Fq(\()p Fj(y)633 1547 y Fh(i)647 1541 y Fq(\).)486 1621 y(\()p Fj(i)p Fq(\))35 b Fj(\034)585 1628 y Ff(j)p Fh(\014)q Ff(j)p Fh(;a;b)679 1621 y Fq(\()p Fj(\013)p Fq(\))12 b(=)g Fj(abw)864 1627 y Fh(y)881 1631 y Fc(1)898 1621 y Fj(ba)g(a)f(abw)1053 1627 y Fh(y)1070 1631 y Fc(2)1088 1621 y Fj(ba)g(b)g(abw)1238 1627 y Fh(y)1255 1631 y Fc(3)1273 1621 y Fj(ba)g(abw)1394 1627 y Fh(y)1411 1631 y Fc(2)1429 1621 y Fj(ba)g(abw)1550 1627 y Fh(y)1567 1631 y Fc(4)1585 1621 y Fj(ba:)340 1702 y Fq(De\014ne)k(the)f(substitution)h Fj(\027)h Fq(b)o(y)d Fj(\027)s Fq(\()p Fj(z)925 1708 y Fp(1)943 1702 y Fq(\))f(=)g Fj(\027)s Fq(\()p Fj(z)1074 1708 y Fp(2)1092 1702 y Fq(\))g(=)g Fj(\025)i Fq(and)585 1782 y Fj(\027)s Fq(\()p Fj(z)644 1788 y Fp(3)663 1782 y Fq(\))d(=)h Fj(w)764 1788 y Fh(y)781 1792 y Fc(1)799 1782 y Fj(ba)f(a)h(abw)954 1788 y Fh(y)971 1792 y Fc(2)988 1782 y Fj(ba)f(b)h(abw)1139 1788 y Fh(y)1156 1792 y Fc(3)1173 1782 y Fj(ba)g(abw)1295 1788 y Fh(y)1312 1792 y Fc(2)1329 1782 y Fj(ba)g(abw)1451 1788 y Fh(y)1468 1792 y Fc(4)1485 1782 y Fj(ba:)340 1863 y Fq(Then)j(clearly)f Fj(\027)s Fq(\()p Fj(\014)r Fq(\))d(=)h Fj(\034)736 1870 y Ff(j)p Fh(\014)q Ff(j)p Fh(;a;b)831 1863 y Fq(\()p Fj(\013)p Fq(\),)h(hence)i Fj(\034)1048 1870 y Ff(j)p Fh(\014)q Ff(j)p Fh(;a;b)1143 1863 y Fq(\()p Fj(\013)p Fq(\))c Fi(2)h Fj(L)1281 1869 y Fh(E)r(;\006)1346 1863 y Fq(\()p Fj(\014)r Fq(\).)478 1943 y(\()p Fj(ii)p Fq(\))35 b Fj(\034)591 1950 y Ff(j)p Fh(\014)q Ff(j)p Fh(;c;a)686 1943 y Fq(\()p Fj(\013)p Fq(\))12 b(=)f Fj(caw)870 1949 y Fh(y)887 1953 y Fc(1)905 1943 y Fj(ac)h(a)f(caw)1060 1949 y Fh(y)1077 1953 y Fc(2)1095 1943 y Fj(ac)g(b)h(caw)1246 1949 y Fh(y)1263 1953 y Fc(3)1280 1943 y Fj(ac)g(caw)1402 1949 y Fh(y)1419 1953 y Fc(2)1436 1943 y Fj(ac)g(caw)1558 1949 y Fh(y)1575 1953 y Fc(4)1593 1943 y Fj(ac:)340 2024 y Fq(No)o(w)20 b(de\014ne)h(the)g(substitution)g Fj(\027)h Fq(b)o(y)e Fj(\027)s Fq(\()p Fj(z)1049 2030 y Fp(1)1067 2024 y Fq(\))i(=)h Fj(caw)1230 2030 y Fh(y)1247 2034 y Fc(1)1264 2024 y Fj(ac)f(a)g(caw)1440 2030 y Fh(y)1457 2034 y Fc(2)1475 2024 y Fq(,)e Fj(\027)s Fq(\()p Fj(z)1566 2030 y Fp(2)1584 2024 y Fq(\))i(=)g Fj(c)e Fq(and)340 2074 y Fj(\027)s Fq(\()p Fj(z)399 2080 y Fp(3)418 2074 y Fq(\))11 b(=)h Fj(caw)559 2080 y Fh(y)576 2084 y Fc(3)594 2074 y Fj(ac)f(caw)715 2080 y Fh(y)732 2084 y Fc(2)750 2074 y Fj(ac)g(caw)871 2080 y Fh(y)888 2084 y Fc(4)906 2074 y Fj(a)p Fq(.)340 2152 y(Note)22 b(that)e(the)i(condition)e(of)g(ha)o(ving)f(t)o(w)o(o)i (extra)g(constan)o(ts)g(could)g(b)q(e)g(dropp)q(ed)h(in)340 2202 y(Lemma)14 b(4,)i(if)f(E-language)h(equiv)n(alence)g(w)o(as)h (preserv)o(ed)h(under)f(alphab)q(et)g(extensions,)340 2252 y(more)c(precisely)m(,)h(if)f(the)i(question)f(b)q(elo)o(w)f(w)o (ould)h(ha)o(v)o(e)f(an)h(answ)o(er)g(in)g(the)g(a\016rmativ)o(e.)340 2351 y Fe(Op)q(en)h(question)f(2:)g Fq(Do)q(es)g(the)h(equiv)n(alence:) 623 2432 y Fj(L)651 2438 y Fh(E)r(;\006)717 2432 y Fq(\()p Fj(\013)p Fq(\))c(=)h Fj(L)859 2438 y Fh(E)r(;\006)925 2432 y Fq(\()p Fj(\014)r Fq(\))47 b Fi(,)f Fj(L)1145 2438 y Fh(E)r(;\006)1209 2430 y Fb(0)1221 2432 y Fq(\()p Fj(\013)p Fq(\))12 b(=)g Fj(L)1364 2438 y Fh(E)r(;\006)1428 2430 y Fb(0)1440 2432 y Fq(\()p Fj(\014)r Fq(\))p eop %%Page: 7 7 7 6 bop 183 194 a Fq(hold)13 b(for)g Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))f Fi(\025)g Fq(3,)h Fj(\013;)7 b(\014)14 b Fi(2)d Fq(\()p Fj(\006)h Fi([)d Fj(V)g Fq(\))856 179 y Fp(+)898 194 y Fq(and)14 b Fj(\006)1013 179 y Ff(0)1037 194 y Fq(=)d Fj(\006)h Fi([)d(f)p Fj(a)p Fi(g)p Fq(,)k(where)i Fj(a)d Fi(62)f Fj(\006)r Fq(?)183 293 y(Again,)17 b(the)i(condition)e Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))j Fi(\025)f Fq(3)f(is)h(essen)o (tial)f(\(cf.)h(Example)d(1\).)i(By)h(v)n(ariations)183 343 y(of)f(the)i(ab)q(o)o(v)o(e)e(pro)q(of)h(tec)o(hnique,)h(w)o(e)f (are)g(able)g(to)g(sho)o(w)g(that)g(E-language)f(inclusion)183 393 y(\(hence)d(E-language)e(equiv)n(alence\))h(is)g(also)f(decidable)i (in)e(other)h(sp)q(ecial)h(cases.)183 467 y Fe(Prop)q(ositi)o(on)5 b(7.)21 b Fg(L)n(et)11 b Fj(\006)k Fg(b)n(e)d(an)g(alphab)n(et)g(and)g (let)g Fj(\013;)7 b(\014)13 b Fi(2)e Fq(\()p Fj(\006)5 b Fi([)r Fj(V)10 b Fq(\))1254 452 y Fp(+)1294 467 y Fg(b)n(e)h(similar) g(p)n(atterns)183 517 y(of)16 b(the)g(form)g Fj(\013)d Fq(=)i Fj(\013)519 523 y Fp(0)537 517 y Fj(u)561 523 y Fp(1)579 517 y Fj(\013)606 523 y Fp(1)624 517 y Fj(u)648 523 y Fp(2)674 517 y Fj(:)7 b(:)g(:)e(\013)756 523 y Fh(m)p Ff(\000)p Fp(1)830 517 y Fj(u)854 523 y Fh(m)885 517 y Fj(\013)912 523 y Fh(m)959 517 y Fg(and)17 b Fj(\014)g Fq(=)d Fj(\014)1150 523 y Fp(0)1169 517 y Fj(u)1193 523 y Fp(1)1211 517 y Fj(\014)1234 523 y Fp(1)1253 517 y Fj(u)1277 523 y Fp(2)1303 517 y Fj(:)7 b(:)g(:)e(\014)1381 523 y Fh(m)p Ff(\000)p Fp(1)1456 517 y Fj(u)1480 523 y Fh(m)1511 517 y Fj(\014)1534 523 y Fh(m)1566 517 y Fg(.)16 b(If)183 566 y Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))c Fi(\025)f Fj(m)f Fq(+)g(2)p Fg(,)k Fj(m)e Fi(\025)g Fq(0)p Fg(,)i(then)h(it)g(is)f(de)n(cidable)h(whether)g Fj(L)1199 572 y Fh(E)r(;\006)1264 566 y Fq(\()p Fj(\013)p Fq(\))d Fi(\022)g Fj(L)1407 572 y Fh(E)r(;\006)1472 566 y Fq(\()p Fj(\014)r Fq(\))p Fg(.)183 646 y Fe(Prop)q(ositi)o(on)5 b(8.)21 b Fg(L)n(et)15 b Fj(\013;)7 b(\014)15 b Fi(2)d Fq(\()p Fj(\006)h Fi([)d Fj(V)f Fq(\))835 631 y Fp(+)878 646 y Fg(b)n(e)16 b(similar)e(p)n(atterns.)i(If)f(ther)n(e)g(ar)n(e)g Fj(a;)7 b(b)13 b Fi(2)f Fj(\006)r Fg(,)183 696 y Fj(a)f Fi(6)p Fq(=)i Fj(b)p Fg(,)h(such)i(that)f(every)g(terminal)f(se)n (gment)h(of)g Fj(\013)g Fg(\(henc)n(e)h(of)f Fj(\014)r Fg(\))h(c)n(ontains)f(at)g(le)n(ast)g(one)183 746 y(letter)e(di\013er)n (ent)i(fr)n(om)f Fj(a)h Fg(and)h Fj(b)p Fg(,)e(then)i(it)e(is)h(de)n (cidable)g(whether)f Fj(L)1254 752 y Fh(E)r(;\006)1319 746 y Fq(\()p Fj(\013)p Fq(\))e Fi(\022)g Fj(L)1462 752 y Fh(E)r(;\006)1527 746 y Fq(\()p Fj(\014)r Fq(\))p Fg(.)183 871 y Fk(4)56 b(V)-5 b(ariable)18 b(Elimination)e(and)j(Normal)e(F)-5 b(orms)183 962 y Fq(Solving)10 b(the)j(equiv)n(alence)f(problem)e(for)i (NE-pattern)h(languages)e(is)h(easy:)g(Tw)o(o)f(patterns)183 1012 y(generate)16 b(the)g(same)f(language)g(if)f(and)h(only)g(if)g (they)h(are)g(iden)o(tical)e(up)i(to)f(renaming)f(of)183 1062 y(v)n(ariables;)e(see)i([Ang80a)o(].)f(F)m(or)f(E-patterns,)j(ho)o (w)o(ev)o(er,)e(this)g(is)h(not)f(true)h(at)f(all.)f(Jiang)h Fg(et)183 1111 y(al.)j Fq([JKS)332 1096 y Fp(+)360 1111 y Fq(94)o(])h(write)g(that:)f(\\Tw)o(o)g(v)o(ery)h(di\013eren)o(t)h(lo) q(oking)d(E-patterns)j(ma)o(y)d(generate)183 1161 y(the)i(same)f (language.)g(F)m(or)h(instance,)g(if)f(a)h(terminal-free)f(pattern)i Fj(\013)e Fq(con)o(tains)h(exactly)183 1211 y(one)h(o)q(ccurrence)j(of) c(some)g(v)n(ariable,)g(then)i Fj(\013)e Fq(is)h(equiv)n(alen)o(t)g(to) g(the)g(pattern)h Fj(x)p Fq(".)e(The)183 1261 y(fact)c(that)h(an)g (E-pattern)g(ma)o(y)e(con)o(tain)i(man)o(y)e(sup)q(er\015uous)j(v)n (ariables)e(seems)h(to)g(b)q(e)g(the)183 1311 y(ma)r(jor)d(problem)g (in)i(deciding)g(whether)h(t)o(w)o(o)e(E-patterns)i(generate)g(the)g (same)e(language.)183 1360 y(W)m(e)h(call)f(a)h(v)n(ariable)f Fj(x)h Fq(in)g(an)g(E-pattern)i Fj(\013)c Fi(2)g Fq(\()p Fj(\006)g Fi([)d Fj(V)h Fq(\))1071 1345 y Fp(+)1112 1360 y Fg(sup)n(er\015uous)p Fq(,)14 b(if)f(the)h(E-pattern)183 1410 y Fj(\013)210 1395 y Ff(0)235 1410 y Fq(obtained)g(from)e Fj(\013)h Fq(b)o(y)h(deleting)g(all)f(o)q(ccurrences)k(of)c Fj(x)g Fq(still)g(generates)j Fj(L)1416 1416 y Fh(E)r(;\006)1482 1410 y Fq(\()p Fj(\013)p Fq(\).)d(W)m(e)183 1460 y(next)j(tac)o(kle)g (the)g(equiv)n(alence)g(problem)e(of)i(t)o(w)o(o)f(E-patterns)i Fj(\013)e Fq(and)h Fj(\014)i Fq(b)o(y)e(eliminating)183 1510 y(sup)q(er\015uous)g(v)n(ariables)f(in)f Fj(\013)h Fq(and)g Fj(\014)r Fq(.)g(The)h(\014rst)g(di\016cult)o(y)e(one)h (encoun)o(ters)i(in)e(this)g(ap-)183 1560 y(proac)o(h)g(is)g(of)f (course)j(the)e(decidabilit)o(y)f(of)g(whether)j(a)e(v)n(ariable)f(is)g (sup)q(er\015uous)j(or)e(not.)183 1609 y(Since)f(w)o(e)g(do)f(not)h (kno)o(w)f(ho)o(w)g(to)h(decide)h(this)f(in)f(general,)g(w)o(e)h(b)o (y-pass)g(the)g(problem)f(b)o(y)183 1659 y(de\014ning)h(a)g(reduction)h (relation)f Fi(!)e(\032)g Fq(\()p Fj(\006)g Fi([)e Fj(V)f Fq(\))958 1644 y Fp(+)995 1659 y Fi(\002)h Fq(\()p Fj(\006)i Fi([)e Fj(V)f Fq(\))1184 1644 y Fp(+)1226 1659 y Fq(suc)o(h)15 b(that)f(if)g(pattern)h Fj(\013)183 1709 y Fq(reduces)h(to)d(pattern)i Fj(\013)556 1694 y Ff(0)567 1709 y Fq(,)f(then)g(the)h(erased)g(v)n (ariables)e(are)h(sup)q(er\015uous.)183 1783 y Fe(De\014niti)o(on)5 b(9.)20 b Fq(The)15 b(reduction)f(relation)f Fi(!)f(\032)g Fq(\()p Fj(\006)f Fi([)e Fj(V)g Fq(\))1120 1768 y Fp(+)1156 1783 y Fi(\002)g Fq(\()p Fj(\006)j Fi([)c Fj(V)i Fq(\))1343 1768 y Fp(+)1384 1783 y Fq(is)k(de\014ned)g(b)o(y:)183 1833 y Fj(\013)d Fi(!)g Fj(\013)301 1818 y Ff(0)326 1833 y Fq(if)i(and)h(only)f(if)200 1907 y(1.)20 b(there)f(is)e(a)g(non-empt) o(y)e(prop)q(er)k(subset)f Fj(V)947 1913 y Fh(d)984 1907 y Fq(of)e Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))i(suc)o(h)g(that)f (erasing)g(all)f(o)q(c-)253 1957 y(currences)i(of)d(v)n(ariables)f(of)h Fj(V)732 1963 y Fh(d)766 1957 y Fq(in)g Fj(\013)g Fq(yields)g Fj(\013)1003 1941 y Ff(0)1029 1957 y Fq(\(that)g(is)g(to)g(sa)o(y)m(,)f Fj(\013)1339 1941 y Ff(0)1364 1957 y Fq(=)g Fj(d)p Fq(\()p Fj(\013)p Fq(\),)g(where)253 2006 y Fj(d)d Fq(=)h Fi(f)p Fj(x)f Fi(7!)g Fj(\025)i Fi(j)f Fj(x)f Fi(2)g Fj(V)598 2012 y Fh(d)618 2006 y Fi(g)p Fq(\),)i(and)200 2056 y(2.)20 b(there)g(is)d(a)h(linear)g(substitution)g Fj(\033)h Fq(:)f Fj(v)q(ar)q Fq(\()p Fj(\013)982 2041 y Ff(0)994 2056 y Fq(\))h Fi(!)e Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))i(suc)o(h)f (that)h Fj(\033)q Fq(\()p Fj(\013)1489 2041 y Ff(0)1500 2056 y Fq(\))g(=)f Fj(\013)p Fq(.)253 2106 y(Hereb)o(y)d Fj(\033)g Fq(is)f(called)g Fg(line)n(ar)f Fq(if)g(it)g(has)h(the)h (form)414 2182 y Fj(\033)e Fq(=)e Fi(f)p Fj(x)539 2188 y Fh(i)564 2182 y Fi(7!)g Fj(\015)638 2188 y Fh(i)653 2182 y Fj(x)677 2188 y Fh(i)690 2182 y Fj(\015)713 2165 y Ff(0)711 2192 y Fh(i)738 2182 y Fi(j)h Fj(x)786 2188 y Fh(i)811 2182 y Fi(2)f Fj(v)q(ar)q Fq(\()p Fj(\013)956 2165 y Ff(0)968 2182 y Fq(\))p Fj(;)30 b(\015)1047 2188 y Fh(i)1061 2182 y Fj(;)7 b(\015)1103 2165 y Ff(0)1101 2192 y Fh(i)1127 2182 y Fi(2)k Fj(V)1199 2165 y Ff(\003)1190 2192 y Fh(d)1218 2182 y Fj(;)30 b Fq(1)11 b Fi(\024)h Fj(i)g Fi(\024)g Fj(n)p Fi(g)p Fj(;)253 2258 y Fq(where)j Fj(v)q(ar)q Fq(\()p Fj(\013)479 2243 y Ff(0)491 2258 y Fq(\))d(=)g Fi(f)p Fj(x)608 2264 y Fp(1)626 2258 y Fj(;)7 b(:)g(:)g(:)e(;)i(x)743 2264 y Fh(n)764 2258 y Fi(g)p Fq(.)183 2332 y(If)17 b Fj(\013)i Fi(!)f Fj(\013)361 2317 y Ff(0)372 2332 y Fq(,)f(then)i(w)o(e)f(sa)o(y)g(that)g Fj(\013)g Fg(r)n(e)n(duc)n(es)g Fq(to)g Fj(\013)1009 2317 y Ff(0)1038 2332 y Fq(\(b)o(y)g(deleting)g(the)h(v)n(ariables)e Fj(V)1553 2338 y Fh(d)1591 2332 y Fq(=)183 2382 y Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))10 b Fi(n)g Fj(v)q(ar)q Fq(\()p Fj(\013)452 2367 y Ff(0)464 2382 y Fq(\)\).)k(P)o(attern)i Fj(\013)f Fq(is)g(said)f(to)h(b)q(e)h Fg(r)n(e)n(ducible)p Fq(,)e(if)g(there)i(exists)g(a)e(pattern)i Fj(\013)1612 2367 y Ff(0)183 2432 y Fq(suc)o(h)e(that)g Fj(\013)d Fi(!)h Fj(\013)485 2417 y Ff(0)496 2432 y Fq(.)p eop %%Page: 8 8 8 7 bop 340 194 a Fq(W)m(e)12 b(illustrate)f(the)i(de\014nition)e(b)o (y)h(a)g(small)d(example)i(whic)o(h)h(also)f(sho)o(ws)h(that)g (sometimes)340 244 y(it)i(is)g(necessary)i(to)d(eliminate)f(more)h (than)h(one)g(v)n(ariable)f(in)g(one)h(reduction)h(step.)340 326 y Fg(Example)8 b(3.)21 b Fq(Let)14 b Fj(\013)e Fq(=)g Fj(xz)r(y)q(z)r(y)q(z)r(z)r Fq(.)j(Then)g Fj(\013)d Fi(!)f Fj(\013)1118 311 y Ff(0)1141 326 y Fq(=)h Fj(x)i Fq(b)q(ecause)i(the)e (linear)g(substitution)340 376 y Fj(\033)j Fq(=)e Fi(f)p Fj(x)g Fi(7!)g Fj(xz)r(y)q(z)r(y)q(z)r(z)r Fi(g)j Fq(satis\014es)f Fj(\033)q Fq(\()p Fj(\013)957 361 y Ff(0)968 376 y Fq(\))f(=)f Fj(\013)p Fq(.)h(Note)g(that)g(neither)i Fj(\013)c Fi(!)h Fj(xy)q(y)k Fq(nor)d Fj(\013)f Fi(!)340 426 y Fj(xz)r(z)r(z)r(z)r Fq(,)f(although)f Fj(xy)q(y)j Fq(and)e Fj(xz)r(z)r(z)r(z)i Fq(generate)f Fj(L)1125 432 y Fh(E)r(;\006)1191 426 y Fq(\()p Fj(\013)p Fq(\).)340 508 y(Giv)o(en)g Fj(\013)g Fq(and)g Fj(\013)613 493 y Ff(0)625 508 y Fq(,)g(it)g(is)g(decidable)h (whether)g Fj(\013)e Fi(!)g Fj(\013)1206 493 y Ff(0)1217 508 y Fq(:)h(Condition)f(\(1\))h(can)h(b)q(e)g(c)o(hec)o(k)o(ed)340 558 y(in)j(linear)g(time)f(and)i(condition)f(\(2\))g(is)g(decidable)h (b)q(ecause)h(it)e(su\016ces)i(to)e(c)o(hec)o(k)i(the)340 608 y(equalit)o(y)d Fj(\033)q Fq(\()p Fj(\013)571 593 y Ff(0)583 608 y Fq(\))h(=)h Fj(\013)e Fq(merely)f(for)i(the)g (\014nitely)f(man)o(y)f(linear)h(substitutions)h Fj(\033)g Fq(whic)o(h)340 658 y(satisfy)471 627 y Fa(P)514 637 y Fh(n)514 670 y(i)p Fp(=1)577 658 y Fi(j)p Fj(\015)610 664 y Fh(i)624 658 y Fj(\015)647 643 y Ff(0)645 668 y Fh(i)660 658 y Fi(j)12 b Fq(=)h Fi(j)p Fj(\013)p Fi(j)8 b(\000)i(j)p Fj(\013)869 643 y Ff(0)880 658 y Fi(j)k Fq(\(since)1024 627 y Fa(P)1068 637 y Fh(n)1068 670 y(i)p Fp(=1)1131 658 y Fi(j)p Fj(\015)1164 664 y Fh(i)1178 658 y Fj(\015)1201 643 y Ff(0)1199 668 y Fh(i)1213 658 y Fi(j)e(6)p Fq(=)h Fi(j)p Fj(\013)p Fi(j)c(\000)h(j)p Fj(\013)1423 643 y Ff(0)1434 658 y Fi(j)k Fq(implies)e Fj(\033)q Fq(\()p Fj(\013)1669 643 y Ff(0)1681 658 y Fq(\))h Fi(6)p Fq(=)g Fj(\013)340 707 y Fq(already\).)i(Hence)i(it)e (is)h(also)f(decidable)g(whether)i Fj(\013)e Fq(is)h(reducible)g(since) g(there)h(are)f(only)340 757 y(\014nitely)e(man)o(y)e(non-empt)o(y)g (prop)q(er)j(subsets)h Fj(V)1101 763 y Fh(d)1134 757 y Fq(of)e Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\).)340 840 y Fe(Lemma)8 b(10.)20 b Fg(If)g Fj(\013)p Fi(!)o Fj(\013)727 825 y Ff(0)738 840 y Fg(,)g(then)g Fj(L)896 846 y Fh(E)r(;\006)961 840 y Fq(\()p Fj(\013)p Fq(\))g(=)g Fj(L)1120 846 y Fh(E)r(;\006)1186 840 y Fq(\()p Fj(\013)1229 825 y Ff(0)1240 840 y Fq(\))p Fg(.)g(\(Henc)n(e)g(the)f(variables)g Fj(V)1709 846 y Fh(d)1749 840 y Fq(=)340 890 y Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))10 b Fi(n)f Fj(v)q(ar)q Fq(\()p Fj(\013)608 875 y Ff(0)620 890 y Fq(\))15 b Fg(ar)n(e)f(sup)n(er\015uous)i(in)f Fj(\013)p Fg(.\))340 980 y Fe(Lemma)8 b(11.)20 b Fg(The)g(r)n(e)n (duction)g(r)n(elation)f Fi(!)g(\032)i Fq(\()p Fj(\006)15 b Fi([)e Fj(V)c Fq(\))1283 965 y Fp(+)1324 980 y Fi(\002)k Fq(\()p Fj(\006)i Fi([)d Fj(V)e Fq(\))1522 965 y Fp(+)1569 980 y Fg(is)20 b(a)f(length-)340 1030 y(de)n(cr)n(e)n(asing)c(\(i.e.,)f Fj(\013)d Fi(!)g Fj(\013)758 1015 y Ff(0)785 1030 y Fg(implies)j Fi(j)p Fj(\013)p Fi(j)c Fj(>)i Fi(j)p Fj(\013)1071 1015 y Ff(0)1082 1030 y Fi(j)p Fg(\))i(p)n(artial)g(or)n(dering.)340 1121 y Fe(De\014nition)t(12.)21 b Fq(A)14 b(pattern)h Fj(\013)f Fq(is)g(said)g(to)g(b)q(e)h(in)f Fg(normal)h(form)e Fq(\(w.r.t.)g Fi(!)p Fq(\),)h(if)f(there)i(is)340 1171 y(no)f(pattern)h Fj(\013)573 1156 y Ff(0)598 1171 y Fq(suc)o(h)g(that)f Fj(\013)d Fi(!)g Fj(\013)900 1156 y Ff(0)911 1171 y Fq(.)340 1261 y(Since)h Fi(!)f Fq(is)g(length-decreasing,)h(the)g(successiv)o(e) i(reduction)e(of)f(a)g(pattern)h(m)o(ust)f(end)h(in)f(a)340 1311 y(normal)f(form)g(\(an)h(irreducible)h(pattern\).)g(Clearly)m(,)e (a)h(pattern)i Fj(\013)e Fq(ma)o(y)f(ha)o(v)o(e)h(t)o(w)o(o)g(distinct) 340 1361 y(normal)f(forms.)g(Just)j(consider)f Fj(\013)g Fq(=)f Fj(xy)q Fq(:)h Fj(\013)f Fi(!)g Fj(x)h Fq(and)g Fj(\013)f Fi(!)g Fj(y)q Fq(.)h(Our)g(next)h(goal)d(is)i(to)f(sho)o(w) 340 1411 y(that)i(the)g(normal)d(forms)h(of)h(a)g(pattern)h(are)g(iden) o(tical)f(up)g(to)g(v)n(ariable)g(renaming.)e(In)i(this)340 1461 y(con)o(text,)k(the)f(follo)o(wing)d(tec)o(hnical)k(lemma)11 b(pla)o(ys)k(a)g(k)o(ey)g(r^)-21 b(ole.)14 b(Its)h(pro)q(of)g(can)g(b)q (e)h(found)340 1511 y(in)e([OU95)o(].)340 1593 y Fe(Lemma)8 b(13.)20 b Fg(L)n(et)c Fj(\013)d Fi(2)f Fq(\()p Fj(\006)h Fi([)c Fj(V)h Fq(\))884 1578 y Fp(+)927 1593 y Fg(b)n(e)16 b(a)g(p)n(attern)f(and)i(let)e Fj(h)e Fq(:)f Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))i Fi(!)e Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))1673 1578 y Ff(\003)1708 1593 y Fg(b)n(e)k(a)340 1643 y(substitution)f(such)h(that)f Fj(h)p Fq(\()p Fj(\013)p Fq(\))c(=)h Fj(\013)p Fg(.)i(Then)h(the)g(fol)r(lowing)f(statements)h (hold.)356 1725 y(1.)21 b Fj(\013)16 b Fg(has)g(a)g(p)n(artition)f Fj(\013)f Fq(=)g Fj(\014)847 1731 y Fp(1)866 1725 y Fj(\014)889 1731 y Fp(2)915 1725 y Fj(:)7 b(:)g(:)e(\014)993 1731 y Fh(k)1030 1725 y Fg(into)16 b(minimal)f(\014xp)n(oints)i(of)f Fj(h)p Fg(,)f(i.e.,)g(for)h(e)n(ach)411 1775 y Fj(i)e Fi(2)g(f)p Fq(1)p Fj(;)7 b(:)g(:)g(:)t(;)g(k)q Fi(g)p Fg(,)15 b Fj(\014)710 1781 y Fh(i)739 1775 y Fi(2)e Fq(\()p Fj(\006)h Fi([)c Fj(V)f Fq(\))929 1760 y Fp(+)957 1775 y Fg(,)16 b(the)g(e)n(quality)g Fj(h)p Fq(\()p Fj(\014)1272 1781 y Fh(i)1286 1775 y Fq(\))f(=)f Fj(\014)1386 1781 y Fh(i)1416 1775 y Fg(holds,)j(and)g(for)e(every)411 1825 y(pr)n(op)n(er)f(subwor)n(d)h Fj(\015)j Fg(of)c Fj(\014)808 1831 y Fh(i)838 1825 y Fg(we)g(have)i Fj(h)p Fq(\()p Fj(\015)r Fq(\))c Fi(6)p Fq(=)g Fj(\015)r Fg(.)356 1875 y(2.)21 b(The)15 b(p)n(artition)f(is)h(unique.)356 1925 y(3.)21 b(F)m(or)16 b(every)g Fj(i)e Fi(2)f(f)p Fq(1)p Fj(;)7 b(:)g(:)g(:)e(;)i(k)q Fi(g)p Fg(,)15 b(either)g Fj(\014)1019 1931 y Fh(i)1047 1925 y Fi(2)f Fj(\006)19 b Fg(or)c Fj(\014)1217 1931 y Fh(i)1246 1925 y Fi(2)e Fj(V)1320 1910 y Fp(+)1348 1925 y Fg(.)j(Mor)n(e)n(over,)f(if)h Fj(\014)1638 1931 y Fh(i)1666 1925 y Fi(2)e Fj(V)1741 1910 y Fp(+)1769 1925 y Fg(,)411 1974 y(then)h(it)g(c)n(ontains)g (exactly)g(one)h(variable)e Fj(x)h Fg(such)g(that)452 2057 y Fq(\()p Fi(\003)p Fq(\))71 b Fj(h)p Fq(\()p Fj(x)p Fq(\))11 b(=)h Fj(\015)732 2063 y Fp(1)751 2057 y Fj(x\015)796 2063 y Fp(2)815 2057 y Fj(;)26 b Fg(wher)n(e)14 b Fj(\015)991 2063 y Fp(1)1011 2057 y Fj(;)7 b(\015)1051 2063 y Fp(2)1081 2057 y Fi(2)k Fq(\()p Fj(v)q(ar)q Fq(\()p Fj(\014)1238 2063 y Fh(i)1253 2057 y Fq(\))e Fi(n)g(f)p Fj(x)p Fi(g)p Fq(\))1390 2041 y Ff(\003)1424 2057 y Fg(and)838 2106 y Fj(\014)861 2112 y Fh(i)887 2106 y Fq(=)j Fj(\016)949 2112 y Fp(1)968 2106 y Fj(\015)989 2112 y Fp(1)1008 2106 y Fj(x\015)1053 2112 y Fp(2)1072 2106 y Fj(\016)1090 2112 y Fp(2)1124 2106 y Fg(for)i(some)h Fj(\016)1314 2112 y Fp(1)1333 2106 y Fj(;)7 b(\016)1370 2112 y Fp(2)1400 2106 y Fi(2)12 b Fq(\()p Fj(v)q(ar)q Fq(\()p Fj(\014)1558 2112 y Fh(i)1573 2106 y Fq(\))d Fi(n)g(f)p Fj(x)p Fi(g)p Fq(\))1710 2091 y Ff(\003)1729 2106 y Fj(:)356 2192 y Fg(4.)21 b(If)c Fj(x)f Fg(is)h(a)g(variable)g(such)g(that)g Fj(h)p Fq(\()p Fj(x)p Fq(\))f(=)f Fj(\015)1087 2198 y Fp(1)1107 2192 y Fj(x\015)1152 2198 y Fp(2)1170 2192 y Fg(,)i(wher)n(e)f Fj(\015)1340 2198 y Fp(1)1360 2192 y Fj(;)7 b(\015)1400 2198 y Fp(2)1434 2192 y Fi(2)15 b Fq(\()p Fj(v)q(ar)q Fq(\()p Fj(\014)1595 2198 y Fh(i)1610 2192 y Fq(\))c Fi(n)f(f)p Fj(x)p Fi(g)p Fq(\))1750 2176 y Ff(\003)1769 2192 y Fg(,)411 2241 y(and)16 b Fj(x)e Fg(o)n(c)n(curs)h(in)g(some)g Fj(\014)837 2247 y Fh(i)866 2241 y Fg(and)h Fj(\014)970 2247 y Fh(j)988 2241 y Fg(,)e Fj(i)e Fi(6)p Fq(=)g Fj(j)r Fg(,)j(then)g Fj(\014)1247 2247 y Fh(i)1273 2241 y Fq(=)d Fj(\014)1340 2247 y Fh(j)1358 2241 y Fg(.)340 2332 y Fe(Theorem)7 b(14.)21 b Fg(L)n(et)g Fj(\013)j Fi(2)g Fq(\()p Fj(\006)17 b Fi([)d Fj(V)9 b Fq(\))954 2317 y Fp(+)1004 2332 y Fg(b)n(e)22 b(a)g(p)n(attern)f(in)h (normal)g(form)f(and)i(let)e Fj(h)j Fq(:)340 2382 y Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))19 b Fi(!)e Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))662 2367 y Ff(\003)700 2382 y Fg(b)n(e)h(a)h (substitution)f(such)h(that)f Fj(h)p Fq(\()p Fj(\013)p Fq(\))g(=)g Fj(\013)p Fg(.)g(Then)g Fj(h)h Fg(is)f(the)g(iden-)340 2432 y(tity)d(function)g(on)g Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))p Fg(.)p eop %%Page: 9 9 9 8 bop 183 194 a Fg(Pr)n(o)n(of.)20 b Fq(According)d(to)f(Lemma)e(13,) h Fj(\013)h Fq(has)h(a)f(unique)g(partition)g Fj(\013)f Fq(=)h Fj(\014)1369 200 y Fp(1)1389 194 y Fj(\014)1412 200 y Fp(2)1438 194 y Fj(:)7 b(:)g(:)e(\014)1516 200 y Fh(k)1553 194 y Fq(in)o(to)183 244 y(minim)o(al)13 b(\014xp)q(oin)o(ts)j(of)h Fj(h)f Fq(suc)o(h)i(that)e(either)i Fj(\014)943 250 y Fh(i)974 244 y Fi(2)d Fj(\006)20 b Fq(or)d Fj(\014)1146 250 y Fh(i)1176 244 y Fi(2)f Fj(V)1254 228 y Fp(+)1298 244 y Fq(where)i Fj(\014)1444 250 y Fh(i)1475 244 y Fq(con)o(tains)183 293 y(exactly)h(one)g(v)n(ariable)e Fj(x)596 299 y Fh(i)629 293 y Fq(whic)o(h)h(o)q(ccurs)i(in)f Fj(h)p Fq(\()p Fj(x)1003 299 y Fh(i)1016 293 y Fq(\).)g(Let)g Fj(i)1156 299 y Fp(1)1175 293 y Fj(;)7 b(:)g(:)g(:)e(;)i(i)1282 299 y Fh(p)1320 293 y Fq(b)q(e)19 b(exactly)g(those)183 343 y(indices)14 b(for)f(whic)o(h)h Fj(\014)524 349 y Fh(i)536 353 y Fd(j)565 343 y Fi(2)d Fj(V)638 328 y Fp(+)679 343 y Fq(and)j(let)f Fj(x)843 349 y Fh(i)855 353 y Fd(j)886 343 y Fq(b)q(e)h(the)h(corresp)q(onding)f(v)n(ariables)f(satisfying)183 393 y(\()p Fi(\003)p Fq(\).)18 b(Let)i Fj(V)370 399 y Fh(nd)430 393 y Fq(=)h Fi(f)p Fj(x)528 399 y Fh(i)540 403 y Fc(1)558 393 y Fj(;)7 b(:)g(:)g(:)t(;)g(x)674 399 y Fh(i)686 403 y Fd(p)705 393 y Fi(g)19 b Fq(\(note)g(that)g Fj(x)977 399 y Fh(i)989 403 y Fd(j)1027 393 y Fq(=)h Fj(x)1103 399 y Fh(i)1115 403 y Fd(q)1134 393 y Fq(,)e Fj(i)1178 399 y Fh(j)1216 393 y Fi(6)p Fq(=)j Fj(i)1283 399 y Fh(q)1302 393 y Fq(,)d(is)h(p)q(ossible\))h(and)183 443 y Fj(V)207 449 y Fh(d)238 443 y Fq(=)12 b Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))7 b Fi(n)g Fj(V)463 449 y Fh(nd)502 443 y Fq(.)12 b(Supp)q(ose)i(that)f Fj(V)801 449 y Fh(d)832 443 y Fi(6)p Fq(=)f Fi(;)g Fq(and)g(let)h Fj(\013)1074 428 y Ff(0)1098 443 y Fq(b)q(e)g(the)g(pattern)h(obtained)e(from)183 493 y Fj(\013)i Fq(b)o(y)h(deleting)f(all)g(the)i(v)n(ariables)e(from)f Fj(V)868 499 y Fh(d)887 493 y Fq(,)i(i.e.,)e Fj(\013)1020 478 y Ff(0)1044 493 y Fq(=)h Fj(d)p Fq(\()p Fj(\013)p Fq(\))g(where)i Fj(d)d Fq(=)g Fi(f)p Fj(x)g Fi(7!)f Fj(\025)h Fi(j)f Fj(x)h Fi(2)183 542 y Fj(V)207 548 y Fh(d)226 542 y Fi(g)p Fq(.)j(Note)i(that)e Fj(v)q(ar)q Fq(\()p Fj(\013)577 527 y Ff(0)589 542 y Fq(\))h(=)g Fj(V)695 548 y Fh(nd)735 542 y Fq(.)f(De\014ne)i Fj(g)f Fq(:)f Fj(v)q(ar)q Fq(\()p Fj(\013)1066 527 y Ff(0)1078 542 y Fq(\))h Fi(!)f Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))1291 527 y Ff(\003)1327 542 y Fq(b)o(y)g Fj(g)q Fq(\()p Fj(x)1448 548 y Fh(i)1460 552 y Fd(j)1478 542 y Fq(\))h(=)f Fj(\014)1582 548 y Fh(i)1594 552 y Fd(j)1612 542 y Fq(.)183 592 y(According)g(to)f (Lemma)e(13,)i Fj(g)i Fq(is)e(w)o(ell-de\014ned)h(b)q(ecause)i Fj(x)1142 598 y Fh(i)1154 602 y Fd(j)1185 592 y Fq(=)d Fj(x)1256 598 y Fh(i)1268 602 y Fd(q)1302 592 y Fq(implies)e Fj(\014)1467 598 y Fh(i)1479 602 y Fd(j)1511 592 y Fq(=)i Fj(\014)1581 598 y Fh(i)1593 602 y Fd(q)1612 592 y Fq(.)183 642 y(F)m(urthermore,)c(w)o(e)g(claim)f Fj(g)q Fq(\()p Fj(\013)664 627 y Ff(0)675 642 y Fq(\))i(=)g Fj(\013)p Fq(.)e(In)i(order)g(to)f(pro)o(v)o(e)h(this)g(claim,)c(it)k(su\016ces)g (to)g(sho)o(w)183 692 y Fj(g)q Fq(\()p Fj(d)p Fq(\()p Fj(\014)281 698 y Fh(i)293 702 y Fd(j)311 692 y Fq(\)\))i(=)g Fj(\014)426 698 y Fh(i)438 702 y Fd(j)471 692 y Fq(for)h(all)f(1)f Fi(\024)h Fj(j)j Fi(\024)d Fj(p)p Fq(.)g(W)m(e)h(ha)o(v)o(e)g Fj(d)p Fq(\()p Fj(\014)1033 698 y Fh(i)1045 702 y Fd(j)1063 692 y Fq(\))f(=)g Fj(x)1163 698 y Fh(i)1175 702 y Fd(j)1207 692 y Fq(b)q(ecause)j Fj(x)1386 698 y Fh(i)1398 702 y Fd(j)1430 692 y Fq(is)e(the)h(only)183 742 y(v)n(ariable)10 b(from)g Fj(V)456 748 y Fh(nd)508 742 y Fq(in)i Fj(\014)578 748 y Fh(i)590 752 y Fd(j)608 742 y Fq(.)f(Hence)i Fj(g)q Fq(\()p Fj(d)p Fq(\()p Fj(\014)850 748 y Fh(i)862 752 y Fd(j)880 742 y Fq(\)\))f(=)g Fj(g)q Fq(\()p Fj(x)1029 748 y Fh(i)1041 752 y Fd(j)1058 742 y Fq(\))g(=)g Fj(\014)1153 748 y Fh(i)1165 752 y Fd(j)1194 742 y Fq(and)g(the)h(claim)c(is)j(pro)o (v)o(ed.)183 791 y(Since)g Fj(\014)312 797 y Fh(i)324 801 y Fd(j)354 791 y Fq(has)h(a)f(represen)o(tation)h Fj(\016)747 797 y Fp(1)766 791 y Fj(\015)787 797 y Fp(1)807 791 y Fj(x)831 797 y Fh(i)843 801 y Fd(j)860 791 y Fj(\015)881 797 y Fp(2)900 791 y Fj(\016)918 797 y Fp(2)937 791 y Fq(,)f(where)h Fj(\015)1100 797 y Fp(1)1119 791 y Fj(;)7 b(\015)1159 797 y Fp(2)1178 791 y Fj(;)g(\016)1215 797 y Fp(1)1233 791 y Fj(;)g(\016)1270 797 y Fp(2)1300 791 y Fi(2)k Fj(V)1373 776 y Ff(\003)1363 803 y Fh(d)1392 791 y Fq(,)h Fj(g)h Fq(is)f(a)g(linear)183 841 y(substitution.)j(Th)o (us)i(it)e(follo)o(ws)f Fj(\013)p Fi(!)p Fj(\013)812 826 y Ff(0)823 841 y Fq(.)h(This,)h(ho)o(w)o(ev)o(er,)g(con)o(tradicts) g(the)h(fact)f(that)g Fj(\013)183 891 y Fq(is)h(in)g(normal)f(form.)f (So)j Fj(V)624 897 y Fh(d)661 891 y Fq(=)g Fi(;)p Fq(.)f(It)h(further)g (follo)o(ws)e(that)i Fj(\014)1210 897 y Fh(i)1222 901 y Fd(j)1258 891 y Fq(=)g Fj(x)1332 897 y Fh(i)1344 901 y Fd(j)1379 891 y Fq(and)f(therefore)183 941 y Fj(h)p Fq(\()p Fj(x)247 947 y Fh(i)259 951 y Fd(j)276 941 y Fq(\))11 b(=)h Fj(x)371 947 y Fh(i)383 951 y Fd(j)414 941 y Fq(for)i(1)d Fi(\024)h Fj(j)i Fi(\024)e Fj(p)p Fq(.)h(Hence)i Fj(h)f Fq(is)g(the)g(iden)o(tit)o(y)g(on)f Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))f(=)g Fi(f)p Fj(x)1383 947 y Fh(i)1395 951 y Fc(1)1413 941 y Fj(;)7 b(:)g(:)g(:)t(;)g(x)1529 947 y Fh(i)1541 951 y Fd(p)1560 941 y Fi(g)p Fq(.)183 1038 y(The)13 b(simple)e(example)h Fj(\013)f Fq(=)h Fj(xy)q Fq(,)h Fj(h)p Fq(\()p Fj(x)p Fq(\))f(=)f Fj(xy)k Fq(and)e Fj(h)p Fq(\()p Fj(y)q Fq(\))f(=)g Fj(\025)h Fq(sho)o(ws)g(that)g(in)g (Theorem)f(14)183 1088 y(the)i(normal)e(form)g(requiremen)o(t)i(on)g Fj(\013)f Fq(cannot)h(b)q(e)h(dropp)q(ed.)183 1177 y Fe(Corollary)6 b(15.)21 b Fg(If)d Fj(\013)f Fi(2)h Fq(\()p Fj(\006)c Fi([)e Fj(V)d Fq(\))757 1162 y Fp(+)803 1177 y Fg(r)n(e)n(duc)n(es)18 b(to)h(distinct)e(normal)i(forms)e Fj(\013)1449 1162 y Ff(0)1479 1177 y Fg(and)i Fj(\013)1590 1162 y Ff(00)1611 1177 y Fg(,)183 1227 y(then)c(ther)n(e)f(is)h(a)g (variable)f(r)n(enaming)h Fj(h)d Fq(:)f Fj(v)q(ar)q Fq(\()p Fj(\013)962 1212 y Ff(0)974 1227 y Fq(\))h Fi(!)f Fj(v)q(ar)q Fq(\()p Fj(\013)1161 1212 y Ff(00)1182 1227 y Fq(\))1198 1212 y Ff(\003)1232 1227 y Fg(such)16 b(that)e Fj(h)p Fq(\()p Fj(\013)1478 1212 y Ff(0)1490 1227 y Fq(\))e(=)f Fj(\013)1588 1212 y Ff(00)1609 1227 y Fg(.)183 1316 y(Pr)n(o)n(of.)20 b Fq(Consider)14 b(t)o(w)o(o)f(reductions)i(of)f Fj(\013)f Fq(to)h(normal)e(forms)g Fj(\013)1186 1301 y Ff(0)1211 1316 y Fq(and)i Fj(\013)1319 1301 y Ff(00)1340 1316 y Fq(:)183 1411 y Fj(\013)210 1393 y Ff(0)233 1411 y Fq(=)d Fj(\013)303 1393 y Ff(0)303 1421 y Fh(n)337 1411 y Fi( )g Fj(\013)417 1393 y Ff(0)417 1421 y Fh(n)p Ff(\000)p Fp(1)493 1411 y Fi( )g Fj(:)c(:)g(:)j Fi( )h Fj(\013)686 1393 y Ff(0)686 1421 y Fp(1)716 1411 y Fi( )g Fj(\013)796 1393 y Ff(0)796 1421 y Fp(0)826 1411 y Fq(=)h Fj(\013)f Fq(=)h Fj(\013)979 1393 y Ff(00)979 1421 y Fp(0)1011 1411 y Fi(!)f Fj(\013)1091 1393 y Ff(00)1091 1421 y Fp(1)1124 1411 y Fi(!)g Fj(:)c(:)g(:)j Fi(!)h Fj(\013)1317 1393 y Ff(00)1317 1421 y Fh(m)p Ff(\000)p Fp(1)1402 1411 y Fi(!)g Fj(\013)1482 1393 y Ff(00)1482 1421 y Fh(m)1524 1411 y Fq(=)h Fj(\013)1595 1393 y Ff(00)1616 1411 y Fj(:)183 1505 y Fq(Since)i Fi(!)f Fq(is)g(transitiv)o(e,)g(w)o(e)h(obtain)f Fj(\013)800 1490 y Ff(0)822 1505 y Fi( )e Fj(\013)h Fi(!)f Fj(\013)994 1490 y Ff(00)1015 1505 y Fq(.)i(By)g(de\014nition)h(of)e (reduction,)i(there)183 1555 y(are)g(substitutions)h Fj(d)522 1540 y Ff(0)533 1555 y Fj(;)7 b(d)574 1540 y Ff(00)608 1555 y Fq(and)14 b Fj(\033)714 1540 y Ff(0)726 1555 y Fj(;)7 b(\033)770 1540 y Ff(00)805 1555 y Fq(suc)o(h)15 b(that)f Fj(d)1011 1540 y Ff(0)1023 1555 y Fq(\()p Fj(\013)p Fq(\))e(=)g Fj(\013)1165 1540 y Ff(0)1176 1555 y Fq(,)i Fj(d)1224 1540 y Ff(00)1245 1555 y Fq(\()p Fj(\013)p Fq(\))d(=)i Fj(\013)1387 1540 y Ff(00)1408 1555 y Fq(,)g Fj(\033)1458 1540 y Ff(0)1470 1555 y Fq(\()p Fj(\013)1513 1540 y Ff(0)1525 1555 y Fq(\))f(=)g Fj(\013)183 1605 y Fq(and)k Fj(\033)291 1589 y Ff(00)312 1605 y Fq(\()p Fj(\013)355 1589 y Ff(00)376 1605 y Fq(\))g(=)g Fj(\013)p Fq(.)g(De\014ne)h Fj(f)j Fq(:)15 b Fj(v)q(ar)q Fq(\()p Fj(\013)815 1589 y Ff(0)827 1605 y Fq(\))h Fi(!)f Fj(v)q(ar)q Fq(\()p Fj(\013)1022 1589 y Ff(00)1044 1605 y Fq(\))1060 1589 y Ff(\003)1095 1605 y Fq(b)o(y)h Fj(f)21 b Fq(=)16 b Fj(d)1266 1589 y Ff(00)1298 1605 y Fi(\016)10 b Fj(\033)1354 1589 y Ff(0)1366 1605 y Fq(.)16 b(Analogously)m(,)183 1654 y(de\014ne)f Fj(g)e Fq(:)e Fj(v)q(ar)q Fq(\()p Fj(\013)465 1639 y Ff(00)486 1654 y Fq(\))h Fi(!)g Fj(v)q(ar)q Fq(\()p Fj(\013)674 1639 y Ff(0)686 1654 y Fq(\))702 1639 y Ff(\003)735 1654 y Fq(b)o(y)h Fj(g)h Fq(=)e Fj(d)892 1639 y Ff(0)912 1654 y Fi(\016)d Fj(\033)967 1639 y Ff(00)989 1654 y Fq(.)k(Then)i Fj(f)t Fq(\()p Fj(\013)1190 1639 y Ff(0)1202 1654 y Fq(\))d(=)g Fj(\013)1301 1639 y Ff(00)1336 1654 y Fq(and)h Fj(g)q Fq(\()p Fj(\013)1480 1639 y Ff(00)1502 1654 y Fq(\))f(=)g Fj(\013)1601 1639 y Ff(0)1612 1654 y Fq(.)183 1704 y(Hence)17 b Fj(f)t Fq(\()p Fj(g)q Fq(\()p Fj(\013)412 1689 y Ff(00)434 1704 y Fq(\)\))e(=)g Fj(\013)555 1689 y Ff(00)592 1704 y Fq(and)g Fj(g)q Fq(\()p Fj(f)t Fq(\()p Fj(\013)778 1689 y Ff(0)791 1704 y Fq(\)\))g(=)g Fj(\013)912 1689 y Ff(0)923 1704 y Fq(.)h(By)g(Theorem)f(14,)g Fj(f)g Fi(\016)10 b Fj(g)17 b Fq(is)f(the)g(iden)o(tit)o(y)183 1754 y(on)d Fj(v)q(ar)q Fq(\()p Fj(\013)346 1739 y Ff(00)368 1754 y Fq(\))h(and)f Fj(g)e Fi(\016)e Fj(f)18 b Fq(is)c(the)g(iden)o (tit)o(y)g(on)f Fj(v)q(ar)q Fq(\()p Fj(\013)1007 1739 y Ff(0)1019 1754 y Fq(\).)h(Th)o(us)g Fj(f)k Fq(and)c Fj(g)h Fq(are)f(bijections,)g(or)183 1804 y(in)f(other)i(w)o(ords,)e(v) n(ariable)g(renamings.)183 1891 y(Th)o(us)i(the)h(normal)e(form)f(of)i (pattern)h Fj(\013)f Fq(is)h(unique)f(\(up)h(to)f(v)n(ariable)f (renamings\);)g(from)183 1941 y(no)o(w)k(on)h(it)f(will)g(b)q(e)i (denoted)f(b)o(y)g Fj(\013)p Fi(#)p Fq(.)f(Next,)h(w)o(e)g(deriv)o(e)h (equiv)n(alen)o(t)e(form)o(ulations)e(of)183 1991 y(Conjecture)f(1)e (of)h(Section)g(1.)183 2080 y Fe(Prop)q(ositi)o(on)5 b(16.)21 b Fg(L)n(et)d Fj(\013;)7 b(\014)19 b Fi(2)f Fq(\()p Fj(\006)d Fi([)c Fj(V)f Fq(\))876 2065 y Fp(+)922 2080 y Fg(b)n(e)18 b(p)n(atterns)g(and)h(let)f Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))h Fi(\025)f Fq(3)p Fg(.)g(The)183 2130 y(fol)r(lowing)c(statements)h(ar)n(e)f(e)n(quivalent.)199 2219 y(1.)20 b Fj(\013)p Fi(#)15 b Fg(and)g Fj(\014)r Fi(#)g Fg(ar)n(e)g(identic)n(al)g(up)g(to)g(variable)f(r)n(enaming.)199 2270 y(2.)20 b(Ther)n(e)j(ar)n(e)f(substitutions)h Fj(f)732 2255 y Ff(0)770 2270 y Fq(:)j Fj(v)q(ar)q Fq(\()p Fj(\013)p Fi(#)p Fq(\))g Fi(!)g Fj(v)q(ar)q Fq(\()p Fj(\014)r Fi(#)q Fq(\))1187 2255 y Ff(\003)1229 2270 y Fg(and)d Fj(g)1338 2255 y Ff(0)1376 2270 y Fq(:)j Fj(v)q(ar)q Fq(\()p Fj(\014)r Fi(#)q Fq(\))g Fi(!)253 2320 y Fj(v)q(ar)q Fq(\()p Fj(\013)p Fi(#)p Fq(\))396 2305 y Ff(\003)430 2320 y Fg(such)16 b(that)f Fj(f)634 2305 y Ff(0)646 2320 y Fq(\()p Fj(\013)p Fi(#)p Fq(\))c(=)h Fj(\014)r Fi(#)j Fg(and)h Fj(g)944 2305 y Ff(0)956 2320 y Fq(\()p Fj(\014)r Fi(#)q Fq(\))11 b(=)h Fj(\013)p Fi(#)p Fg(.)199 2372 y(3.)20 b(Ther)n(e)e(ar)n(e)h (substitutions)f Fj(f)23 b Fq(:)18 b Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))h Fi(!)f Fj(v)q(ar)q Fq(\()p Fj(\014)r Fq(\))1089 2356 y Ff(\003)1128 2372 y Fg(and)i Fj(g)f Fq(:)f Fj(v)q(ar)q Fq(\()p Fj(\014)r Fq(\))i Fi(!)e Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))1604 2356 y Ff(\003)253 2421 y Fg(such)e(that)e Fj(f)t Fq(\()p Fj(\013)p Fq(\))f(=)f Fj(\014)17 b Fg(and)f Fj(g)q Fq(\()p Fj(\014)r Fq(\))d(=)e Fj(\013)p Fg(.)p eop %%Page: 10 10 10 9 bop 340 194 a Fg(Pr)n(o)n(of.)20 b Fq(The)12 b(implication)c (\(1\))j Fi(\))g Fq(\(2\))h(holds)e(trivially)m(.)e(The)k(con)o(v)o (erse)g(implication)c(\(2\))k Fi(\))340 244 y Fq(\(1\))j(is)g(a)f (consequence)j(of)d(Theorem)g(14)g(\(cf.)h(also)f(pro)q(of)g(of)g (Corollary)g(15\).)g(The)h(equiv-)340 293 y(alence)h(\(2\))e Fi(,)f Fq(\(3\))i(follo)o(ws)f(from)g(the)h(equalities)g Fj(d)p Fq(\()p Fj(\013)p Fq(\))f(=)g Fj(\013)p Fi(#)o Fq(,)h Fj(\033)q Fq(\()p Fj(\013)p Fi(#)p Fq(\))f(=)g Fj(\013)p Fq(,)g Fj(d)1606 278 y Ff(0)1617 293 y Fq(\()p Fj(\014)r Fq(\))h(=)f Fj(\014)r Fi(#)340 343 y Fq(and)i Fj(\033)448 328 y Ff(0)460 343 y Fq(\()p Fj(\014)r Fi(#)p Fq(\))e(=)h Fj(\014)r Fq(.)h(The)g(existence)h(of)e(a)g(substitution)h Fj(f)1259 328 y Ff(0)1285 343 y Fq(:)e Fj(v)q(ar)q Fq(\()p Fj(\013)p Fi(#)p Fq(\))g Fi(!)g Fj(v)q(ar)q Fq(\()p Fj(\014)r Fi(#)q Fq(\))1666 328 y Ff(\003)1701 343 y Fq(with)340 393 y Fj(f)364 378 y Ff(0)377 393 y Fq(\()p Fj(\013)p Fi(#)o Fq(\))j(=)f Fj(\014)r Fi(#)h Fq(implies)e(for)h(instance)h(the)g (existence)i(of)d(a)g(substitution)h Fj(f)k Fq(:)15 b Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))i Fi(!)340 443 y Fj(v)q(ar)q Fq(\()p Fj(\014)r Fq(\))460 428 y Ff(\003)495 443 y Fq(suc)o(h)d(that)g Fj(f)t Fq(\()p Fj(\013)p Fq(\))f(=)e Fj(\014)r Fq(;)j(just)h(de\014ne)f Fj(f)j Fq(=)12 b Fj(\033)1176 428 y Ff(0)1197 443 y Fi(\016)d Fj(f)1251 428 y Ff(0)1272 443 y Fi(\016)g Fj(d)p Fq(.)340 519 y(Consequen)o(tly)m(,)19 b(in)g(the)g(situation)g(of)f(Corollary)g(6)h(\(resp.)g(of)g(Prop)q (ositions)g(7)g(and)f(8\))340 569 y(language)12 b(equiv)n(alence)i(can) f(also)f(b)q(e)i(decided)g(b)o(y)f(comparing)e(normal)g(forms)h (instead)h(of)340 619 y(testing)i(mem)o(b)q(ership)e(of)g(certain)i(w)o (ords:)f Fj(L)1056 625 y Fh(E)r(;\006)1122 619 y Fq(\()p Fj(\013)p Fq(\))e(=)h Fj(L)1266 625 y Fh(E)r(;\006)1331 619 y Fq(\()p Fj(\014)r Fq(\))i(if)f(and)g(only)f(if)h Fj(\013)p Fi(#)f Fq(and)340 669 y Fj(\014)r Fi(#)i Fq(are)f(iden)o (tical)f(up)h(to)f(v)n(ariable)g(renaming.)f(W)m(e)h(ha)o(v)o(e)h(not)f (in)o(v)o(estigated)h(y)o(et)g(whether)340 719 y(reduction)h(to)e (normal)f(form)f(is)j(less)g(complex)e(than)i(solving)e(the)j(mem)o(b)q (ership)d(problem)340 769 y(whic)o(h)i(is)g(NP-complete)f(\(see)j ([Ang80a)n(,)e(JKS)1083 753 y Fp(+)1111 769 y Fq(94]\).)340 891 y Fk(5)56 b(Equiv)m(alence)17 b(T)-5 b(ests)18 b(Based)h(on)g (Normal)e(F)-5 b(orms)340 979 y Fq(W)m(e)14 b(next)g(sho)o(w)g(the)h(b) q(ene\014ts)g(of)e(our)h(normal)e(form)g(approac)o(h.)340 1051 y Fe(Prop)q(osition)5 b(17.)20 b Fg(L)n(et)14 b Fj(\013;)7 b(\014)14 b Fi(2)d Fq(\()p Fj(\006)g Fi([)d Fj(V)i Fq(\))1010 1035 y Fp(+)1052 1051 y Fg(and)15 b(let)f Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))e Fi(\025)f Fq(4)p Fg(.)j(Supp)n(ose)i(\(i\))e Fj(\013)p Fi(#)g Fg(has)340 1100 y(indep)n(endent)j(variable)e(se)n(gments)h(or)f(\(ii\))g Fj(\013)p Fi(#)g Fg(is)g(line)n(ar.)f(Then)i Fj(L)1407 1106 y Fh(E)r(;\006)1473 1100 y Fq(\()p Fj(\013)p Fq(\))c(=)h Fj(L)1617 1106 y Fh(E)r(;\006)1682 1100 y Fq(\()p Fj(\014)r Fq(\))k Fg(if)340 1150 y(and)f(only)f(if)f Fj(\013)p Fi(#)h Fg(and)g Fj(\014)r Fi(#)h Fg(ar)n(e)e(identic)n(al)h(up)g(to)g (variable)f(r)n(enaming.)340 1221 y(Pr)n(o)n(of.)20 b Fq(\(i\))e(W)m(e)f(sho)o(w)g Fj(L)741 1227 y Fh(E)r(;\006)807 1221 y Fq(\()p Fj(\013)p Fq(\))h(=)f Fj(L)961 1227 y Fh(E)r(;\006)1027 1221 y Fq(\()p Fj(\014)r Fq(\))h(if)f(and)g(only)g (if)g(there)i(are)f(substitutions)340 1271 y Fj(f)24 b Fq(:)18 b Fj(v)q(ar)q Fq(\()p Fj(\013)p Fi(#)p Fq(\))g Fi(!)g Fj(v)q(ar)q Fq(\()p Fj(\014)r Fi(#)q Fq(\))777 1256 y Ff(\003)814 1271 y Fq(and)g Fj(g)i Fq(:)e Fj(v)q(ar)q Fq(\()p Fj(\014)r Fi(#)q Fq(\))g Fi(!)g Fj(v)q(ar)q Fq(\()p Fj(\013)p Fi(#)p Fq(\))1332 1256 y Ff(\003)1369 1271 y Fq(suc)o(h)h(that)f Fj(f)t Fq(\()p Fj(\013)p Fi(#)q Fq(\))g(=)h Fj(\014)r Fi(#)340 1321 y Fq(and)f Fj(g)q Fq(\()p Fj(\014)r Fi(#)q Fq(\))f(=)h Fj(\013)p Fi(#)p Fq(.)f(The)h Fg(if)f Fq(direction)g(is)h(trivially)d(true,)j(so)g(w)o (e)g(pro)o(v)o(e)f(the)h Fg(only)h(if)e Fq(di-)340 1371 y(rection.)i(Let)g Fj(L)602 1377 y Fh(E)r(;\006)667 1371 y Fq(\()p Fj(\013)p Fq(\))g(=)g Fj(L)824 1377 y Fh(E)r(;\006)890 1371 y Fq(\()p Fj(\014)r Fq(\),)g(hence)g Fj(L)1125 1377 y Fh(E)r(;\006)1191 1371 y Fq(\()p Fj(\013)p Fi(#)o Fq(\))g(=)h Fj(L)1369 1377 y Fh(E)r(;\006)1434 1371 y Fq(\()p Fj(\014)r Fi(#)q Fq(\).)e(According)g(to)340 1421 y(Theorem)g(1,)f Fj(\013)p Fi(#)g Fq(and)h Fj(\014)r Fi(#)g Fq(are)h(similar,)c(so)j (let)g Fj(\013)p Fi(#)g Fq(=)g Fj(\013)1272 1427 y Fp(0)1290 1421 y Fj(u)1314 1427 y Fp(1)1333 1421 y Fj(\013)1360 1427 y Fp(1)1378 1421 y Fj(u)1402 1427 y Fp(2)1427 1421 y Fj(:)7 b(:)g(:)f(\013)1510 1427 y Fh(m)p Ff(\000)p Fp(1)1583 1421 y Fj(u)1607 1427 y Fh(m)1638 1421 y Fj(\013)1665 1427 y Fh(m)1714 1421 y Fq(and)340 1471 y Fj(\014)r Fi(#)12 b Fq(=)g Fj(\014)465 1477 y Fp(0)484 1471 y Fj(u)508 1477 y Fp(1)527 1471 y Fj(\014)550 1477 y Fp(1)569 1471 y Fj(u)593 1477 y Fp(2)618 1471 y Fj(:)7 b(:)g(:)e(\014)696 1477 y Fh(m)p Ff(\000)p Fp(1)771 1471 y Fj(u)795 1477 y Fh(m)826 1471 y Fj(\014)849 1477 y Fh(m)881 1471 y Fq(.)14 b(W)m(e)f(sho)o(w:)358 1542 y(1.)20 b(F)m(or)13 b(an)o(y)h Fj(\013)591 1548 y Fh(i)604 1542 y Fq(,)g(there)h(is)f(an)f Fj(f)855 1548 y Fh(i)881 1542 y Fq(:)e Fj(v)q(ar)q Fq(\()p Fj(\013)1010 1548 y Fh(i)1024 1542 y Fq(\))h Fi(!)f Fj(v)q(ar)q Fq(\()p Fj(\014)1207 1548 y Fh(i)1221 1542 y Fq(\))1237 1527 y Ff(\003)1271 1542 y Fq(suc)o(h)j(that)g Fj(f)1474 1548 y Fh(i)1488 1542 y Fq(\()p Fj(\013)1531 1548 y Fh(i)1545 1542 y Fq(\))d(=)h Fj(\014)1639 1548 y Fh(i)1654 1542 y Fq(.)358 1592 y(2.)20 b(F)m(or)d(an)o(y)g Fj(\014)594 1598 y Fh(i)609 1592 y Fq(,)g(there)i(is)e(a)g Fj(g)851 1598 y Fh(i)883 1592 y Fq(:)g Fj(v)q(ar)q Fq(\()p Fj(\014)1014 1598 y Fh(i)1029 1592 y Fq(\))h Fi(!)f Fj(v)q(ar)q Fq(\()p Fj(\013)1228 1598 y Fh(i)1242 1592 y Fq(\))1258 1577 y Ff(\003)1295 1592 y Fq(suc)o(h)h(that)g Fj(g)1506 1598 y Fh(i)1519 1592 y Fq(\()p Fj(\014)1558 1598 y Fh(i)1573 1592 y Fq(\))g(=)g Fj(\013)1684 1598 y Fh(i)1714 1592 y Fq(and)411 1642 y(moreo)o(v)o(er)13 b Fj(g)610 1648 y Fh(i)624 1642 y Fq(\()p Fj(x)p Fq(\))e(=)h Fj(\025)i Fq(whenev)o(er)h Fj(x)f Fq(also)f(o)q(ccurs)i(in)f Fj(\014)1276 1648 y Fh(j)1294 1642 y Fq(,)f Fj(j)h Fi(6)p Fq(=)e Fj(i)i Fq(.)358 1691 y(3.)20 b(The)13 b(lo)q(cal)e(substitutions)i Fj(f)857 1697 y Fh(i)884 1691 y Fq(can)g(b)q(e)g(com)o(bined)e(in)o(to) h(a)g(global)f(substitution)h Fj(f)18 b Fq(suc)o(h)411 1741 y(that)c Fj(f)t Fq(\()p Fj(\013)p Fi(#)p Fq(\))e(=)g Fj(\014)r Fi(#)p Fq(.)358 1791 y(4.)20 b(The)13 b(lo)q(cal)f (substitutions)h Fj(g)858 1797 y Fh(i)885 1791 y Fq(can)g(b)q(e)g(com)o (bined)f(in)o(to)g(a)g(global)g(substitution)h Fj(g)h Fq(suc)o(h)411 1841 y(that)g Fj(g)q Fq(\()p Fj(\014)r Fi(#)q Fq(\))d(=)h Fj(\013)p Fi(#)p Fq(.)340 1912 y(In)k(order)h(to)f (pro)o(v)o(e)g(\(1\))g(and)g(\(2\),)g(w)o(e)g(consider)h(only)e(the)i (case)g(0)e Fj(<)g(i)g(<)h(m)g Fq(\(the)h(cases)340 1962 y Fj(i)12 b Fq(=)g(0)h(and)h Fj(i)e Fq(=)f Fj(m)j Fq(are)g(similar)e (and)h(simpler\).)f(Let)i Fj(c)g Fq(b)q(e)g(the)g(last)f(letter)i(of)e Fj(u)1596 1968 y Fh(i)1623 1962 y Fq(and)h Fj(d)f Fq(b)q(e)340 2012 y(the)i(\014rst)g(letter)f(of)g Fj(u)680 2018 y Fh(i)p Fp(+1)735 2012 y Fq(.)g(W)m(e)f(c)o(ho)q(ose)i Fj(a;)7 b(b)k Fi(2)g Fj(\006)h Fi(n)d(f)p Fj(c;)e(d)p Fi(g)12 b Fq(suc)o(h)j(that)f Fj(a)d Fi(6)p Fq(=)h Fj(b)p Fq(.)358 2083 y(1.)20 b(Consider)11 b Fj(\034)599 2090 y Ff(j)p Fh(\013)p Ff(#j)p Fh(;a;b)712 2083 y Fq(\()p Fj(\014)r Fi(#)p Fq(\).)g Fj(\034)831 2090 y Ff(j)p Fh(\013)p Ff(#)o(j)p Fh(;a;b)943 2083 y Fq(\()p Fj(\014)r Fi(#)q Fq(\))g(can)f(b)q(e)h(written)h(as)e Fj(w)1378 2089 y Fp(0)1397 2083 y Fj(u)1421 2089 y Fp(1)1439 2083 y Fj(w)1469 2089 y Fp(1)1494 2083 y Fj(:)d(:)g(:)f(w)1580 2089 y Fh(m)p Ff(\000)p Fp(1)1653 2083 y Fj(u)1677 2089 y Fh(m)1709 2083 y Fj(w)1739 2089 y Fh(m)1770 2083 y Fq(,)411 2133 y(where)21 b Fj(w)567 2139 y Fh(i)602 2133 y Fq(=)h Fj(\034)674 2140 y Ff(j)p Fh(\013)p Ff(#j)p Fh(;a;b)787 2133 y Fq(\()p Fj(\014)826 2139 y Fh(i)841 2133 y Fq(\).)d(Since)i Fj(L)1031 2139 y Fh(E)r(;\006)1096 2133 y Fq(\()p Fj(\013)p Fi(#)p Fq(\))h(=)g Fj(L)1280 2139 y Fh(E)r(;\006)1345 2133 y Fq(\()p Fj(\014)r Fi(#)q Fq(\),)d(there)j(is)e(a)f Fj(\033)j Fq(suc)o(h)411 2183 y(that)c Fj(\033)q Fq(\()p Fj(\013)p Fi(#)p Fq(\))h(=)h Fj(w)711 2189 y Fp(0)729 2183 y Fj(u)753 2189 y Fp(1)771 2183 y Fj(w)801 2189 y Fp(1)827 2183 y Fj(:)7 b(:)g(:)e(w)912 2189 y Fh(m)p Ff(\000)p Fp(1)986 2183 y Fj(u)1010 2189 y Fh(m)1041 2183 y Fj(w)1071 2189 y Fh(m)1102 2183 y Fq(.)18 b(Note)h(that)f(if)g Fj(\013)1401 2189 y Fh(i)1432 2183 y Fq(is)h(b)q(et)o(w)o(een)g(the)g Fj(k)q Fq(th)411 2232 y(app)q(earance)d(of)f Fj(c)g Fq(and)g(the)h Fj(l)q Fq(th)g(app)q(earance)g(of)f Fj(d)g Fq(in)g Fj(\013)p Fi(#)o Fq(,)g(then)h Fj(w)1490 2238 y Fh(i)1519 2232 y Fq(is)f(b)q(et)o(w)o(een)i(the)411 2282 y Fj(k)q Fq(th)i(app)q (earance)g(of)f Fj(c)h Fq(and)f(the)h Fj(l)q Fq(th)g(app)q(earance)h (of)e Fj(d)g Fq(in)g Fj(\034)1421 2289 y Ff(j)p Fh(\013)p Ff(#j)p Fh(;a;b)1534 2282 y Fq(\()p Fj(\014)r Fi(#)q Fq(\).)g(Since)h Fj(\033)411 2332 y Fq(cannot)f(in)o(tro)q(duce)h(the)g (constan)o(ts)h Fj(c)e Fq(and)g Fj(d)p Fq(,)f(it)h(follo)o(ws)f Fj(\033)q Fq(\()p Fj(\013)1432 2338 y Fh(i)1446 2332 y Fq(\))i(=)g Fj(w)1562 2338 y Fh(i)1575 2332 y Fq(.)f(As)h(in)f(the) 411 2382 y(pro)q(of)f(of)f(Lemma)e(4,)j(w)o(e)g(obtain)f(a)h (substitution)g Fj(f)1262 2388 y Fh(i)1293 2382 y Fq(:)f Fj(v)q(ar)q Fq(\()p Fj(\013)1427 2388 y Fh(i)1441 2382 y Fq(\))h Fi(!)f Fj(v)q(ar)q Fq(\()p Fj(\014)1634 2388 y Fh(i)1649 2382 y Fq(\))1665 2367 y Ff(\003)1702 2382 y Fq(suc)o(h)411 2432 y(that)e Fj(f)521 2438 y Fh(i)535 2432 y Fq(\()p Fj(\013)578 2438 y Fh(i)592 2432 y Fq(\))d(=)h Fj(\014)686 2438 y Fh(i)700 2432 y Fq(.)p eop %%Page: 11 11 11 10 bop 200 194 a Fq(2.)20 b(Let)c Fj(\034)k Fq(b)q(e)c(the)g (substitution)f(whic)o(h)g(enco)q(des)i(only)e(v)n(ariables)f(from)g Fj(v)q(ar)q Fq(\()p Fj(\013)1477 200 y Fh(i)1491 194 y Fq(\).)h(That)253 244 y(is,)h Fj(\034)5 b Fq(\()p Fj(x)p Fq(\))15 b(=)g Fj(\034)468 251 y Ff(j)p Fh(\014)q Ff(#)q(j)p Fh(;a;b)580 244 y Fq(\()p Fj(x)p Fq(\))h(if)f Fj(x)g Fi(2)g Fj(v)q(ar)q Fq(\()p Fj(\013)880 250 y Fh(i)894 244 y Fq(\))h(and)g Fj(\034)5 b Fq(\()p Fj(x)p Fq(\))15 b(=)g Fj(\025)i Fq(otherwise.)f(Since)h Fj(\013)p Fi(#)e Fq(has)253 293 y(indep)q(enden)o(t)g(v)n(ariable)e(segmen)o(ts,)h(it)f (follo)o(ws)562 376 y Fj(\034)5 b Fq(\()p Fj(\013)p Fi(#)o Fq(\))12 b(=)g Fj(u)744 382 y Fp(0)762 376 y Fj(u)786 382 y Fp(1)811 376 y Fj(:)7 b(:)g(:)f(u)891 382 y Fh(i)904 376 y Fj(\034)922 383 y Ff(j)p Fh(\014)q Ff(#)q(j)p Fh(;a;b)1034 376 y Fq(\()p Fj(\013)1077 382 y Fh(i)1090 376 y Fq(\))p Fj(u)1130 382 y Fh(i)p Fp(+1)1193 376 y Fj(:)h(:)g(:)e(u)1272 382 y Fh(m)1304 376 y Fj(:)253 459 y Fq(Since)18 b Fj(L)393 465 y Fh(E)r(;\006)459 459 y Fq(\()p Fj(\013)p Fi(#)o Fq(\))g(=)g Fj(L)634 465 y Fh(E)r(;\006)700 459 y Fq(\()p Fj(\014)r Fi(#)p Fq(\),)g(there)g(is)g(a)f(substitution)h Fj(\033)h Fq(suc)o(h)f(that)g Fj(\033)q Fq(\()p Fj(\014)r Fi(#)p Fq(\))g(=)253 509 y Fj(u)277 515 y Fp(0)296 509 y Fj(u)320 515 y Fp(1)345 509 y Fj(:)7 b(:)g(:)e(u)424 515 y Fh(i)438 509 y Fj(\034)456 516 y Ff(j)p Fh(\014)q Ff(#j)p Fh(;a;b)567 509 y Fq(\()p Fj(\013)610 515 y Fh(i)624 509 y Fq(\))p Fj(u)664 515 y Fh(i)p Fp(+1)727 509 y Fj(:)i(:)g(:)e(u) 806 515 y Fh(m)837 509 y Fq(.)16 b(Since)i Fj(\033)f Fq(cannot)g(in)o(tro)q(duce)h(the)f(constan)o(ts)h Fj(c)253 559 y Fq(and)e Fj(d)p Fq(,)f(it)g(follo)o(ws)g Fj(\033)q Fq(\()p Fj(\014)631 565 y Fh(i)645 559 y Fq(\))g(=)h Fj(\034)742 566 y Ff(j)p Fh(\014)q Ff(#j)p Fh(;a;b)853 559 y Fq(\()p Fj(\013)896 565 y Fh(i)910 559 y Fq(\))g(and)g Fj(\033)q Fq(\()p Fj(\014)1089 565 y Fh(j)1107 559 y Fq(\))f(=)g Fj(\025)h Fq(for)g(ev)o(ery)g Fj(j)i Fi(6)p Fq(=)d Fj(i)p Fq(.)h(As)g(in)253 609 y(the)d(pro)q(of)e(of)g(Lemma)e (4,)i(w)o(e)h(obtain)f(a)g(substitution)h Fj(g)1131 615 y Fh(i)1156 609 y Fq(:)f Fj(v)q(ar)q Fq(\()p Fj(\014)1281 615 y Fh(i)1296 609 y Fq(\))h Fi(!)f Fj(v)q(ar)q Fq(\()p Fj(\013)1483 615 y Fh(i)1497 609 y Fq(\))1513 594 y Ff(\003)1544 609 y Fq(suc)o(h)253 659 y(that)17 b Fj(g)366 665 y Fh(i)380 659 y Fq(\()p Fj(\014)419 665 y Fh(i)433 659 y Fq(\))g(=)g Fj(\013)542 665 y Fh(i)556 659 y Fq(.)f(Moreo)o(v)o(er)i Fj(g)790 665 y Fh(i)803 659 y Fq(\()p Fj(x)p Fq(\))f(=)g Fj(\025)g Fq(whenev)o(er)i Fj(x)d Fi(2)h Fj(v)q(ar)q Fq(\()p Fj(\014)1339 665 y Fh(i)1354 659 y Fq(\))11 b Fi(\\)g Fj(v)q(ar)q Fq(\()p Fj(\014)1522 665 y Fh(j)1541 659 y Fq(\))17 b(for)253 708 y(some)c Fj(j)h Fi(6)p Fq(=)e Fj(i)p Fq(.)200 758 y(3.)20 b(Let)d Fj(x)d Fi(2)h Fj(v)q(ar)q Fq(\()p Fj(\013)p Fi(#)p Fq(\).)h(Since)g Fj(\013)p Fi(#)g Fq(has)g(indep)q(enden)o(t)h(v)n(ariable)e(segmen)o(ts,)g(there)j(is)d (ex-)253 808 y(actly)f(one)h(index)f Fj(i)h Fq(suc)o(h)g(that)f Fj(x)e Fi(2)g Fj(v)q(ar)q Fq(\()p Fj(\013)940 814 y Fh(i)954 808 y Fq(\).)i(De\014ne)h Fj(f)t Fq(\()p Fj(x)p Fq(\))e(=)f Fj(f)1282 814 y Fh(i)1296 808 y Fq(\()p Fj(x)p Fq(\).)i(The)h (substitu-)253 858 y(tion)f Fj(f)k Fq(obtained)c(in)f(this)h(manner)f (is)h(w)o(ell-de\014ned)g(and)g Fj(f)t Fq(\()p Fj(\013)p Fi(#)p Fq(\))e(=)g Fj(\014)r Fi(#)p Fq(.)200 908 y(4.)20 b(De\014ne)532 972 y Fj(g)q Fq(\()p Fj(x)p Fq(\))12 b(=)664 914 y Fa(\032)701 945 y Fj(g)721 951 y Fh(i)735 945 y Fq(\()p Fj(x)p Fq(\))26 b(if)13 b Fj(x)e Fi(2)g Fj(v)q(ar)q Fq(\()p Fj(\014)1031 951 y Fh(i)1046 945 y Fq(\))e Fi(n)1101 914 y Fa(S)1136 958 y Fh(j)r Ff(6)p Fp(=)p Fh(i)1197 945 y Fj(v)q(ar)q Fq(\()p Fj(\014)1299 951 y Fh(j)1318 945 y Fq(\))701 998 y Fj(\025)78 b Fq(otherwise)253 1070 y(The)15 b(substitution)f Fj(g)h Fq(is)e(w)o(ell-de\014ned)i(and)e (furthermore)h Fj(g)q Fq(\()p Fj(\014)r Fi(#)q Fq(\))e(=)g Fj(\013)p Fi(#)o Fq(.)183 1151 y(\(ii\))h(If)g Fj(\013)p Fi(#)h Fq(is)f(linear,)g(then)i(it)e(has)h(indep)q(enden)o(t)i(v)n (ariable)c(segmen)o(ts.)183 1232 y(It)i(has)g(already)g(b)q(een)h(sho)o (wn)f(b)o(y)g(Jiang)f Fg(et)i(al.)f Fq([JKS)1037 1216 y Fp(+)1065 1232 y Fq(94)o(])g(that)g Fj(L)1250 1238 y Fh(E)r(;\006)1315 1232 y Fq(\()p Fj(\013)p Fq(\))e Fi(\022)g Fj(L)1458 1238 y Fh(E)r(;\006)1524 1232 y Fq(\()p Fj(\014)r Fq(\))j(is)183 1281 y(decidable)g(if)g Fj(\014)i Fq(is)e(a)g(one-v)n(ariable)g(pattern)h(and)f Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))f Fi(\025)g Fq(2.)g(Th)o(us)i(our)f(next)h (result)183 1331 y(is)g(not)g(surprising.)g(Its)h(pro)q(of,)e(ho)o(w)o (ev)o(er,)i(is)f(m)o(uc)o(h)f(more)g(complicated)g(than)h(exp)q(ected) 183 1381 y(b)q(ecause)f(only)e(one)h(normal)e(form)g(is)i(assumed)g(to) f(b)q(e)i(a)e(one-v)n(ariable)g(pattern.)183 1462 y Fe(Prop)q(ositi)o (on)5 b(18.)21 b Fg(L)n(et)16 b Fj(\013;)7 b(\014)17 b Fi(2)e Fq(\()p Fj(\006)f Fi([)c Fj(V)g Fq(\))867 1447 y Fp(+)911 1462 y Fg(b)n(e)17 b(p)n(atterns)g(and)h(let)e Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))g Fi(\025)f Fq(3)p Fg(.)i(If)f Fj(\013)p Fi(#)183 1512 y Fg(is)e(a)g(one-variable)h(p)n (attern,)f(then)g Fj(L)770 1518 y Fh(E)r(;\006)836 1512 y Fq(\()p Fj(\013)p Fq(\))d(=)h Fj(L)978 1518 y Fh(E)r(;\006)1044 1512 y Fq(\()p Fj(\014)r Fq(\))j Fg(if)f(and)h(only)f(if)g Fj(\013)p Fi(#)g Fg(and)h Fj(\014)r Fi(#)g Fg(ar)n(e)183 1561 y(identic)n(al)f(up)i(to)e(variable)h(r)n(enaming.)183 1642 y Fq(W)m(e)e(conclude)i(with)f(a)g(result)h(similar)d(to)i(Prop)q (osition)f(18;)g(again)g(w)o(e)i(ha)o(v)o(e)f(to)g(omit)e(the)183 1692 y(pro)q(of)h(due)i(to)e(space)i(limitations.)183 1773 y Fe(Prop)q(ositi)o(on)5 b(19.)21 b Fg(L)n(et)13 b Fj(\013;)7 b(\014)13 b Fi(2)e Fq(\()p Fj(\006)e Fi([)d Fj(V)j Fq(\))846 1758 y Fp(+)887 1773 y Fg(b)n(e)k(p)n(atterns)g(and)h (let)f Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))f Fi(\025)g Fq(4)p Fg(.)g(Supp)n(ose)183 1822 y Fj(\013)p Fi(#)f Fq(=)h Fj(\013)313 1828 y Fp(0)331 1822 y Fj(u)355 1828 y Fp(1)373 1822 y Fj(\013)400 1828 y Fp(1)419 1822 y Fj(u)443 1828 y Fp(2)468 1822 y Fj(:)7 b(:)g(:)e(\013)550 1828 y Fh(m)p Ff(\000)p Fp(1)624 1822 y Fj(u)648 1828 y Fh(m)679 1822 y Fj(\013)706 1828 y Fh(m)737 1822 y Fg(,)15 b(wher)n(e)f Fi(j)p Fj(\013)921 1828 y Fp(0)939 1822 y Fi(j)d(\024)h Fq(1)p Fg(,)j Fi(j)p Fj(\013)1094 1828 y Fh(m)1124 1822 y Fi(j)d(\024)g Fq(1)p Fg(,)i(and)i Fi(j)p Fj(\013)1360 1828 y Fh(i)1373 1822 y Fi(j)11 b Fq(=)h(1)p Fg(,)j Fq(0)c Fj(<)h(i)g(<)183 1872 y(m)p Fg(.)j(In)h(other)f(wor)n(ds,)f Fj(\013)p Fi(#)h Fg(do)n(es)g(not)h(c)n (ontain)g(c)n(onse)n(cutive)g(variables.)e(Then)i Fj(L)1455 1878 y Fh(E)r(;\006)1520 1872 y Fq(\()p Fj(\013)p Fq(\))c(=)183 1922 y Fj(L)211 1928 y Fh(E)r(;\006)276 1922 y Fq(\()p Fj(\014)r Fq(\))k Fg(if)e(and)i(only)f(if)f Fj(\013)p Fi(#)h Fg(and)g Fj(\014)r Fi(#)h Fg(ar)n(e)e(identic)n(al)h(up)g(to)g (variable)f(r)n(enaming.)183 2003 y Fq(Note)22 b(that)g(if)f(a)h (pattern)h(in)e(normal)f(form)h(is)g(linear,)g(then)i(its)f(canonical)f (form)g(is)183 2053 y Fj(x)207 2059 y Fp(0)225 2053 y Fj(u)249 2059 y Fp(1)267 2053 y Fj(x)291 2059 y Fp(1)310 2053 y Fj(u)334 2059 y Fp(2)359 2053 y Fj(:)7 b(:)g(:)e(x)438 2059 y Fh(m)p Ff(\000)p Fp(1)512 2053 y Fj(u)536 2059 y Fh(m)567 2053 y Fj(x)591 2059 y Fh(m)623 2053 y Fq(.)12 b(Therefore,)j(Prop)q(osition)d(19)h(also)g(generalizes)h(Prop)q (osition)183 2102 y(17)f(\(ii\).)183 2235 y Fk(6)56 b(Related)17 b(W)-5 b(ork)183 2332 y Fq(In)18 b(this)g(pap)q(er,)h(w)o(e)f(did)g (not)g(in)o(v)o(estigate)g(the)h(cases)h Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))f Fi(\024)g Fq(2.)e(In)i([DF96)o(],)e(it)h(is) 183 2382 y(sho)o(wn)i(that)h(the)g(equiv)n(alence)g(of)e(E-patterns)j (is)f(decidable)f(for)h Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))i(=)f(1)f(and)183 2432 y(a)e(necessary)i(condition)e(for)f(the)i (equiv)n(alence)g(of)e(E-patterns)j(in)e(case)h Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))h(=)g(2)p eop %%Page: 12 12 12 11 bop 340 194 a Fq(is)19 b(giv)o(en.)e(Moreo)o(v)o(er,)i(D\023)-21 b(an)o(yi)17 b(and)h(F)q(\177)-22 b(ul\177)h(op)18 b([DF96)o(])g(claim) f(that)h(for)g Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))i Fi(\025)f Fq(2)g(the)340 244 y(inclusion)14 b(and)g(hence)i(the)e (equiv)n(alence)h(problem)e(for)h(similar)d(E-patterns)16 b(is)e(decidable)340 293 y(b)o(y)d(testing)h(mem)o(b)q(ership)d(of)h(a) h(certain)h(w)o(ord;)e(see)i(b)q(elo)o(w)f(for)g(the)g(exact)h(claim.)c (Ho)o(w)o(ev)o(er,)340 343 y(Example)14 b(2)g(refutes)i(the)g(claim.)c (T)m(o)i(see)i(this,)e(let)h(us)g(\014rst)h(recall)f(the)g (de\014nition)f(of)h(the)340 393 y(substitution)f Fj(\034)589 399 y Fh(k)q(;a;b)676 393 y Fq(in)g([DF96)n(])g(\(whic)o(h)g(is)f(a)h (mo)q(di\014cation)e(of)h(De\014nition)g(3\).)340 476 y Fe(De\014nition)t(20.)21 b Fq(Let)10 b Fj(\013)h Fq(=)h Fj(\013)816 482 y Fp(0)834 476 y Fj(u)858 482 y Fp(1)876 476 y Fj(\013)903 482 y Fp(1)922 476 y Fj(u)946 482 y Fp(2)971 476 y Fj(:)7 b(:)g(:)e(\013)1053 482 y Fh(m)p Ff(\000)p Fp(1)1127 476 y Fj(u)1151 482 y Fh(m)1182 476 y Fj(\013)1209 482 y Fh(m)1252 476 y Fi(2)11 b Fq(\()p Fj(\006)r Fi([)p Fj(V)f Fq(\))1419 461 y Fp(+)1447 476 y Fq(,)e Fj(V)21 b Fq(=)12 b Fi(f)p Fj(x)1601 482 y Fp(1)1619 476 y Fj(;)7 b(:)g(:)g(:)e(;)i(x)1736 482 y Fh(n)1758 476 y Fi(g)p Fq(,)340 526 y(and)14 b Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))f Fi(\025)f Fq(2.)h(Moreo)o(v)o(er,)h(let)h Fj(max)d Fq(=)g(max)n Fi(fj)p Fj(u)1199 532 y Fh(i)1212 526 y Fi(j)g(j)g Fq(1)g Fi(\024)g Fj(i)g Fi(\024)g Fj(m)p Fi(g)p Fq(.)i(F)m(or)g(ev)o(ery)g Fj(a;)7 b(b)14 b Fq(in)340 576 y Fj(\006)r Fq(,)h Fj(a)c Fi(6)p Fq(=)h Fj(b)p Fq(,)h(and)h Fj(k)e(>)g Fq(0,)h(de\014ne)i Fj(\034)864 582 y Fh(k)q(;a;b)948 576 y Fq(:)d Fj(V)20 b Fi(!)12 b(f)p Fj(a;)7 b(b)p Fi(g)1171 561 y Ff(\003)1202 576 y Fq(b)o(y)438 666 y Fj(\034)456 672 y Fh(k)q(;a;b)529 666 y Fq(\()p Fj(x)569 672 y Fh(i)583 666 y Fq(\))k(=)h Fj(ab)694 649 y Fh(max)762 666 y Fj(b)780 649 y Fh(k)q Ff(\003)p Fh(i)p Fp(+1)871 666 y Fj(aab)933 649 y Fh(max)1002 666 y Fj(b)1020 649 y Fh(k)q Ff(\003)p Fh(i)p Fp(+2)1111 666 y Fj(a)7 b(:)g(:)g(:)e(ab)1235 649 y Fh(max)1303 666 y Fj(b)1321 649 y Fh(k)q Ff(\003)p Fp(\()p Fh(i)p Fp(+1\))1438 666 y Fj(a;)29 b Fq(1)12 b Fi(\024)f Fj(i)h Fi(\024)g Fj(n:)340 747 y Fe(Claim:)17 b Fg(L)n(et)i Fj(car)q(d)p Fq(\()p Fj(\006)r Fq(\))f Fi(\025)g Fq(2)g Fg(and)h(let)f Fj(\013;)7 b(\014)20 b Fi(2)e Fq(\()p Fj(\006)c Fi([)e Fj(V)d Fq(\))1258 732 y Fp(+)1304 747 y Fg(b)n(e)19 b(similar)e(p)n(atterns,)h(wher)n(e)340 793 y Fj(\013)12 b Fq(=)g Fj(\013)450 799 y Fp(0)468 793 y Fj(u)492 799 y Fp(1)510 793 y Fj(\013)537 799 y Fp(1)556 793 y Fj(u)580 799 y Fp(2)605 793 y Fj(:)7 b(:)g(:)e(\013)687 799 y Fh(m)p Ff(\000)p Fp(1)761 793 y Fj(u)785 799 y Fh(m)816 793 y Fj(\013)843 799 y Fh(m)874 793 y Fg(.)15 b(L)n(et)g Fj(k)g Fg(b)n(e)g(the)g(numb)n(er)h(of)e(variable)h(o)n(c)n (curr)n(enc)n(es)g(in)g Fj(\014)340 838 y Fg(and)i(\014x)f(two)f (distinct)g(letters)g Fj(a;)7 b(b)12 b Fi(2)g Fj(\006)r Fg(.)k(Then)g Fj(\034)1135 844 y Fh(k)q Fp(+)p Fh(m;a;b)1263 838 y Fq(\()p Fj(\013)p Fq(\))d Fi(2)g Fj(L)1404 844 y Fh(E)r(;\006)1469 838 y Fq(\()p Fj(\014)r Fq(\))k Fg(if)e(and)h(only) g(if)340 884 y(ther)n(e)f(is)f(a)h(substitution)g Fj(h)d Fq(:)f Fj(v)q(ar)q Fq(\()p Fj(\014)r Fq(\))i Fi(!)e Fj(v)q(ar)q Fq(\()p Fj(\013)p Fq(\))1115 869 y Ff(\003)1149 884 y Fg(such)16 b(that)e Fj(h)p Fq(\()p Fj(\014)r Fq(\))f(=)f Fj(\013)p Fg(.)340 975 y Fq(Let)18 b Fj(\013)f Fq(and)g Fj(\014)j Fq(b)q(e)e(as)g(in)f(Example)f(2)h(and)g(note)h(that)f Fj(\034)1261 981 y Fp(6)p Fh(;a;b)1332 975 y Fq(\()p Fj(y)1368 981 y Fh(i)1382 975 y Fq(\))h(=)g Fj(abw)1536 981 y Fh(y)1553 985 y Fd(i)1567 975 y Fj(ba)f Fq(for)g(some)340 1021 y(sub)o(w)o(ord)h Fj(w)538 1027 y Fh(y)555 1031 y Fd(i)586 1021 y Fq(of)f Fj(\034)655 1027 y Fp(6)p Fh(;a;b)726 1021 y Fq(\()p Fj(y)762 1027 y Fh(i)776 1021 y Fq(\).)g(It)g(follo)o (ws)e(as)j(in)e(Example)g(2)g(that)i Fj(\034)1439 1027 y Fp(6)p Fh(;a;b)1510 1021 y Fq(\()p Fj(\013)p Fq(\))e Fi(2)h Fj(L)1658 1027 y Fh(E)r(;\006)1723 1021 y Fq(\()p Fj(\014)r Fq(\))340 1067 y(but)d(there)i(is)d(no)h(substitution)g Fj(h)g Fq(with)f Fj(h)p Fq(\()p Fj(\014)r Fq(\))g(=)f Fj(\013)p Fq(.)340 1201 y Fk(References)340 1297 y Fn([Ang80a])21 b(D.)13 b(Angluin.)21 b(Finding)16 b(patterns)f(common)f(to)g(a)f(set)h (of)f(strings.)21 b Fl(Journal)12 b(of)i(Com-)506 1342 y(puter)f(and)f(System)h(Scienc)n(es)e Fm(21)p Fn(,)h(pages)i(46{62,)g (1980.)340 1388 y([Ang80b])22 b(D.)12 b(Angluin.)19 b(Inductiv)o(e)c (inference)f(of)f(formal)h(languages)h(from)e(p)q(ositiv)o(e)i(data.)i Fl(In-)506 1434 y(formation)12 b(and)h(Contr)n(ol)g Fm(45)p Fn(,)f(pages)i(117{135,)g(1980.)340 1479 y([DF96])52 b(G.)13 b(D\023)-19 b(an)o(yi)17 b(and)f(Z.)d(F)q(\177)-20 b(ul\177)h(op.)26 b(A)15 b(note)h(on)g(the)g(equiv)n(alence)i(problem)f (of)f(E-patterns.)506 1525 y Fl(Information)c(Pr)n(o)n(c)n(essing)f(L)n (etters)h Fm(57)p Fn(,)h(pages)h(125{128,)g(1996.)340 1571 y([IJ91])72 b(O.)12 b(Ibarra)k(and)f(T.)d(Jiang.)24 b(Learning)16 b(regular)g(languages)h(from)e(coun)o(terexamples.)506 1616 y Fl(Journal)e(of)g(Computer)g(and)f(System)g(Scienc)n(es)f Fm(43)p Fn(,)i(pages)h(299{316,)g(1991.)340 1662 y([JKS)422 1646 y Fo(+)447 1662 y Fn(94])21 b(T.)12 b(Jiang,)f(E.)h(Kin)o(b)q(er,) f(A.)h(Salomaa,)f(K.)h(Salomaa,)g(and)e(S.)j(Y)m(u.)i(P)o(attern)c (languages)506 1708 y(with)17 b(and)h(without)f(erasing.)29 b Fl(Intern.)15 b(J.)i(Computer)f(Math.)g Fm(50)p Fn(,)g(pages)h (147{163,)506 1753 y(1994.)340 1799 y([JSSY95])k(T.)12 b(Jiang,)17 b(A.)12 b(Salomaa,)17 b(K.)12 b(Salomaa,)18 b(and)f(S.)12 b(Y)m(u.)27 b(Decision)18 b(problems)g(for)e(pat-)506 1845 y(terns.)i Fl(Journal)12 b(of)h(Computer)g(and)f(System)h(Scienc)n (es)e Fm(50)p Fn(,)h(pages)i(53{63,)f(1995.)340 1890 y([KMU95])21 b(P)m(.)12 b(Kilp)q(el\177)-19 b(ainen)q(,)11 b(H.)h(Mannila,)f(and)f(E.)i(Ukk)o(onen.)k(MDL)9 b(learning)j(of)c (unions)j(of)e(sim-)506 1936 y(ple)h(pattern)g(languages)g(from)f(p)q (ositiv)o(e)i(examples.)17 b(In)9 b Fl(Pr)n(o)n(c)n(e)n(e)n(dings)e(of) i(the)g(2nd)f(Eur)n(o-)506 1982 y(p)n(e)n(an)j(Confer)n(enc)n(e)e(on)i (Computational)e(L)n(e)n(arning)h(The)n(ory)p Fn(,)f(pages)j(252{260.)g (Lecture)506 2027 y(Notes)h(in)h(Computer)g(Science)g Fm(904)p Fn(,)f(Berlin:)h(Springer)h(V)m(erlag,)e(1995.)340 2073 y([OU95])47 b(E.)13 b(Ohlebusc)o(h)e(and)f(E.)i(Ukk)o(onen.)17 b(On)9 b(the)h(the)f(equiv)n(alence)k(problem)d(for)g(E-pattern)506 2119 y(languages.)48 b(Rep)q(ort)24 b(95-04,)f(F)m(orsc)o(h)o(ungsb)q (eric)o(h)o(te)i(der)e(T)m(ec)o(hnisc)o(hen)h(F)m(akult\177)-19 b(at,)506 2164 y(Abteilung)16 b(Informationstec)o(hnik,)f(Univ)o (ersit\177)-19 b(at)15 b(Bielefeld,)g(1995.)340 2210 y([Sal94])56 b(A.)12 b(Salomaa.)21 b(P)o(atterns.)f Fl(Bul)r(letin)12 b(of)i(the)g(Eur)n(op)n(e)n(an)e(Asso)n(ciation)f(for)j(The)n(or)n (etic)n(al)506 2256 y(Computer)f(Scienc)n(e)f Fm(54)p Fn(,)g(pages)i(194{206,)g(1994.)340 2301 y([Sal95])56 b(A.)12 b(Salomaa.)27 b(Return)16 b(to)g(patterns.)25 b Fl(Bul)r(letin)14 b(of)h(the)g(Eur)n(op)n(e)n(an)f(Asso)n(ciation)f (for)506 2347 y(The)n(or)n(etic)n(al)f(Computer)h(Scienc)n(e)e Fm(55)p Fn(,)i(pages)h(144{155,)f(1995.)340 2424 y(This)h(article)g(w)o (as)f(pro)q(cessed)i(using)f(the)f(L)968 2415 y Fo(A)985 2424 y Fn(T)1007 2432 y(E)1028 2424 y(X)f(macro)h(pac)o(k)n(age)h(with) g(LLNCS)e(st)o(yle)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF