# HG changeset patch # User urbanc # Date 1287744301 0 # Node ID 9563a9cd28d37b902709bc36b5f0a56cca75ea75 # Parent a53606765839f2ad646600a043c831d6860095b6 added a paper by Constable about the Myhill-Nerode in Nuprl using DFA and a paper by tobias about RegExp->DFA translation diff -r a53606765839 -r 9563a9cd28d3 Literature/FormalizingAutomata-Constable.pdf Binary file Literature/FormalizingAutomata-Constable.pdf has changed diff -r a53606765839 -r 9563a9cd28d3 Literature/nipkow-tphols98.ps --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Literature/nipkow-tphols98.ps Fri Oct 22 10:45:01 2010 +0000 @@ -0,0 +1,2821 @@ +%!PS-Adobe-2.0 +%%Creator: dvipsk 5.58f Copyright 1986, 1994 Radical Eye Software +%%Title: main.dvi +%%Pages: 16 +%%PageOrder: Ascend +%%BoundingBox: 0 0 596 842 +%%DocumentPaperSizes: a4 +%%EndComments +%DVIPSCommandLine: dvips main.dvi -o main.ps +%DVIPSParameters: dpi=600, compressed, comments removed +%DVIPSSource: TeX output 1998.08.20:0849 +%%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 600 600 (main.dvi) +@start /Fa 38 122 df44 D<121C127F12FFA412FE12380808778718 +>46 D<1370EA01FC1203A413F8EA00E01300B0121C127F5AA45A12380E20779F18>58 +D<161C163CA2167C16FCA21501821503A2ED077E150F150E151CA21538A2157015F015E0 +EC01C0A2913803807F82EC0700A2140E141E141C5CA25CA25C49B6FCA25B913880003F49 +C7EA1F80A2130E131E131C133C13385B13F05B12011203D80FF0EC3FC0D8FFFE903807FF +FEA32F367BB539>65 D<0107B612C04915F017FC903A003F8000FE177FEF3F8092C7121F +A24A15C0A2147EA214FE18804A143FA20101ED7F00177E4A5C16010103EC03F04C5A4AEB +1FC091B6C7FC495C9139F0007F804AEB0FC0707E010F6E7E834A1301A2011F81A25CA213 +3F5F91C71203A2494A5AA2017E4A5A4C5A01FE4A5A4CC7FC49EB01FE0001EC07FC007FB6 +12F0B712C04BC8FC32337BB236>II< +0107B712F05B18E0903A003F80001F1707170392C7FC17015C18C0147EA214FEA24A130E +A20101EC1E03041C13804A91C7FC163C13035E9138F001F891B5FC5B5EECE0011500130F +5E5C1707011F01015BEEC00E0280141E92C7121C133F173C91C812381778495DA2017E14 +014C5A01FE14074C5A49141F00014AB45A007FB7FCB8FC94C7FC34337CB234>69 +D<0107B712E05B18C0903A003F80003F170F170792C7FC17035C1880147EA214FEA25C16 +1C0101EC3C07043813004A91C7FCA20103147816704A13F0150349B5FCA25EECE003130F +6F5A14C0A2011F13035E1480A2013F90C9FCA291CAFCA25BA2137EA213FEA25B1201387F +FFFCB5FCA233337CB232>I<0107B548B512C0495CA2903C003FC0000FF0004B5CA292C7 +5BA24A141F60147EA202FE143F95C7FC5CA201015D177E5CA2010315FE5F5C91B6FC5B5F +9138E00001A2010F14035F5CA2011F14075F5CA2013F140F5F91C7FCA249141F5F137EA2 +01FE143F94C8FC5B00015D3B7FFFF01FFFFCB55BA23A337BB239>72 +D<010FB51280A216009038003FC05DA292C7FCA25CA2147EA214FEA25CA21301A25CA213 +03A25CA21307A25CA2130FA25CA2131FA25CA2133FA291C8FCA25BA2137EA213FEA25B12 +01B512F8A25C21337BB21E>I<0107B512C05BA29026003FC0C7FC5DA292C8FCA25CA214 +7EA214FEA25CA21301A25CA21303A25CA21307A25CA2130FA25C17E0011F140117C05C16 +03013F1580160791C7FCEE0F005B5E017E143EA201FE5CED01FC4913030001EC1FF8007F +B6FCB7FC5E2B337CB230>76 D<902607FFC0ED7FFC4917FF81D9003F4B1300611803023B +ED077CA2027BED0EFC610273151C1838DAF1F01439F071F014E118E10101ED01C36102C1 +EC0383EF070301031607050E5BEC80F8171C0107ED380F6102001470A249EDE01FDC01C0 +90C7FC130EEE0380011E017C5C933807003E011C140EA2013C4A137E187C01385C5E0178 +16FC6F485B1370ED3FC001F0EC80016000011500D807F81503277FFF803E90B512C0B5EB +3C01151C46337BB245>I<902607FF8090383FFFC0496D5BA2D9001F913803F8004A6C6D +5A6060EC3BF0027B140360EC71F8A202F11407DAF0FC91C7FC14E0A20101017E5B170E14 +C0810103151EEE801CEC801FA20107ECC03C030F1338140016E049010713781770010E14 +F01503011E15F0705A011C1301A2013C14FD03005B133816FF0178147F5F0170143FA213 +F070C8FC1201EA07F8267FFF807FB5140EA23A337BB239>I<0107B612C04915F883903A +003F8001FEEE003FEF1F8092C713C0170F5C18E0147EA214FEEF1FC05CA201011680173F +4A1500177E010315FE5F4AEB03F8EE07E00107EC3FC091B6C7FC16F802E0C9FC130FA25C +A2131FA25CA2133FA291CAFCA25BA2137EA213FEA25B1201387FFFF0B5FCA233337CB234 +>80 D<0107B512FE49ECFFC017F0903A003F8007F8EE01FCEE007E92C7127F835C188014 +7EA214FEEF7F005CA2010115FE5F4A13015F01034A5AEE0FC04A495A04FEC7FC49B512F0 +16C09138E003E0ED01F8010F6D7E167C4A137EA2131FA25CA2013F14FEA291C7FCA24913 +015E137EEF01C001FE150318805B00011607277FFFF0001400B5ECFE0EEE7E1CC9EA1FF8 +EE07E032357BB238>82 D<913901FC018091380FFF03023F13C791387E07EF903A01F801 +FF0049487E4A7F495A4948133E131F91C7FC5B013E143CA3137E1638A293C7FC137FA26D +7E14E014FE90381FFFC06D13F86D7F01017F6D6C7E020F7F1400153F6F7E150FA4120EA2 +001E5D121CA2151F003C92C7FCA2003E143E5D127E007F5C6D485A9038C007E039F3F80F +C000F0B5C8FC38E03FFC38C00FF029377AB42B>I<0003B812C05A1880903AF800FC003F +260FC001141F0180150F01005B001EEE07001403121C003C4A5BA200380107140E127800 +705CA2020F141E00F0161CC74990C7FCA2141FA25DA2143FA292C9FCA25CA2147EA214FE +A25CA21301A25CA21303A25CA21307A25C497E001FB512F05AA2323374B237>I97 D<137EEA0FFE121F5B1200A35BA21201A25BA21203A25BA21207A2EBC3E0EBCFF838 +0FDC3EEBF81F497E01E01380EA1FC0138015C013005AA2123EA2007E131F1580127CA214 +3F00FC14005AA2147EA25CA2387801F85C495A6C485A495A6C48C7FCEA0FFCEA03F01A35 +78B323>I<14FCEB07FF90381F078090383E03C0EBFC013801F8033803F0073807E00F13 +C0120F391F80070091C7FC48C8FCA35A127EA312FE5AA4007C14C0EC01E0A2EC03C06CEB +0F80EC1F006C137C380F81F03803FFC0C648C7FC1B2278A023>III<151FED7FC0EDF0E0020113F0EC03E3A2EC07C316 +E0EDC1C091380FC0005DA4141F92C7FCA45C143E90381FFFFEA3D9007EC7FC147CA414FC +5CA513015CA413035CA413075CA3130FA25CA3131F91C8FCA35B133E1238EA7E3CA2EAFE +7812FC485AEA78E0EA3FC0000FC9FC244582B418>I<143FECFF80903803E1E6903807C0 +FF90380F807FEB1F00133E017E133F49133EA24848137EA24848137CA215FC12074913F8 +A21401A2D80FC013F0A21403120715E01407140F141F3903E03FC00001137FEBF0FF3800 +7FCF90381F0F801300141FA21500A25C143E1238007E137E5C00FE5B48485A387803E038 +7C0F80D81FFFC7FCEA07F820317CA023>III< +EB0FC0EA01FF5A5CEA001FA391C7FCA25BA2133EA2137EA2137CA213FCA2491378EC01FE +0001EB078FEC0E0F9038F01C3F143800031370ECE03E9038E1C01C9038E38000D807E7C7 +FC13EE5B13F8120F13FFEB9FC0EB83F0EA1F81EB80F81300150C48141E151C123EA2007E +143C1538127C157800FCEB787015E048EB3FC00070EB0F8020357BB323>107 +D<133FEA07FF5A13FEEA007EA3137CA213FCA213F8A21201A213F0A21203A213E0A21207 +A213C0A2120FA21380A2121FA21300A25AA2123EA2127EA2127C1318EAFC1C133CEAF838 +A21378137012F013F0EAF8E01279EA3FC0EA0F00103579B314>I<2703C003F8137F3C0F +F00FFE01FFC03C1E783C1F07C1E03C1C7CF00F8F01F03B3C3DE0079E0026383FC001FC7F +D97F805B007001005B5E137ED8F0FC90380FC00100E05FD860F8148012000001021F1303 +60491400A200034A13076049013E130FF081800007027EEC83C0051F138049017C1403A2 +000F02FC1407053E130049495CEF1E0E001F01015D183C010049EB0FF0000E6D48EB03E0 +3A227AA03F>I<3903C007F0390FF01FFC391E787C1E391C7CF01F393C3DE00F26383FC0 +1380EB7F8000781300EA707EA2D8F0FC131F00E01500EA60F8120000015C153E5BA20003 +147E157C4913FCEDF8180007153C0201133801C013F0A2000F1578EDE070018014F016E0 +001FECE1C015E390C7EAFF00000E143E26227AA02B>I<14FCEB07FF90381F07C090383E +03E09038FC01F0EA01F83903F000F8485A5B120F484813FCA248C7FCA214014814F8127E +A2140300FE14F05AA2EC07E0A2007CEB0FC01580141FEC3F006C137E5C381F01F0380F83 +E03803FF80D800FCC7FC1E2278A027>I<011E137C90387F81FF9039F3C387C09039E3EF +03E03901E1FE01D9C1FC13F0EBC3F8000313F0018314F814E0EA07871307000313C01200 +010F130316F01480A2011F130716E01400A249EB0FC0A2013EEB1F80A2017EEB3F00017F +133E5D5D9038FF81F09038FDC3E09038F8FF80027EC7FC000190C8FCA25BA21203A25BA2 +1207A25BB5FCA325307FA027>I<3903C00FC0390FF03FF0391E78F078391C7DE03C393C +3FC0FC00381380EB7F00007814F8D8707E13701500EAF0FC12E0EA60F812001201A25BA2 +1203A25BA21207A25BA2120FA25BA2121FA290C8FC120E1E227AA020>114 +DI<1303EB0F80A3131FA214 +00A25BA2133EA2137EA2137C387FFFF8A2B5FC3800F800A21201A25BA21203A25BA21207 +A25BA2120FA25B1460001F13F014E01300130114C01303001E1380EB07005BEA0F1EEA07 +F8EA01E015307AAE19>II119 D<13F0D803FC1307D80F1E130F000E141F121C123C +0038143FD8783E133E1270A2017E137ED8F07C137CEA60FCC65A15FC000114F85BA21401 +000314F013E0A2140315E0EA07C0A20003130715C0EBE00F141F0001133F9038F07F8038 +007FEFEB1F8FEB001F1500A25C003E133E007E137E147C5C007C5BEA7001495A38380780 +D83C1FC7FCEA0FFCEA07F020317AA025>121 D E /Fb 5 96 df<1638A2163C161C161E +828283707EB87E17F883CA121E717EEF07E0EF01FC9438007F80183FF0FC00EF03F0EF07 +C0051FC7FC173EB812F85F5FC9EA03C04C5A94C8FC5E161E161C163C1638A239237C9F42 +>41 D<49B5FC130F133F01FFC7FCEA01F8EA03E0EA078048C8FC121E121C123C12381278 +1270A212F05AA2B7FCA300E0C8FCA27E1270A212781238123C121C121E7E6C7EEA03E0EA +01F86CB4FC013FB5FC130F130120277AA12D>50 D57 D<146014F0A2497EA2497E149CEB079E140EEB0F0F +EB0E07011E7FEB1C03013C7FEB380101787FEB700001F07F491370000114784913380003 +143C49131C0007141E90C7120E48140F000E80001E1580001C1403003C15C00038140100 +7815E00070140000F015F0481570163024247CA22D>94 D<00E0153016706C15F0007015 +E000781401003815C0003C1403001C1580001E1407000E1500000F5C6C140E6D131E0003 +141C6D133C000114386D1378000014706D13F001705BEB780101385BEB3C03011C5BEB1E +07010E90C7FCEB0F0FEB070E149EEB039C14FC6D5AA26D5AA2146024247CA22D>I +E /Fc 21 120 df35 +D<130C133E137E13FCEA01F8EA03F0EA07E0EA0FC01380121F13005A123E127E127CA212 +FCA25AA97EA2127CA2127E123E123F7E1380120F13C0EA07E0EA03F0EA01F8EA00FC137E +133E130C0F2D76A71F>40 D<126012F87E127E7EEA1F80EA0FC0EA07E0120313F0120113 +F8120013FC137CA2137EA2133EA9137EA2137CA213FC13F8120113F0120313E01207EA0F +C0EA1F80EA3F00127E5A5A12600F2D7BA71F>I<1378A2137C1378A20070133800F8137C +38FE79FCEAFF7B387FFFF8001F13E0000713803801FE003807FF80001F13E0007F13F838 +FF7BFCEAFE7938F8787C0070133800001300A2137C1378A216197C9D1F>I<121EEA3F80 +127F13C0A3123F121F1207A2EA0F80121FEA7F0012FE12F812700A1076871F>44 +D<123C127E12FFA4127E123C080875871F>46 D<007FB51280B612C0A36C1480C9FCA500 +7FB51280B612C0A36C14801A0F7E981F>61 D64 D76 D82 D<13C0EA03F0EA0FFCEA3FFF481380 +38FF3FC0EAFE1FEAF8073870038012097AA31F>94 D97 D102 D<387F87F038FFDFFCEBFFFE6CEBFF803907FC1FC0EBF00F9038E0 +07E0A29038C003F0A21401A5140313E0EC07E013F09038F80FC09038FC3F8090B512005C +EBDFFCEBC7E001C0C7FCA9EA7FFC487EA26C5A1C2680981F>112 +D +I<387FE03F39FFF0FFC001F313E0EA7FF73801FFE714879038FE03C091C7FC5B5BA35BA9 +387FFFF0B5FCA27E1B197F981F>I<3803FFE0001F13F05A5AEAFE03EAF80112F038F800 +E06C1300EAFFC06CB4FC001F13C06C13E0C613F8EB07FCEA700000F8137C6C133CA26C13 +7C38FF01FCEBFFF814F014C00071130016197C981F>I<13E0487EA6387FFFFCB57EA26C +5BD801F0C7FCAB1407EC0F80A2141F13F89038FC3F006CB5FC6D5AEB3FF8EB0FE019207F +9F1F>I<387F80FFD8FFC11380A2EA7FC00007130FAE141F143FEBE07F90B512F86C14FC +C6FC90387FC7F81E1980981F>I<397FF0FFE0D8FFF913F0A2D87FF013E03907801E00A2 +EBC03E0003133CA36C6C5AA36C6C5AA3EB79E0A3137F6D5AA36D5A6DC7FC1C197F981F> +I<397FE07FE039FFF0FFF0A2397FE07FE0391E000780A4001F130F6C1400130FEB1F8FEB +3FCFA3000713CE1339A2EBB9DEA2EBF0FE00035BA33801E0781C197F981F>I +E /Fd 15 118 df<90383E07C0137F13FF5AEA03E301C1C7FCEA07C0A9B5EA07C0A4EA07 +C0B3A41A297FA821>12 D70 +D78 D84 +D97 D99 D<137E3801FF80000713C04813E0381FC3F01300003E13785A14380078133C +12F8B512FCA400F0C7FC7EA31278127C123C003E13046C131CEBC0FCEA0FFF000313F86C +13E038007F00161D7E9B1B>101 D<12F8B3B3A405287CA70E>108 +D<133F38F8FFC000F913E000FB13F0EAFF8338FE01F813005AA25AB2151B7B9A20>110 +D<133F3801FFE0487F487F380FC0FC381F807E48487E003E7F48EB0F80A20078130700F8 +14C0A8007CEB0F80A2007E131F6CEB3F00381F807EEBC0FE6CB45A000313F06C5BD8003F +C7FC1A1D7E9B1F>I<133F38F8FFC000FB13E0B512F0EB03F838FE01FCEAFC0048137E14 +3EA2141FA7143F143EA2147E6C13FC38FE01F8EAFF07EBFFF000FB13E000F9138038F87E +0090C7FCAA18267B9A20>I<133CEAF0FC12F112F312F713E0EAFF8013005A5AA25AB00E +1B7B9A15>114 DII<00F813F8B3A213011303EAFC0FEA7FFF +13FEEA3FF8381FC000151B7B9920>I E /Fe 12 32 df16 D<1C0C1C1EA91C3EA21C3CA51C7CA21C78A21CF8A21CF0A2 +1B01A21CE01B03A21CC01B07A2F30F80A21C0063A21B3EA263A2631A0163505AA2505A1A +0F505A98C7FC1A3E1A7E62624F5A19034F5A4F5A4F5A4FC8FC197E614E5A4E5AF00FE04E +5A4EC9FC18FE4D5AEF07F04D5AEF3FC005FFCAFCEE03FCEE0FF8EE3FE0923801FF80DB0F +FECBFCED7FF8913803FFE0027F90CCFC90381FFFF8007FB512C0B548CDFC14C0D87FF0CE +FC5757D3D6A6>I<126012F0A97EA21278A4127CA2123CA3123EA2121E121FA27E7FA212 +077FA26C7EA212017FA26C7EA2137C137E133E7FA26D7E8013076D7E8013016D7E80147E +143E80816E7E6E7E6E7E6E7E6E7E157E816F7E6F7EED07F06F7EED00FC167F707EEE0FE0 +707EEE01FC70B4FCEF3FC0EF1FF0EF07FC943801FF809438007FE0F01FFC953807FFC006 +0013FC96383FFFF80707EBFFFCDF007F13FE1A079738000FFC575780D6A6>III<1E041E1EAB1E3EA21E3CA51E7CA21E78A31EF8A21EF0A21D01A21EE0 +A21D03A21EC01D07A21E801D0FA2F51F00A21D3EA21D3C1D7CA265A2525AA2525A1C0765 +525AA252C7FC641C3E641CFC64515A1B03515A515A6451C8FC631B7E63505A505A505A50 +5A505A50C9FC1A7E4F5A4F5AF107E04F5AF13F804FCAFCF001FC4E5AF00FE0F03FC006FF +CBFCEF03FEEF0FF8EF3FE0EFFF80DC07FECCFCEE3FF8923801FFE0030F1380DBFFFCCDFC +021F13E0011FB5CEFCB612F8158002F0CFFC01F0D0FC6768E3E7C7>I<122012F0AA7EA2 +1278A6127CA2123CA3123EA2121EA2121FA27E7FA212077FA212037FA26C7EA212007FA2 +137CA27FA27FA26D7E8013076D7EA26D7E801300147C147E80806E7E816E7E6E7E14016E +7E81157E816F7E6F7E6F7E6F7E6F7E6F7E167F707EEE0FC0707EEE03F8707EEE007E717E +EF1FE0EF07F0EF03FCEF00FFF03FC0F01FF0F007FCF001FF9538007FE0F11FFC963807FF +80070113F09638003FFF080713F80800EBFFF0091FEBFFFE090114FFF3000F9938001FFE +686880E7C7>II[137 137 +261 131 266 28 D[<2203FA0780AC220FA22300A66AA2221EA4223EA2223CA3227CA222 +78A222F8A26A2101A26A2103A26A2107A26A210FA29FC7FC69A2213EA269A2217821F8A2 +565AA2565AA2565AA2565A201F9EC8FC203EA26820FC68555A1F0368555A1F0F6855C9FC +671F7E1F7C671E01545A545A67545A1E1F54CAFC1E7E66535A535A535A535A535A53CBFC +1D7E65F403F8525AF40FC0525A0A7FCCFC1CFEF301F8F307F0515AF33F8051CDFCF201FC +505AF20FE0F23FC008FFCEFCF103FEF10FF8F13FE0F1FF80DE03FECFFCF01FF8F07FE094 +3803FF80DD1FFED0FCEFFFF0040F13C0DCFFFED1FC031F13F00203B512800107B500F8D2 +FC007FB61280B600F0D3FC4AD4FCD87FFCD5FC>137 137 261 264 +266 I[<126012F0AB7EA21278A7127CA2123CA3123EA2121EA3121FA27EA27FA212077F +A21203A27FA212017FA26C7EA21378137CA27FA2131E131FA26D7EA26D7EA26D7EA26D7E +A26D7E80147C80A28081140F6E7E8114036E7E811400157C157E81816F7E826F7E6F7E6F +7E1500167C167E82707E707E707E707E707E707E177E83717EEF0FE0717EEF01F8717E18 +7E727E727EF007E0F003F8727EF0007F737EF10FE0737EF101FC73B4FCF23FC0F21FF0F2 +07FCF201FF9738007FC0F31FF0F307FE983801FF809838007FF0F41FFE993803FFC00A00 +13FC9A381FFFC00B0313FC9A39007FFFF00C07EBFFF0E4007F90B5FC0D071580F7001FE6 +001F1300>137 137 128 264 266 I[137 +137 128 131 266 I E /Ff 1 84 df<0078EF078000FCEF0FC0B3B3B3A46C171F007E18 +80A2007F173F6C1800A26D5E001F177E6D16FE6C6C4B5A6D15036C6C4B5A6C6C4B5A6C6C +4B5A6C6C6CEC7FC06D6C4A5AD93FF8010790C7FC6DB4EB3FFE6D90B55A010315F06D5D6D +6C1480020F01FCC8FC020113E03A537B7F45>83 D E /Fg 6 66 +df<13FF000313C0380781E0380F00F0001E137848133CA248131EA400F8131FAD007813 +1EA2007C133E003C133CA26C13786C13F0380781E03803FFC0C6130018227DA01E>48 +D<13E01201120712FF12F91201B3A7487EB512C0A212217AA01E>II<13FF000313C0380F03E0381C00F014F8003E13FC147CA2001E13 +FC120CC712F8A2EB01F0EB03E0EB0FC03801FF00A2380003E0EB00F01478147C143E143F +1230127812FCA2143E48137E0060137C003813F8381E03F0380FFFC00001130018227DA0 +1E>I<14E01301A213031307A2130D131D13391331136113E113C1EA01811203EA070112 +06120C121C12181230127012E0B6FCA2380001E0A6EB03F0EB3FFFA218227DA11E>I<14 +38A2147CA314FEA2497E149FA29038030F80A201067F1407010E7FEB0C03A2496C7EA201 +387FEB3000A249137C90387FFFFC90B57E9038C0003EA248487FA20003158090C7120F5A +16C0D81F8014E0D8FFE0EB7FFEA227247DA32D>65 D E /Fh 16 +96 df<007FB712FCB812FEA26C16FC2F047A943C>0 D<0060153000F815F86C1401007E +EC03F06CEC07E06C6CEB0FC06C6CEB1F806C6CEB3F006C6C137E6C6C5B6C6C485A90387E +03F06D485A90381F8FC090380FDF806DB4C7FC6D5A6D5AA2497E497E90380FDF8090381F +8FC090383F07E090387E03F0496C7E48486C7E4848137E48487F4848EB1F804848EB0FC0 +48C7EA07E0007EEC03F048EC01F848140000601530252475A43C>2 +D12 D14 +D<007FB812C0B912E0A26C17C0CCFCAC007FB812C0B912E0A26C17C0CCFCAC007FB812C0 +B912E0A26C17C033247CA43C>17 D<171C177EEE01FEEE07FCEE1FF0EE7FC0923801FF00 +ED07FCED1FF0ED7FC04A48C7FCEC07FCEC1FF0EC7FC04948C8FCEB07FCEB1FF0EB7FC048 +48C9FCEA07FCEA1FF0EA7FC048CAFCA2EA7FC0EA1FF0EA07FCEA01FF38007FC0EB1FF0EB +07FCEB01FF9038007FC0EC1FF0EC07FCEC01FF9138007FC0ED1FF0ED07FCED01FF923800 +7FC0EE1FF0EE07FCEE01FEEE007E171C1700AC007FB712FCB812FEA26C16FC2F3E7AB03C +>20 D<187018F0A2841878A2187C183C183E84A2727E727E85727E727E727E197F007FBA +12C0BB12F0A26C19C0CCEA7F0019FC4E5A4E5A4E5A614E5A4EC7FCA2183E183C187C1878 +A218F860A2187044287CA64D>33 D<17F0A283177C173C173E83A2717E717E717E007FB8 +7EB97E846C17FFCBEA1F80F00FE0F003F0F001FE9538007F80F11FF0A2F17F80953801FE +00F003F0F00FE0F01F80007FB9C7FCB912FC606C5FCAEA03E04D5A4D5A4DC8FCA2173E17 +3C177C5F5FA2442A7CA74D>41 D<91383FFFF849B512FC1307011F14F8D93FE0C7FC01FF +C8FCEA01FCEA03F0485A485A5B48C9FC5A123E5AA21278A212F8A25AB712F816FCA216F8 +00F0C9FC7EA21278A2127CA27E123F7E6C7E7F6C7E6C7EEA01FC6CB4FCEB3FE06DB512F8 +010714FC1301D9003F13F8262E7AA933>50 D<1630167816F8A2ED01F0A2ED03E0A2ED07 +C0A2ED0F80A2ED1F00A2153EA25DA25DA24A5AA24A5AA24A5AA24A5AA24AC7FCA2143EA2 +5CA25CA2495AA2495AA2495AA2495AA249C8FCA2133EA25BA25BA2485AA2485AA2485AA2 +485AA248C9FCA2123EA25AA25AA25A1260254675B500>54 D<0060ED018000F0ED03C06C +1507A200781680007C150FA2003C1600003E5DA26C153EA26C153C6D147CA26C6C5CA200 +035D90B6FCA26C5DA29038F000036C6C495AA201785C017C130FA2013C91C7FC013E5BA2 +6D133EA26D133CEC807CA201071378ECC0F8A2903803E1F0A201015B14F3A26DB45AA26E +5AA36EC8FCA3141E140C2A3680B32B>56 D<007FB61280B712C0A27EC81203B3A2003FB6 +FC5AA27EC81203B3A2007FB6FCB7FCA26C158022347CB32B>I<007FB71280B812C0A27E +C91203B0EE01802A157C9A33>I<0060ED018000F0ED03C0B3AF6C1507A2007CED0F80A2 +6CED1F00003F5D6C6C147ED80FE0495AD807F8EB07F83A01FF807FE06C90B55A013F91C7 +FC010F13FC010013C02A307CAD33>91 D<140C141E143FA24A7EA34A7EA2903801F3E0A2 +903803E1F0A214C001077FA290380F807CA249487EA2011E131E013E131FA2496D7EA249 +6D7EA2491303000181A248486D7EA248486D7EA2491478000F157CA248C87EA2003E81A2 +003C81007C1680A248ED07C0A24815030060ED01802A307CAD33>94 +D<0060ED018000F0ED03C06C1507A2007CED0F80A2003C1600003E5DA26C153EA26C6C5C +A2000715786D14F8A26C6C495AA26C6C495AA200005D6D1307A2017C495AA26D49C7FCA2 +011E131E011F133EA26D6C5AA26D6C5AA201035B14E1A2903801F3E0A26DB45AA26E5AA3 +6EC8FCA2141E140C2A307CAD33>I E /Fi 6 114 df<147F903803FFE090380FC0F89038 +3F007C017C017E1360497F484815E0484890381F80C0120748481481EEC1804848130F00 +3F15C390C7140016C74815C6007E15CE16DC16D816F8485D5E5E127CA3151F6C143F0377 +13C06C903801E7E03A0F800783E13B07C07E03E3803B01FFF801FF003A007F80007C2B22 +7EA031>11 D<137CEB7F80EB1FE0130F6D7EA26D7EA36D7EA36D7EA28080A26E7EA36E7E +A281140FA26E7EA381140F141FEC3DFC1479ECF8FEEB01F0EB03E0903807C07FEB0F80EB +1F00013EEB3F80137E4914C04848131F485A4848EB0FE0EA1FC0123F4848EB07F048C7FC +4815F848140348EC01FC48140026357CB32D>21 D<91B6FC01031580130F013F1500495C +2701FF03FCC7FC3803F80048487F49137E485A121F49133E48C7127EA25A127EA215FE00 +FE5C5AA24A5AA24A5A007C5C14074A5A6C495A4AC8FC6C137C380F81F83803FFE0C66CC9 +FC29217E9F2C>27 D<14FF010713E0011F13F8017F13FC3801FE00D803E0133CD8078013 +1890C8FC120E120CA4380E03C038073FF83803FC3CEBFFF8486C5A000EC8FC5A5A5A1260 +A212E05AA26C14E015C0007013010078EB0380003FEB1F00381FFFFE6C5B000313F0C613 +801E247EA124>34 D<010FB712FCA218F8903A003FC00007170018785D1838147F183092 +C8FCA25CA25C16060101020E1370040C13604A1500A20103141C5E5C16F849B5FCA25EEC +F001010F130016605CA2011F14E05E5CA2013F91C8FCA25CA2137FA291CAFCA25BA25B48 +7EB6FCA336337DB231>70 D<903801F803903807FE0790381F071F90387C03BF9038F801 +BED801F013FE00031300485A4913FC120F485A1401D83F0013F8A3481303007E14F0A300 +FE13074814E0A3140F15C0127C141F143F003CEB7F80003E13FF381E01DF380F07BF3907 +FE3F00EA00F813005C147EA314FE5CA21301A25C90387FFFE090B5FCA220307EA022> +113 D E /Fj 29 122 df<903907E03F80EB1FF8133F137FA2EBFC183801F80891C8FC5B +1203ABB538F81F80A53803F000B3AA21357FB429>12 D50 D65 D67 D69 +DI78 D83 DI<00FE15FCB3B3A3007FEC01F8A36C6CEB03F0A26C6CEB07E06D13 +0F6C6CEB1FC06C6CEB7F803A03FF01FF006CEBFFFE6C5C013F13F0010F13C0D901FEC7FC +263679B335>I97 +D99 D<15FCB2EB3F80EBFFF0000313FC4813FE4813FFEBF81F +381FE007383FC001138048C7FC127EA35AA9127EA3007F1301EA3F801403381FE007380F +F81F90B5FC6C13FC6C13F8C613E090383F80001E357DB328>III<90391FC00F8090387FF0FF90B612 +C05A5A2607F07FC7FC390FC01F80EB800FA248486C7EA76C6C485AA2EBC01F2607F07FC7 +FCEBFFFE485B5C486C5AEB1FC090C9FCA37F380FFFFEECFFE06C804814FC48805A397F80 +03FF007EC77E00FEEC3F8048141FA46C143F007FEC7F006D5B393FF007FE6CB55A6C5C00 +0314E0C61480D91FFCC7FC22337EA126>I<12FCB2EB07F0EB3FFE497E90B51280B6FC90 +38E07FC0EB801F9038000FE0A2481307A35AB3A41B347AB328>I<12FEA71200AC127EB3 +AF07347BB313>I<12FCB3B3B006347AB313>108 DIIII< +EB03C0EAF81F133F13FF12F912FBEBFC00EAFFF013C05B90C7FCA25AA35AB312227AA11A +>114 DII<00FCEB07E0B3A7140F +141F6C133F6C13FF6CB5FC14F76C13E76C1307D807F8C7FC1B227AA028>I<007E143F6C +5C6C6C13FE6D5B6C6C485A0007495A6C6C485A3801F80FD800FC5B90387E1F80D97F3FC7 +FCEB3F7E6D5A6D5A13076D5AA2497E497E131FEB3F3EEB3E1F017C7F9038FC0FC048486C +7E48486C7EEA07E06E7E48486C7E4848137E48C7127F48EC3F8000FEEC1FC0222180A023 +>120 D<00FE143F007E147EA27E15FC7F001FEB01F813C0120FEC03F0EA07E015E0EBF0 +07120315C03801F80F15801200EBFC1F1500137CEB7E3E133EA2EB1F3C147CEB0F78A36D +5AA26D5AA35C13075CA2130F91C7FC5B131EEA203EEA387CEA3FFC5BA25BEA0FC020317F +A023>I E /Fk 6 83 df<1C0C1C1E1C3E1C7E1CFCF301F8F303F0F307E0F30FC0F31F80 +F33F001B7E63505A505A505A505A505A50C7FC1A7E624F5A4F5A4F5A4F5A4F5A4FC8FC19 +7E614E5A4E5A4E5A4E5A4E5A4EC9FC187E604D5A4D5A4D5A4D5A4D5A4DCAFC177E5F4C5A +4C5A4C5A4C5A4C5A4CCBFC167E5E4B5A4B5A4B5A4B5A4B5A4BCCFC157E5D4A5A4A5A4A5A +4A5A4A5A4ACDFC147E5C495A495A495A495A495A49CEFC137E5B485A485A485A485A485A +48CFFC127E5A5A1260575782D453>0 D<15011502150C153C15F81403EC0FF0143FECFF +E01303011F13C0137F0003B51280121FB612007E6C5B7E6C5B7E7E6C5B7E6D5A133F131F +6D5A130713036D5A1300144020204DD253>18 D<12C012F012FCB4FC13C013F813FEEBFF +C014F814FF15E015FEA215E0150014F814C049C7FC13F813C090C8FC12FC12F012C01F18 +4E8B53>45 D63 D<126012F87E127E7E6C7E6C7E6C7E +6C7E6C7E6C7E137E7F6D7E6D7E6D7E6D7E6D7E6D7E147E806E7E6E7E6E7E6E7E6E7E6E7E +157E816F7E6F7E6F7E6F7E6F7E6F7E167E82707E707E707E707E707E707E177E83717E71 +7E717E717E717E717E187E84727E727E727E727E727E727E197E85737E737E737E737E73 +7E737E1A7E86747E747E747E747E747E747E1B7E87F31F80F30FC0F307E0F303F0F301F8 +F300FC1C7E1C3E1C1E1C0C575782D453>I<144014C01301497E1307130F497E133F137F +497E5A487F5A5A487F5A487FB6FC001F14801203C66C13C0131F010313E01300EC3FF014 +0FEC03F81400153C150C1502150120204D9F53>82 D E /Fl 47 +127 df<010F133C90381F807EA8013F13FE4A5AA4007FB612F0B712F8A4003F15F03A00 +7E01F800A5EBFE0301FC5BA6003FB612F0B712F8A46C15F03A01F807E000A30003130F01 +F05BA86C486C5A25337DB22C>35 D<143814FC13011303EB07F8EB0FF0EB1FC0EB3F80EB +7F0013FE485A485A5B12075B120F5B485AA2123F90C7FCA25A127EA312FE5AAC7E127EA3 +127F7EA27F121FA26C7E7F12077F12037F6C7E6C7E137FEB3F80EB1FC0EB0FF0EB07F8EB +03FC130113001438164272B92C>40 D<127012FC7E7E6C7E6C7EEA0FE06C7E6C7E6C7E6C +7E137F7F1480131F14C0130FEB07E0A214F01303A214F81301A314FC1300AC130114F8A3 +130314F0A2130714E0A2EB0FC0131F1480133F14005B13FE485A485A485A485AEA3FC048 +5A48C7FC5A5A1270164279B92C>II44 +D<121FEA3F80EA7FC0EAFFE0A5EA7FC0EA3F80EA1F000B0B708A2C>46 +D<1507ED0F80151FA2153F16005D157E15FE5D14015D14035DA214075D140F5D141F5D14 +3F92C7FC5C147E14FE5CA213015C13035C13075C130F5C131F5CA2133F91C8FC5B137E13 +FE5B12015B12035B12075BA2120F5B121F5B123F90C9FC5A127E12FE5AA25A127821417B +B92C>I<121FEA3F80EA7FC0EAFFE0A5EA7FC0EA3F80EA1F00C7FCAE121FEA3F80EA7FC0 +EAFFE0A5EA7FC0EA3F80EA1F000B2470A32C>58 D<007FB612F0B712F8A4003F15F0CAFC +A8003FB612F0B712F8A46C15F025147DA22C>61 D64 +D<14FE497EA4497FA214EFA2130781A214C7A2010F7FA314C390381F83F0A590383F01F8 +A490387E00FCA549137E90B512FEA34880A29038F8003FA34848EB1F80A4000715C04913 +0FD87FFEEBFFFC6D5AB514FE6C15FC497E27347EB32C>I<007FB5FCB612C015F0816C80 +3907E003FEEC00FFED7F80153FED1FC0ED0FE0A2150716F0150316F81501A4ED00FCACED +01F8A3150316F0A2150716E0150FED1FC0153FED7F80EDFF00EC03FE007FB55AB65A5D15 +C06C91C7FC26337EB22C>68 D<007FB612F8B712FCA37ED803F0C7FCA716781600A515F0 +4A7EA490B5FCA5EBF001A46E5A92C7FCAD387FFFE0B5FC805C7E26337EB22C>70 +D72 D<387FFFE0B57EA36C5BD803F0C8FC +B3AE16F0ED01F8A8007FB6FCB7FCA36C15F025337DB22C>76 D78 +DI<007FB512C0B612F88115FF6C15802603F00013C0153FED0F +E0ED07F0A2150316F81501A6150316F01507A2ED0FE0ED3FC015FF90B61280160015FC5D +15C001F0C8FCB0387FFF80B57EA36C5B25337EB22C>I<90381FF80790B5EA0F804814CF +000714FF5A381FF01F383FC003497E48C7FC007E147F00FE143F5A151FA46CEC0F00007E +91C7FC127F7FEA3FE0EA1FFCEBFFC06C13FC0003EBFFC06C14F06C6C7F01077F9038007F +FEEC07FF02001380153FED1FC0A2ED0FE0A20078140712FCA56CEC0FC0A26CEC1F806D13 +3F01E0EB7F009038FE01FF90B55A5D00F914F0D8F83F13C0D8700790C7FC23357CB32C> +83 D<3A3FFF03FFE0484913F0148714076C6D13E03A01F800FE007F0000495A13FE017E +5BEB7F03013F5B1487011F5B14CF010F5B14FF6D5BA26D90C7FCA26D5AA26D5AA2497EA2 +497EA2497F81EB0FCF81EB1FC7EC87F0EB3F83EC03F8EB7F01017E7FEBFE00497F000114 +7E49137F000380491480151FD87FFEEBFFFC6D5AB514FE6C15FC497E27337EB22C>88 +D<387FFFFCB512FEA314FC00FCC7FCB3B3B3B512FC14FEA36C13FC17416FB92C>91 +D<387FFFFCB512FEA37EC7127EB3B3B3387FFFFEB5FCA36C13FC17417DB92C>93 +D<130EEB3F80EBFFE0000313F8000F13FE487FD87FF113C0D8FFE013E0EB803F38FE000F +007CEB07C00030EB01801B0C78B22C>I<137013F812011203EA07F0EA0FE0EA1FC01380 +EA3F00123E127E127CA212FC5AA4EAFF8013C013E0A2127FA2123FEA1FC0EA0F800D1B71 +B82C>96 D<3801FFF0000713FE001F6D7E15E048809038C01FF81407EC01FC381F800000 +06C77EC8127EA3ECFFFE131F90B5FC1203120F48EB807E383FF800EA7FC090C7FC12FE5A +A47E007F14FEEB8003383FE01F6CB612FC6C15FE6C14BF0001EBFE1F3A003FF007FC2724 +7CA32C>II<903803FFE0011F13F8017F13FE48B5FC48804848C6FCEA0FF0485A49 +137E4848131890C9FC5A127EA25AA8127EA2127F6C140F6DEB1F806C7E6D133F6C6CEB7F +003907FE03FF6CB55A6C5C6C6C5B011F13E0010390C7FC21247AA32C>IIII104 +D<1307EB1FC0A2497EA36D5AA20107C7FC90C8FCA7387FFFC080B5FC7EA2EA0007B3A800 +7FB512FCB612FEA36C14FC1F3479B32C>I<387FFFE0B57EA37EEA0003B3B3A5007FB612 +80B712C0A36C158022337BB22C>108 D<3A7F83F007E09039CFFC1FF83AFFDFFE3FFCD8 +7FFF13FF91B57E3A07FE1FFC3E01FCEBF83F496C487E01F013E001E013C0A301C01380B3 +3B7FFC3FF87FF0027F13FFD8FFFE6D13F8D87FFC4913F0023F137F2D2481A32C>I<397F +F01FE039FFF87FFC9038F9FFFE01FB7F6CB6FC00019038F03F80ECC01F02807FEC000F5B +5BA25BB3267FFFE0B5FCB500F11480A36C01E0140029247FA32C>II<397FF01FE0 +39FFF8FFF801FB13FE90B6FC6C158000019038F07FC09138801FE091380007F049EB03F8 +5BED01FC491300A216FE167EA816FE6D14FCA2ED01F86D13036DEB07F0150F9138801FE0 +9138E07FC091B51280160001FB5B01F813F8EC3FC091C8FCAD387FFFE0B57EA36C5B2736 +7FA32C>I<903903FC078090391FFF0FC0017F13CF48B512EF4814FF3807FE07380FF001 +48487E49137F4848133F90C7FC48141F127E150F5AA87E007E141FA26C143F7F6C6C137F +6D13FF380FF0033807FC0F6CB6FC6C14EF6C6C138F6D130FEB07F890C7FCAD0203B5FC4A +1480A36E140029367DA32C>II<90387FF8700003B512F8120F5A5A387FC00F387E00034813015AA36CEB +00F0007F140013F0383FFFC06C13FE6CEBFF80000314E0C66C13F8010113FCEB0007EC00 +FE0078147F00FC143F151F7EA26C143F6D133E6D13FE9038F007FC90B5FC15F815E000F8 +148039701FFC0020247AA32C>I<131E133FA9007FB6FCB71280A36C1500D8003FC8FCB1 +ED03C0ED07E0A5EC800F011FEB1FC0ECE07F6DB51280160001035B6D13F89038003FE023 +2E7EAD2C>I<3A7FF003FF80486C487FA3007F7F0001EB000FB3A3151FA2153F6D137F39 +00FE03FF90B7FC6D15807F6D13CF902603FE07130029247FA32C>I119 D<3A3FFF03FFF048018713F8A36C010313F03A00FC00 +7E005D90387E01F8013F5BEB1F83EC87E090380FCFC0903807EF80EB03FF6D90C7FC5C6D +5A147C14FE130180903803EF80903807CFC0EB0FC7EC83E090381F01F0013F7FEB7E0001 +7C137C49137E0001803A7FFF01FFFC1483B514FE6C15FC140127247EA32C>I<3A7FFF01 +FFFCB5008113FE148314816C010113FC3A03E0000F806C7E151F6D140012005D6D133E13 +7C017E137E013E137CA2013F13FC6D5BA2EB0F815DA2EB07C1ECC3E0A2EB03E3ECE7C013 +0114F75DEB00FFA292C7FC80A2143EA2147E147CA214FC5CA2EA0C01003F5BEA7F83EB87 +E0EA7E0F495A387FFF806C90C8FC6C5A6C5AEA07E027367EA32C>I<003FB612E04815F0 +A4007EC7EA1FE0ED3FC0ED7F80EDFF004A5A003C495AC7485A4A5A4A5A4A5A4A5A4AC7FC +EB01FC495AEB0FF0495A495A495A49C8FC4848EB01E04848EB03F0485A485A485A485A48 +5AB7FCA46C15E024247DA32C>I<01F81370D803FE13F8380FFF0148138748EBCFF0397F +9FFFE0D8FF0F13C0D8FC07138039F803FE00387000F81D0A79B22C>126 +D E /Fm 2 111 df<130E131F5BA2133E131C90C7FCA7EA03E0487EEA0C78EA187C1230 +A212605B12C0A2EA01F0A3485AA2485AA2EBC180EA0F81A2381F0300A213066C5A131CEA +07F06C5A11287DA617>105 D<3907801FC0390FE07FF03918F0E0F83930F1807CEBFB00 +D860FE133C5B5B00C1147C5B1201A248485BA34A5AEA07C01660EC03E0A23A0F8007C0C0 +A2EDC180913803C300D81F0013C7EC01FE000EEB00F8231B7D9929>110 +D E /Fn 5 62 df<13381378EA01F8121F12FE12E01200B3AB487EB512F8A215267BA521 +>49 D<13FF000313E0380E03F0381800F848137C48137E00787F12FC6CEB1F80A4127CC7 +FC15005C143E147E147C5C495A495A5C495A010EC7FC5B5B903870018013E0EA01803903 +00030012065A001FB5FC5A485BB5FCA219267DA521>I<13FF000313E0380F01F8381C00 +7C0030137E003C133E007E133FA4123CC7123E147E147C5C495AEB07E03801FF8091C7FC +380001E06D7E147C80143F801580A21238127C12FEA21500485B0078133E00705B6C5B38 +1F01F03807FFC0C690C7FC19277DA521>I<1438A2147814F81301A2130313071306130C +131C131813301370136013C012011380EA03005A120E120C121C5A12305A12E0B612E0A2 +C7EAF800A7497E90383FFFE0A21B277EA621>I +61 D E /Fo 33 124 df46 D<141E143E14FE1307133FB5FCA313CFEA000FB3B3A6007FB61280A42137 +79B630>49 DI< +EB03FF011F13F0017F13FC3901FC07FF2603F003138048486C13C0496C13E0EA0FF001FC +14F0121F7FA56C4814E0A23803F001C714C04A138016004A5A4A5AEC3FF090380FFFC092 +C7FC15F090380007FE913801FF806E13C016E0ED7FF016F816FC153FA216FEEA1FC0487E +487E487EA416FCA249EB7FF8127F01C0EBFFF06C4814E06C6C4813C0260FFC0713806CB6 +1200000114FC6C6C13F0010790C7FC27387CB630>II<001C +15C0D81F80130701F8137F90B61280A216005D5D15F05D15804AC7FC14F090C9FCA8EB07 +FE90383FFFE090B512F89038FC07FC9038E003FFD98001138090C713C0120EC813E0157F +16F0A216F8A21206EA3F80EA7FE012FF7FA44914F0A26C4813FF90C713E0007C15C06C5B +6C491380D9C0071300390FF01FFE6CB512F8000114E06C6C1380D90FF8C7FC25387BB630 +>I67 +DIII78 D83 D<003FB91280A4D9F800EBF0 +03D87FC09238007FC049161F007EC7150FA2007C1707A200781703A400F818E0481701A4 +C892C7FCB3AE010FB7FCA43B387DB742>I97 D<903801FFC0010F13FC017F +13FFD9FF8013802603FE0013C048485AEA0FF8121F13F0123F6E13804848EB7F00151C92 +C7FC12FFA9127FA27F123FED01E06C7E15036C6CEB07C06C6C14806C6C131FC69038C07E +006DB45A010F13F00101138023257DA42A>99 DI<903803FF80011F13F0017F13FC3901FF83FE3A03FE +007F804848133F484814C0001FEC1FE05B003FEC0FF0A2485A16F8150712FFA290B6FCA3 +01E0C8FCA4127FA36C7E1678121F6C6C14F86D14F000071403D801FFEB0FE06C9038C07F +C06DB51200010F13FC010113E025257DA42C>II<161FD907FEEBFFC090387FFFE348B6EAEFE02607 +FE07138F260FF801131F48486C138F003F15CF4990387FC7C0EEC000007F81A6003F5DA2 +6D13FF001F5D6C6C4890C7FC3907FE07FE48B512F86D13E0261E07FEC8FC90CAFCA2123E +123F7F6C7E90B512F8EDFF8016E06C15F86C816C815A001F81393FC0000F48C813804815 +7F5A163FA36C157F6C16006D5C6C6C495AD81FF0EB07FCD807FEEB3FF00001B612C06C6C +91C7FC010713F02B377DA530>I<13FFB5FCA412077EAFED7FC0913803FFF8020F13FE91 +381F03FFDA3C01138014784A7E4A14C05CA25CA291C7FCB3A3B5D8FC3F13FFA4303A7DB9 +35>II<13FFB5FCA412077EB3B3ACB512FCA4163A7DB91B>108 +D<01FED97FE0EB0FFC00FF902601FFFC90383FFF80020701FF90B512E0DA1F81903983F0 +3FF0DA3C00903887801F000749DACF007F00034914DE6D48D97FFC6D7E4A5CA24A5CA291 +C75BB3A3B5D8FC1FB50083B512F0A44C257DA451>I<01FEEB7FC000FF903803FFF8020F +13FE91381F03FFDA3C011380000713780003497E6D4814C05CA25CA291C7FCB3A3B5D8FC +3F13FFA430257DA435>I<903801FFC0010F13F8017F13FFD9FF807F3A03FE003FE04848 +6D7E48486D7E48486D7EA2003F81491303007F81A300FF1680A9007F1600A3003F5D6D13 +07001F5DA26C6C495A6C6C495A6C6C495A6C6C6CB45A6C6CB5C7FC011F13FC010113C029 +257DA430>I<9039FF01FF80B5000F13F0023F13FC9138FE07FFDAF00113800003496C13 +C00280EB7FE091C713F0EE3FF8A2EE1FFCA3EE0FFEAA17FC161FA217F8163F17F06E137F +6E14E06EEBFFC0DAF00313809139FC07FE0091383FFFF8020F13E0020390C7FC91C9FCAC +B512FCA42F357EA435>I<49B4EB0780010FEBE00F013FEBF81F9039FFC07C3F0003EB80 +3E3A07FE000F7F4848EB07FF121F497F123F497F127FA25B12FFAA6C7EA36C7E5D6C7E00 +0F5C6C6C5B6C6C133F6CEBC0FD39007FFFF1011F13C10101130190C7FCAC037F13FEA42F +357DA432>I<9038FE03F000FFEB0FFEEC3FFF91387C7F809138F8FFC000075B6C6C5A5C +A29138807F80ED3F00150C92C7FC91C8FCB3A2B512FEA422257EA427>I<90383FF03839 +03FFFEF8000F13FF381FC00F383F0003007E1301007C130012FC15787E7E6D130013FCEB +FFE06C13FCECFF806C14C06C14F06C14F81203C614FC131F9038007FFE140700F0130114 +007E157E7E157C6C14FC6C14F8EB80019038F007F090B512C000F8140038E01FF81F257D +A426>I<130FA55BA45BA25B5BA25A1207001FEBFFE0B6FCA3000390C7FCB21578A815F8 +6CEB80F014816CEBC3E090383FFFC06D1380903803FE001D357EB425>I<01FFEC3FC0B5 +EB3FFFA4000714016C80B3A35DA25DA26C5C6E4813E06CD9C03E13FF90387FFFFC011F13 +F00103138030257DA435>II123 D E /Fp 17 120 df11 D<133F14C0EB07F06D7E801301A26D7E +A3147FA36E7EA36E7EA36E7EA36E7EA36E7EA36E7EA26E7EA214014A7E5C4A7E91381E3F +80143C14784A6C7E1301EB03E049486C7EEB0F80EB1F00496D7E137E5B48486D7E485A48 +5A000F6E7E485A485A48C87E12FE167F4816800070151F293B7CB930>21 +D<027FB512C00103B612E0130F5B017F15C09026FF81FEC7FC3901FC007E48487F485A49 +7F484880485AA248C7FCA2127EA2153F00FE92C7FC5AA25D157E5A5DA24A5AA24A5A007C +495A5D003C495A003E013FC8FC6C137C380F81F83803FFE0C66CC9FC2B257DA32F>27 +D34 D<121C127FEAFF80A5EA7F00121C0909798817> +58 D<121C127FEAFF80A213C0A3127F121C1200A412011380A2120313005A1206120E5A +5A5A12600A19798817>I<1760177017F01601A21603A21607160FA24C7EA21633167316 +6316C3A2ED0183A2ED0303150683150C160115181530A21560A215C014011580DA03007F +A202061300140E140C5C021FB5FC5CA20260C7FC5C83495A8349C8FC1306A25BA25B1338 +5B01F01680487E000716FFB56C013F13FF5EA2383C7DBB3E>65 D<0103B812E05BA29026 +0007F8C7123F4B140FF003C0140F18015DA2141FA25D1980143FA25D1760027F14E095C7 +FC92C75AA24A1301A24A495A16070101141F91B6FC94C8FCA2903903FC001F824A130EA2 +1307A24A130CA2010F141CA24A90C9FCA2131FA25CA2133FA25CA2137FA291CBFC497EB6 +12C0A33B397DB835>70 D<0103B6FC5B5E90260007FCC8FC5D5D140FA25DA2141FA25DA2 +143FA25DA2147FA292C9FCA25CA25CA21301A25CA21303A25CA2130718404A15C0A2010F +150118804A1403A2011F16005F4A1406170E013F151E171C4A143C177C017F5D160391C7 +120F49EC7FF0B8FCA25F32397DB839>76 D<0103B7FC4916E018F8903B0007F80007FC4B +EB00FE187F020FED3F80F01FC05DA2021F16E0A25DA2143FF03FC05DA2027FED7F80A292 +C8130018FE4A4A5A604AEC07F04D5A0101ED3FC04CB4C7FC91B612FC17E0D903FCCAFCA2 +5CA21307A25CA2130FA25CA2131FA25CA2133FA25CA2137FA291CBFC497EB6FCA33B397D +B835>80 D<0103B612F849EDFF8018E0903B0007F8001FF84BEB03FCEF00FE020F157FA2 +4BEC3F80A2021F16C0A25DA2143FF07F805DA2027FEDFF006092C7485A4D5A4A4A5A4D5A +4AEC1F80057FC7FC0101EC07F891B612E094C8FC9139FC000FC00103EC03F0707E4A6D7E +831307177E5C177F010F5D5F5CA2011F1401A25CA2133F16034A4A1360A2017F17E019C0 +91C71401496C01011480B61503933900FE0700EF7E0ECAEA1FFCEF07F03B3B7DB83F>82 +D<0003B812FEA25A903AF8003FC00101C0913880007E4848163C90C7007F141C121E001C +92C7FCA2485CA200305C007017180060130112E0485CA21403C716005DA21407A25DA214 +0FA25DA2141FA25DA2143FA25DA2147FA292C9FCA25CA25CA21301A25CA21303A25CEB0F +FC003FB6FC5AA237397EB831>84 D101 D110 D<13F8D803FE1438D8070F147C000E6D13FC121C1218003814011230D870 +1F5C12601503EAE03F00C001005B5BD8007E1307A201FE5C5B150F1201495CA2151F1203 +49EC80C0A2153F1681EE0180A2ED7F0303FF130012014A5B3A00F8079F0E90397C0E0F1C +90393FFC07F8903907F001F02A267EA430>117 D<01F8EB03C0D803FEEB07E0D8070F13 +0F000E018013F0121C12180038140700301403D8701F130112601500D8E03F14E000C090 +C7FC5BEA007E16C013FE5B1501000115805B150316001203495B1506150E150C151C1518 +15385D00015C6D485A6C6C485AD97E0FC7FCEB1FFEEB07F024267EA428>I<01F816F0D8 +03FE9138E001F8D8070F903801F003000ED9800314FC121C12180038020713010030EDE0 +00D8701F167C1260030F143CD8E03F163800C001005B5BD8007E131F183001FE5C5B033F +1470000117604991C7FCA218E000034A14C049137E17011880170318005F03FE1306170E +000101015C01F801BF5B3B00FC039F8070903A7E0F0FC0E0903A1FFC03FFC0902703F000 +7FC7FC36267EA43B>I E /Fq 27 122 df<903901F803F8EB07FE130F131F133FEB7F0E +EB7E0201FEC8FC5BA21201ACB538FE03F8A53801FC00B3AE253B7FBA2D>12 +D45 D50 D69 +DI78 D83 DI97 D99 DII<14FF010713C05B5B5BEB7F819038FE0040491300485AA212 +03ACB512FCA5D803F8C7FCB3AE1A3B7FBA19>I<903907E001F890383FFC1F90397FFEFF +FC48B6FC5A9039F81FF8003907F00FE048486C7EEBC003A248486C7EA76C6C485AA2EBE0 +076C6C485A6C6C485A48B5FC5D4849C7FCEB3FFC381F07E090C9FCA37F7F6CB512C015F8 +15FE6CECFF8016C04815E05A3A3F80007FF048C7120F007EEC03F8481401A46C1403007E +15F0D87F80130F6C6CEB1FE03A1FFC01FFC06CB612806C1500000114FC6C6C13F0010790 +C7FC26387EA52A>I<12FEB3A2EB01FC90380FFF804913C0017F13E090B512F039FFF81F +F8EBE007EBC003018013FC14011300A35AB3A71E3A7AB92B>I<12FFA81200AC127FB3B3 +08397BB814>I<12FEB3B3B3A4073A7AB914>108 DI +III<14 +F0EAFC07130F133F137F13FF00FD130013FCEAFFF05B5BA25B90C7FCA35AB3A414267AA5 +1C>114 DII<00FEEB01FCB3AA1403A214076C131F387F807F +90B5FC6C13F914F1000F13C1D803FCC7FC1E267AA42B>I120 DI +E /Fr 7 121 df12 +D20 D<173CA2173E171E171F8384717E170384717E717E187C007FB812FEBAFC856C +84CBEA03F0727EF000FEF13F80F11FE0F107F8F101FFA2F107F8F11FE0F13F80F1FE00F0 +01F84E5A007FB912C0BA5A96C7FC6C5FCB127C604D5A4D5A6017074D5A95C8FC5F171E17 +3E173CA248307BAC53>41 D<91381FFFFE91B6FC1303010F14FED91FF0C7FCEB7F8001FE +C8FCEA01F8485A485A485A5B48C9FCA2123EA25AA2127812F8A25AA2B712FE16FFA216FE +00F0C9FCA27EA21278127CA27EA27EA26C7E7F6C7E6C7E6C7EEA00FEEB7F80EB1FF06DB5 +12FE010314FF1300021F13FE283279AD37>50 D102 +D<12FCEAFFC0EA07F0EA01FCEA007E7F80131F80130FB3A7801307806D7E6D7EEB007EEC +1FF0EC07F8EC1FF0EC7E00495A495A495A5C130F5CB3A7131F5C133F91C7FC137E485AEA +07F0EAFFC000FCC8FC1D537ABD2A>I<137E3801FFC03807C1E0380F0070001E1338003E +131C48130C141E147E5AA3143C1400A3127CA37E121E7E6C7E6C7EEA00F013FCEA03FF38 +0F8780381F01E0003E13F0EB00F848137CA200FC133E5A141FA6127C143F6C133EA26C13 +7CEA0F80000713F83801E1F03800FFC0EB3F00130FEB03C0EB01E0EB00F01478147C143E +A3141FA3123C127EA3143E127812300038137C6C13786C13F0380783E03803FF8038007E +00184C7ABA25>120 D E /Fs 22 122 df12 D<120EEA3F80127F12FFA31300127E123C09097788 +19>46 D65 D<14F8EB07FE90381F871C90 +383E03FE137CEBF801120148486C5A485A120FEBC001001F5CA2EA3F801403007F5C1300 +A21407485C5AA2140F5D48ECC1C0A2141F15831680143F1587007C017F1300ECFF076C48 +5B9038038F8E391F0F079E3907FE03FC3901F000F0222677A42A>97 +D<147F903803FFC090380FC1E090381F0070017E13784913383901F801F83803F0031207 +13E0120FD81FC013F091C7FC485AA2127F90C8FCA35A5AA45AA3153015381578007C14F0 +007EEB01E0003EEB03C0EC0F806CEB3E00380F81F83803FFE0C690C7FC1D2677A426>99 +DI<147F903803FFC090380FC1E090383F00F0017E13785B485A485A485A120F4913 +F8001F14F0383F8001EC07E0EC1F80397F81FF00EBFFF891C7FC90C8FC5A5AA55AA21530 +007C14381578007E14F0003EEB01E0EC03C06CEB0F806CEB3E00380781F83803FFE0C690 +C7FC1D2677A426>I103 DII107 +DIII<147F903803FFC090380FC1F090381F00F8017E137C5B4848 +137E4848133E0007143F5B120F485AA2485A157F127F90C7FCA215FF5A4814FEA2140115 +FC5AEC03F8A2EC07F015E0140F007C14C0007EEB1F80003EEB3F00147E6C13F8380F83F0 +3803FFC0C648C7FC202677A42A>I<9039078007C090391FE03FF090393CF0787C903938 +F8E03E9038787FC00170497EECFF00D9F0FE148013E05CEA01E113C15CA2D80003143FA2 +5CA20107147FA24A1400A2010F5C5E5C4B5A131F5EEC80035E013F495A6E485A5E6E48C7 +FC017F133EEC70FC90387E3FF0EC0F8001FEC9FCA25BA21201A25BA21203A25B1207B512 +C0A3293580A42A>I<3903C003F0390FF01FFC391E783C0F381C7C703A3C3EE03F803838 +3FC0EB7F800078150000701300151CD8F07E90C7FCEAE0FE5BA2120012015BA312035BA3 +12075BA3120F5BA3121F5BA3123F90C9FC120E212679A423>114 +D<14FE903807FF8090380F83C090383E00E04913F00178137001F813F00001130313F0A2 +15E00003EB01C06DC7FC7FEBFFC06C13F814FE6C7F6D13807F010F13C01300143F141F14 +0F123E127E00FE1480A348EB1F0012E06C133E00705B6C5B381E03E06CB45AD801FEC7FC +1C267AA422>II<13F8D8 +03FEEB01C0D8078FEB03E0390E0F8007121E121C0038140F131F007815C01270013F131F +00F0130000E015805BD8007E133FA201FE14005B5D120149137EA215FE120349EBFC0EA2 +0201131E161C15F813E0163CD9F003133814070001ECF07091381EF8F03A00F83C78E090 +393FF03FC090390FC00F00272679A42D>I<01F01507D803FC903903801F80D8071E9039 +07C03FC0D80E1F130F121C123C0038021F131F49EC800F00701607A249133FD8F07E1680 +00E0ED000313FEC64849130718000001147E5B03FE5B0003160E495BA2171E0007010114 +1C01E05B173C1738A217781770020314F05F0003010713016D486C485A000190391E7C07 +802800FC3C3E0FC7FC90393FF81FFE90390FE003F0322679A437>119 +D<13F0D803FCEB01C0D8071EEB03E0D80E1F1307121C123C0038140F4914C01270A24913 +1FD8F07E148012E013FEC648133F160012015B5D0003147E5BA215FE00075C5BA214015D +A314035D14070003130FEBF01F3901F87FE038007FF7EB1FC7EB000F5DA2141F003F5C48 +133F92C7FC147E147C007E13FC387001F8EB03E06C485A383C1F80D80FFEC8FCEA03F023 +3679A428>121 D E /Ft 35 121 df49 DII<163FA25E5E5D5DA25D5D5D5DA25D92B5FCEC01F7EC03E7140715C7EC0F87EC1F +07143E147E147C14F8EB01F0EB03E0130714C0EB0F80EB1F00133E5BA25B485A485A485A +120F5B48C7FC123E5A12FCB91280A5C8000F90C7FCAC027FB61280A531417DC038>I<00 +07150301E0143F01FFEB07FF91B6FC5E5E5E5E5E16804BC7FC5D15E092C8FC01C0C9FCAA +EC3FF001C1B5FC01C714C001DF14F09039FFE03FFC9138000FFE01FC6D7E01F06D138049 +15C0497F6C4815E0C8FC6F13F0A317F8A4EA0F80EA3FE0487E12FF7FA317F05B5D6C4815 +E05B007EC74813C0123E003F4A1380D81FC0491300D80FF0495AD807FEEBFFFC6CB612F0 +C65D013F1480010F01FCC7FC010113C02D427BC038>I<4AB47E021F13F0027F13FC49B6 +FC01079038807F8090390FFC001FD93FF014C04948137F4948EBFFE048495A5A1400485A +120FA248486D13C0EE7F80EE1E00003F92C7FCA25B127FA2EC07FC91381FFF8000FF017F +13E091B512F89039F9F01FFC9039FBC007FE9039FF8003FF17804A6C13C05B6F13E0A249 +15F0A317F85BA4127FA5123FA217F07F121FA2000F4A13E0A26C6C15C06D4913806C0180 +14006C6D485A6C9038E01FFC6DB55A011F5C010714C0010191C7FC9038003FF02D427BC0 +38>I<121E121F13FC90B712FEA45A17FC17F817F017E017C0A2481680007EC8EA3F0000 +7C157E5E00785D15014B5A00F84A5A484A5A5E151FC848C7FC157E5DA24A5A14035D1407 +4A5AA2141F5D143FA2147F5D14FFA25BA35B92C8FCA35BA55BAA6D5A6D5A6D5A2F447AC2 +38>II<903807FFC0013F13FC48B612804815E0260FF8 +0013F0D81FC0EB3FF848C7EA1FFC4815FE01C0130F486C14FF7FA66C485B6C4814FE000F +C7FCC8EA3FFCED7FF8EDFFF04A13E04A13801600EC07FC4A5A5D4A5A5D4A5A92C7FCA214 +7E147CA31478AA91C8FCA814F8EB03FE497E497FA2497FA56D5BA26D90C7FC6D5AEB00F8 +28467AC535>63 D65 D67 DI73 +D82 +D<003FBA12E0A59026FE000FEB8003D87FE09338003FF049171F90C71607A2007E180300 +7C1801A300781800A400F819F8481978A5C81700B3B3A20107B8FCA545437CC24E>84 +D<903801FFE0011F13FE017F6D7E48B612E03A03FE007FF84848EB1FFC6D6D7E486C6D7E +A26F7FA36F7F6C5A6C5AEA00F090C7FCA40203B5FC91B6FC1307013F13F19038FFFC0100 +0313E0000F1380381FFE00485A5B127F5B12FF5BA35DA26D5B6C6C5B4B13F0D83FFE013E +EBFFC03A1FFF80FC7F0007EBFFF86CECE01FC66CEB8007D90FFCC9FC322F7DAD36>97 +D99 DIIIII<137C48B4FC4813804813C0A24813E0A56C13C0A26C +13806C1300EA007C90C7FCAAEB7FC0EA7FFFA512037EB3AFB6FCA518467CC520>I107 +DI<90277F8007FEEC0FFCB590 +263FFFC090387FFF8092B5D8F001B512E002816E4880913D87F01FFC0FE03FF8913D8FC0 +0FFE1F801FFC0003D99F009026FF3E007F6C019E6D013C130F02BC5D02F86D496D7EA24A +5D4A5DA34A5DB3A7B60081B60003B512FEA5572D7CAC5E>I<90397F8007FEB590383FFF +8092B512E0028114F8913987F03FFC91388F801F000390399F000FFE6C139E14BC02F86D +7E5CA25CA35CB3A7B60083B512FEA5372D7CAC3E>II<90397FC00FF8B590B57E02C314E002CF14F89139DFC03FFC91 +39FF001FFE000301FCEB07FF6C496D13804A15C04A6D13E05C7013F0A2EF7FF8A4EF3FFC +ACEF7FF8A318F017FFA24C13E06E15C06E5B6E4913806E4913006E495A9139DFC07FFC02 +CFB512F002C314C002C091C7FCED1FF092C9FCADB67EA536407DAC3E>I<90387F807FB5 +3881FFE0028313F0028F13F8ED8FFC91389F1FFE000313BE6C13BC14F8A214F0ED0FFC91 +38E007F8ED01E092C7FCA35CB3A5B612E0A5272D7DAC2E>114 D<90391FFC038090B512 +87000314FF120F381FF003383FC00049133F48C7121F127E00FE140FA215077EA27F01E0 +90C7FC13FE387FFFF014FF6C14C015F06C14FC6C800003806C15806C7E010F14C0EB003F +020313E0140000F0143FA26C141F150FA27EA26C15C06C141FA26DEB3F8001E0EB7F0090 +38F803FE90B55A00FC5CD8F03F13E026E007FEC7FC232F7CAD2C>III119 DI E /Fu 14 117 df<120FEA3FC0EA7FE0EAFFF0 +A6EA7FE0EA3FC0EA0F000C0C7A8B19>46 D<147814F81303131FEA03FFB5FCA3EAFC1F12 +00B3B2007FB512FEA41F317AB02C>49 DI +I65 D70 D97 DI<903807FF80013F13F090B512FC3903FE01FE4848487EEA0FF8 +EA1FF0EA3FE0A2007F6D5A496C5A153000FF91C7FCA9127F7FA2003FEC07807F6C6C130F +000FEC1F00D807FE133E3903FF80FCC6EBFFF8013F13E0010790C7FC21217DA027>I<16 +F890390FFC07FE90387FFF9F48B6127F3907FC0FFC380FF003001F14FED9E001133E003F +ECFF1C1600A6001F5CEBF003000F5C3907FC0FF890B512E0486C1380D90FFCC7FC48C9FC +A37F7F90B512F015FE6CECFF8016E06C15F06C15F84815FC121F393F80001F48C7EA03FE +481401481400A46C14016C6CEB03FC6C6CEB07F86C6CEB0FF0D80FFCEB7FE00003B61280 +C6ECFE00010F13E028327EA12C>103 D105 D<3901F81F8000FFEB7FF0EC +FFF89038F9E3FC9038FBC7FE380FFF876C1307A213FEEC03FCEC01F8EC0060491300B1B5 +12F0A41F217EA024>114 D<9038FFE1C0000713FF5A383F803F387E000F14075A14037E +A26C6CC7FC13FCEBFFE06C13FC806CEBFF80000F14C06C14E0C6FC010F13F0EB007F140F +00F0130714037EA26C14E06C13076CEB0FC09038C01F8090B5120000F913FC38E03FE01C +217DA023>I<133CA5137CA313FCA21201A212031207001FB51280B6FCA3D807FCC7FCB0 +EC03C0A79038FE078012033901FF0F006C13FEEB3FFCEB0FF01A2F7EAE22>I +E /Fv 58 127 df<90383C03C090387E07E0A7EBFE0F01FC13C0A2007FB512FEB7FCA400 +3F14FE3901F81F80AC003FB512FEB7FCA46C14FE3903F03F00A200075BEBE07EA73803C0 +3C202E7DAD27>35 D40 D<127012F812FE7E6C7E6C7EEA +0FE06C7E12037F6C7E1200137EA27FA2EB1F80A3EB0FC0A4EB07E0ACEB0FC0A4EB1F80A3 +EB3F00A2137EA25B1201485A5B1207485AEA3FC0485A48C7FC5A12F81270133A7AB327> +I<130F497EA60078EB81E000FEEB87F000FF138FEBDFBF6CB512E06C14C0000F14000003 +13FCC613F0A2000313FC000F13FF003F14C04814E039FFDFBFF0EB1F8F00FE13870078EB +81E00000EB8000A66DC7FC1C207BA627>II<120FEA3FC013E0EA7FF0A213F8A2123FA2120F120113 +F01203EA07E0121FEA7FC0EAFF8013005A12700D14738927>I<121EEA7F80A2EAFFC0A4 +EA7F80A2EA1E000A0A728927>46 D<1538157C15FCA2140115F8140315F0140715E0140F +15C0141F1580143F1500A25C147E14FE5C13015C13035C13075C130F5CA2131F5C133F91 +C7FC5B137E13FE5B12015B12035BA212075B120F5B121F5B123F90C8FC5A127E12FE5AA2 +5A12781E3A7CB327>II<130E131FA25B5BA25B5A5A127FB5FCA2 +13BFEA7E3F1200B3AA003FB512805A15C01580A21A2F79AE27>II<001FB512E04814F0A315E090C8FCACEB1FF0EBFFFC14FF158015C0 +9038F03FE09038C00FF0EB0007003EEB03F8001C1301C7FC15FC1400A3127C12FEA21401 +15F84813036C14F0007F130F9038801FE0393FE07FC06CB512806C14006C5B000113F838 +007FC01E2F7CAD27>53 D57 D<121EEA7F80A2EAFFC0A4EA7F80A2EA1E00C7FCAC121EEA7F80A2EA +FFC0A4EA7F80A2EA1E000A20729F27>I<153815FC14011407140FEC3FF8EC7FE0ECFFC0 +01031300495AEB1FF8495A495A3801FF804890C7FCEA0FFC485AEA7FF0EAFFC05BA27FEA +7FF0EA1FF86C7EEA03FF6C7F38007FE06D7E6D7EEB07FE6D7E010013C0EC7FE0EC3FF8EC +0FFC14071401140015381E287CAA27>60 D<007FB512FEB7FCA4003F14FEC9FCA6003FB5 +12FEB7FCA46C14FE20127D9F27>I64 +DI<007FB5FCB612C08115F87E3907E003FCEC00FE157E157F81A6157E +A25D1403EC0FF890B55A15C015F081819038E000FE157FED3F80151FA2ED0FC0A6151F16 +80153FED7F004A5A007FB55AB65A5D15E06C1480222E7FAD27>I<387FFFFC14FFB612C0 +6C80813907E00FF81407EC01FC6E7EA2157E157F811680151FA316C0150FABED1F80A315 +3F1600A25D15FEA24A5A4A5A140F007FB55A5DB65A6C91C7FC14FC222E7FAD27>68 +D<387FFFC080B5FC7E5CD803F0C8FCB3AAED0780ED0FC0A7007FB6FCA2B7FC7E1680222E +7FAD27>76 D<3A7FF003FFE0486C4813F0A213FC007F6D13E000079038003E0013DEA313 +CFA3148013C714C0A213C314E0A213C114F0A3EBC0F8A31478147CA2143C143EA2141E14 +1F140FA3EC07BEA3EC03FEEA7FFCEAFFFE1401A26C486C5A242E7FAD27>78 +D<007FB5FCB612E081816C803907E003FEEC00FF81ED3F80151F16C0150FA6151F168015 +3FED7F005DEC03FE90B55A5D5D5D92C7FC01E0C8FCADEA7FFEB5FCA36C5A222E7FAD27> +80 DI<387FFFF0B512FE6E7E816C803907E01FF014076E7E1401811400A514015D1403 +4A5A141F90B55A5D5DA281EBE01F6E7E14076E7EA816F0EDF1F8A4397FFE01FBB5EBFFF0 +8016E06C48EB7FC0C8EA1F00252F7FAD27>I<90387FC0E03901FFF1F0000713FF5A5AEA +3FE0EB801F387F000F007E130712FE5A1403A3EC01E06C90C7FC127E127FEA3FC013F86C +B47E6C13F86C13FE6CEBFF80C614C0010F13E0010013F0140FEC07F81403140115FC1400 +127812FCA46CEB01F8A26C130390388007F09038F01FE090B5FC15C0150000F85B38701F +F81E307CAE27>I<387FFFF0B512F8A314F000FCC7FCB3B3ACB512F014F8A36C13F0153A +71B327>91 D<387FFFF0B512F8A37EEA0001B3B3ACEA7FFFB5FCA36C13F0153A7EB327> +93 D<131C137E3801FF80000713E0001F13F84813FC38FFE7FF13C3130000FC133F0078 +131E180B79AD27>I<13E0EA01F01207120F13E0EA1FC0EA3F00A2127E127C12FC5AA4B4 +FC138013C0127FA2123F1380EA0F000C1773B227>96 D<3803FFC0000F13F04813FC4813 +FF811380EC1FC0381F000F000480C71207A2EB0FFF137F0003B5FC120F5A383FFC07EA7F +C0130012FE5AA46C130F007F131FEBC0FF6CB612806C15C07E000313F1C69038807F8022 +207C9F27>IIIIII104 D<130F497E497EA46D5A6DC7FC90C8FCA7383FFF80487FA37EEA00 +0FB3A4007FB512F0B6FC15F815F07E1D2F7BAE27>I107 D<387FFF80B57EA37EEA000FB3B2007FB512 +F8B612FCA36C14F81E2E7CAD27>I<397F07C01F3AFF9FF07FC09039FFF9FFE091B57E7E +3A0FFC7FF1F89038F03FC001E0138001C01300A3EB803EB03A7FF0FFC3FF486C01E31380 +01F913E701F813E36C4801C313002920819F27>I<387FE07F39FFF1FFC001F713F090B5 +FC6C80000313C1EC01FCEBFE005B5BA25BB03A7FFF83FFE0B500C713F0A36C018313E024 +207F9F27>II<387FE0FFD8 +FFF313C090B512F0816C800003EB81FE49C67E49EB3F8049131F16C049130FA216E01507 +A6150F16C07F151F6DEB3F80157F6DEBFF009038FF83FEECFFFC5D5D01F313C0D9F0FEC7 +FC91C8FCAC387FFF80B57EA36C5B23317F9F27>I<90380FF03C90383FFE7E90B5FC0003 +14FE5A380FFC1F381FE007EBC003383F800148C7FC127EA200FE147E5AA67E007E14FEA2 +007F1301EA3F80EBC003381FE007380FF81F6CB5FC7E6C147E38007FFCEB0FF090C7FCAC +91381FFFF8A24A13FC6E13F8A226317E9F27>I<397FFC03FC39FFFE0FFF023F13804A13 +C0007F90B5FC39007FFE1F14F89138F00F809138E002004AC7FC5CA291C8FCA2137EAD00 +7FB57EB67EA36C5C22207E9F27>I<9038FFF3800007EBFFC0121F5A5AEB803F38FC000F +5AA2EC07806C90C7FCEA7F8013FC383FFFF06C13FC000713FF00011480D8000F13C09038 +003FE014070078EB03F000FC1301A27E14036CEB07E0EBE01F90B512C01580150000FB13 +FC38707FF01C207B9F27>I<133C137EA8007FB512F0B612F8A36C14F0D8007EC7FCAE15 +18157EA415FE6D13FC1483ECFFF86D13F06D13E0010313C0010013001F297EA827>I<39 +7FE01FF8486C487EA3007F131F00031300B21401A21403EBFC0F6CB612E016F07EEB3FFE +90390FF87FE024207F9F27>I<3A7FFC0FFF80486C4813C0A36C486C13803A07C000F800 +EBE00100035CA2EBF00300015CA2EBF80700005CA390387C0F80A36D48C7FCA3EB3F3FEB +1F3EA214FE6D5AA36D5AA26D5A22207E9F27>I<3A7FFE07FFE000FF15F06D5A497E007F +15E03A0F80001F00A36D5B0007143EA414F0EBC1F83903E3FC7CA4EBE79EA200011478A3 +01F713F8A2EBFF0F6C5CA3EBFE0790387C03E024207F9F27>I<393FFC1FFF486C5A1680 +16006C487E3901F807E06C6C485A4A5A017E90C7FC6D5AEB1F7E5C6D5A13076D5A5C8049 +7E130F497E143EEB3E3FEB7E1F90387C0F8001F87F00016D7E3803F0033A7FFE1FFF80A2 +B54813C06C486C1380A222207E9F27>I<3A7FFC0FFF80486C4813C0A36C486C13803A07 +E000F800000313015D13F00001130301F85B1200A26D485A137CA290387E0F80133EA201 +1F90C7FC5CA2130F149E14BE130714FC1303A25C1301A25CA213035CA213075C1208EA3E +0F007F5B131FD87E7FC8FCEA7FFE6C5A5B6C5AEA07C022317E9F27>I<001FB512FE4814 +FFA490380001FEEC03FCEC07F8EC0FF0001EEB1FE0C7EA3FC0EC7F80ECFF00495A495A49 +5AEB1FE0495A495A49C7FC485A4848131E4848133F485A485A485A485AB7FCA46C14FE20 +207E9F27>II<127812FCB3B3B3A21278063A70B327>II<3901F003803903FC +07C0000F130F381FFE1F393FFF7F80397FBFFF0038FE1FFE486C5A00F813F0387003E01A +0A7AAD27>I E /Fw 75 128 df<91393FE00FE0903A01FFF83FF8903A07E01EF83C903A +1F800FF07E903A3F001FE0FE017E133F4914C0485A1738484890381F8000ACB812C0A33B +03F0001F8000B3A7486C497EB50083B5FCA32F357FB42D>11 DI<137813FCA21201 +1203EA07F813E0EA0FC0EA1F801300123C5A5A12400E0E71B326>19 +D<123C127EB4FCA21380A2127F123D1201A412031300A25A1206120E120C121C5A5A1260 +09177AB315>39 D<14C01301EB0380EB0F00130E5B133C5B5BA2485A485AA212075B120F +90C7FC5AA2121E123EA3123C127CA55AB0127CA5123C123EA3121E121FA27E7F12077F12 +03A26C7E6C7EA213787F131C7F130FEB0380EB01C01300124A79B71E>I<12C07E127012 +3C121C7E120F6C7E6C7EA26C7E6C7EA27F1378137C133C133EA2131E131FA37F1480A5EB +07C0B0EB0F80A514005BA3131E133EA2133C137C137813F85BA2485A485AA2485A48C7FC +120E5A123C12705A5A124A7CB71E>I<123C127EB4FCA21380A2127F123D1201A4120313 +00A25A1206120E120C121C5A5A126009177A8715>44 DI<123C +127E12FFA4127E123C08087A8715>I<1530157815F8A215F01401A215E01403A215C014 +07A21580140FA215005CA2143EA2143C147CA2147814F8A25C1301A25C1303A25C1307A2 +495AA291C7FC5BA2131E133EA2133C137CA2137813F8A25B1201A25B1203A2485AA25B12 +0FA290C8FC5AA2121E123EA2123C127CA2127812F8A25A12601D4B7CB726>II<13075B5B137FEA07FFB5FC13BFEA +F83F1200B3B3A2497E007FB51280A319327AB126>IIII<000C14C0380FC00F +90B5128015005C5C14F014C0D80C18C7FC90C8FCA9EB0FC0EB7FF8EBF07C380FC03F9038 +001F80EC0FC0120E000CEB07E0A2C713F01403A215F8A41218127E12FEA315F0140712F8 +006014E01270EC0FC06C131F003C14806CEB7F00380F80FE3807FFF8000113E038003F80 +1D347CB126>I<14FE903807FF80011F13E090383F00F0017C13703901F801F8EBF003EA +03E01207EA0FC0EC01F04848C7FCA248C8FCA35A127EEB07F0EB1FFC38FE381F9038700F +809038E007C039FFC003E0018013F0EC01F8130015FC1400A24814FEA5127EA4127F6C14 +FCA26C1301018013F8000F14F0EBC0030007EB07E03903E00FC03901F81F806CB51200EB +3FFCEB0FE01F347DB126>I<1230123C003FB6FCA34814FEA215FC0070C7123800601430 +157015E04814C01401EC0380C7EA07001406140E5C141814385CA25CA2495A1303A3495A +A2130FA3131F91C7FCA25BA55BA9131C20347CB126>III<123C127E12FFA4127E123C1200 +B0123C127E12FFA4127E123C08207A9F15>I<007FB812C0B912E0A26C17C0CCFCAC007F +B812C0B912E0A26C17C033147C9C3C>61 D<15E0A34A7EA24A7EA34A7EA3EC0DFE140CA2 +EC187FA34A6C7EA202707FEC601FA202E07FECC00FA2D901807F1507A249486C7EA30106 +6D7EA2010E80010FB5FCA249800118C77EA24981163FA2496E7EA3496E7EA20001821607 +487ED81FF04A7ED8FFFE49B512E0A333367DB53A>65 DIIIIIIII<017FB5FCA39038003FE0EC1FC0B3B1127EB4FCA4EC3F80 +5A0060140000705B6C13FE6C485A380F03F03803FFC0C690C7FC20357DB227>IIIIIII82 +D<90381FE00390387FFC0748B5FC3907F01FCF390F8003FF48C7FC003E80814880A20078 +8000F880A46C80A27E92C7FC127F13C0EA3FF013FF6C13F06C13FF6C14C06C14F0C68001 +3F7F01037F9038003FFF140302001380157F153FED1FC0150F12C0A21507A37EA26CEC0F +80A26C15006C5C6C143E6C147E01C05B39F1FC03F800E0B512E0011F138026C003FEC7FC +22377CB42B>I<007FB712FEA390398007F001D87C00EC003E0078161E0070160EA20060 +160600E01607A3481603A6C71500B3AB4A7E011FB512FCA330337DB237>IIII<267FFFFC90B512C0A3000101E090381FF80026007F80EB +0FC0013F6E5A6E91C7FC6D6C130E010F140C6E5B6D6C133801035C6E13606D6C13E06D6C +485A5EDA7F83C8FCEC3FC715C6EC1FECEC0FFC5D14076E7EA26E7E815C6F7E9138063FC0 +140E4A6C7E9138180FF0EC380702707F91386003FCECC0010101804A6C7E49C77E498101 +0E6E7E010C6E7E131C496E7E01786E7E13FCD807FEEC1FFEB56C90B512F8A335337EB23A +>I91 D93 D<1320137013F8487EEA03DEEA078F380F0780381E03C0383C01E0 +387800F000E0133800401310150C78B326>I97 DI< +EB07F8EB3FFF9038FC07C03901F000E03903E003F03807C007120FEA1F80123F90380003 +E04890C7FCA2127E12FEAA127FA26C14187F001F14386D1330000F14706C6C13E03903F0 +01C03900FC0F8090383FFE00EB07F01D237EA122>I<153FEC0FFFA3EC007F81AEEB07F0 +EB3FFCEBFC0F3901F003BF3907E001FF48487E48487F8148C7FCA25A127E12FEAA127E12 +7FA27E6C6C5BA26C6C5B6C6C4813803A03F007BFFC3900F81E3FEB3FFCD90FE013002635 +7DB32B>III<151F90391FC07F809039FFF8E3C03901F07F +C73907E03F033A0FC01F83809039800F8000001F80EB00074880A66C5CEB800F000F5CEB +C01F6C6C48C7FCEBF07C380EFFF8380C1FC0001CC9FCA3121EA2121F380FFFFEECFFC06C +14F06C14FC4880381F0001003EEB007F4880ED1F8048140FA56C141F007C15006C143E6C +5C390FC001F83903F007E0C6B51280D91FFCC7FC22337EA126>III107 DI<2703F01FE013 +FF00FF90267FF80313C0903BF1E07C0F03E0903BF3803E1C01F02807F7003F387FD803FE +1470496D486C7EA2495CA2495CB3486C496C487EB53BC7FFFE3FFFF0A33C217EA041>I< +3903F01FC000FFEB7FF09038F1E0FC9038F3807C3907F7007EEA03FE497FA25BA25BB348 +6CEB7F80B538C7FFFCA326217EA02B>II<3903F03F8000FFEBFFE09038F3C0F89038F7007ED807FE7F6C48EB1F8049 +14C049130F16E0ED07F0A3ED03F8A9150716F0A216E0150F16C06D131F6DEB3F80160001 +FF13FC9038F381F89038F1FFE0D9F07FC7FC91C8FCAA487EB512C0A325307EA02B>I<90 +3807F00390383FFC07EBFC0F3901F8038F3807E001000F14DF48486CB4FC497F123F90C7 +7E5AA25A5AA9127FA36C6C5B121F6D5B000F5B3907E003BF3903F0073F3800F81EEB3FF8 +EB0FE090C7FCAAED7F8091380FFFFCA326307DA029>I<3803E07C38FFE1FF9038E38F80 +9038E71FC0EA07EEEA03ECA29038FC0F8049C7FCA35BB2487EB512E0A31A217FA01E>I< +EBFF06000713CE381F00FE003C133E48131E140E5A1406A27EA200FE90C7FC6C7EEA7FFC +383FFFC014F0000F7F6C7FC67FEB0FFF1300EC3F8000C0131F140F6C1307A37E15006C5B +6C130E6C5B38F7807838E1FFE038C07F8019237EA11E>I<1330A51370A313F0A21201A2 +12031207381FFFFEB5FCA23803F000AF1403A814073801F806A23800FC0EEB7E1CEB1FF8 +EB07E0182F7FAD1E>IIIII<3A7FFF807FF8A33A07F8001FC00003EC +0F800001EC070015066C6C5BA26D131C017E1318A26D5BA2EC8070011F1360ECC0E0010F +5BA2903807E180A214F3010390C7FC14FBEB01FEA26D5AA31478A21430A25CA214E05CA2 +495A1278D8FC03C8FCA21306130EEA701CEA7838EA1FF0EA0FC025307F9F29>I<003FB5 +12F0A2EB000F003C14E00038EB1FC00030EB3F800070137F1500006013FE495A13035CC6 +485A495AA2495A495A49C7FC153013FE485A12035B48481370485A001F14604913E0485A +387F000348130F90B5FCA21C207E9F22>II<001C1370387F01FC +00FF13FEA4007F13FC381C0070170879B226>127 D E /Fx 81 128 +df11 DIII16 D<121C127FEAFF80A8EA7F00 +AB123EAB121CABC7FCA8121C127FEAFF80A5EA7F00121C093C79BB17>33 +D<001C131C007F137F39FF80FF80A26D13C0A3007F137F001C131C00001300A400011301 +01801380A20003130301001300485B00061306000E130E485B485B485B006013601A197D +B92A>I<121C127FEAFF80A213C0A3127F121C1200A412011380A2120313005A1206120E +5A5A5A12600A1979B917>39 D<146014E0EB01C0EB0380EB0700130E131E5B5BA25B485A +A2485AA212075B120F90C7FCA25A121EA2123EA35AA65AB2127CA67EA3121EA2121F7EA2 +7F12077F1203A26C7EA26C7E1378A27F7F130E7FEB0380EB01C0EB00E01460135278BD20 +>I<12C07E12707E7E7E120F6C7E6C7EA26C7E6C7EA21378A2137C133C133E131EA2131F +7FA21480A3EB07C0A6EB03E0B2EB07C0A6EB0F80A31400A25B131EA2133E133C137C1378 +A25BA2485A485AA2485A48C7FC120E5A5A5A5A5A13527CBD20>I<121C127FEAFF80A213 +C0A3127F121C1200A412011380A2120313005A1206120E5A5A5A12600A19798817>44 +DI<121C127FEAFF80A5EA7F00121C0909798817>I<150C151E15 +3EA2153C157CA2157815F8A215F01401A215E01403A215C01407A21580140FA215005CA2 +141E143EA2143C147CA2147814F8A25C1301A25C1303A2495AA25C130FA291C7FC5BA213 +1E133EA2133C137CA2137813F8A25B1201A25B1203A25B1207A25B120FA290C8FC5AA212 +1E123EA2123C127CA2127812F8A25A12601F537BBD2A>IIIII<1538A2157815F8A2140114031407A2140F141F +141B14331473146314C313011483EB030313071306130C131C131813301370136013C012 +01EA038013005A120E120C5A123812305A12E0B712F8A3C73803F800AB4A7E0103B512F8 +A325397EB82A>I<0006140CD80780133C9038F003F890B5FC5D5D158092C7FC14FC3806 +7FE090C9FCABEB07F8EB3FFE9038780F803907E007E090388003F0496C7E12066E7EC87E +A28181A21680A4123E127F487EA490C71300485C12E000605C12700030495A00385C6C13 +03001E495A6C6C485A3907E03F800001B5C7FC38007FFCEB1FE0213A7CB72A>II<12301238123E003FB612E0A316C05A168016000070C71206 +0060140E5D151800E01438485C5D5DC712014A5A92C7FC5C140E140C141C5CA25CA214F0 +495AA21303A25C1307A2130FA3495AA3133FA5137FA96DC8FC131E233B7BB82A>III<121C127FEAFF80A5EA7F00121CC7FC +B2121C127FEAFF80A5EA7F00121C092479A317>I<121C127FEAFF80A5EA7F00121CC7FC +B2121C127F5A1380A4127F121D1201A412031300A25A1206A2120E5A121812385A126009 +3479A317>I63 D<1538A3157CA315FEA34A7EA34A6C7EA202077FEC063FA2020E7FEC0C1FA202 +1C7FEC180FA202387FEC3007A202707FEC6003A202C07F1501A2D901807F81A249C77F16 +7FA20106810107B6FCA24981010CC7121FA2496E7EA3496E7EA3496E7EA213E0707E1201 +486C81D80FFC02071380B56C90B512FEA3373C7DBB3E>65 DI<913A +01FF800180020FEBE003027F13F8903A01FF807E07903A03FC000F0FD90FF0EB039F4948 +EB01DFD93F80EB00FF49C8127F01FE153F12014848151F4848150FA248481507A2485A17 +03123F5B007F1601A35B00FF93C7FCAD127F6DED0180A3123F7F001F160318006C7E5F6C +7E17066C6C150E6C6C5D00001618017F15386D6C5CD91FE05C6D6CEB03C0D903FCEB0F80 +902701FF803FC7FC9039007FFFFC020F13F002011380313D7BBA3C>IIIIII< +B612C0A3C6EBC0006D5AB3B3AD497EB612C0A31A397EB81E>I75 DIIIII82 +D +I<003FB812E0A3D9C003EB001F273E0001FE130348EE01F00078160000701770A3006017 +30A400E01738481718A4C71600B3B0913807FF80011FB612E0A335397DB83C>II87 D89 D91 D<3901800180000313033907000700000E130E485B0018 +131800381338003013300070137000601360A200E013E0485BA400CE13CE39FF80FF806D +13C0A3007F137FA2393F803F80390E000E001A1974B92A>II<13101338137C13FE487E3803C780380783C0380F01E0381E +00F04813780070131C48130E00401304170D77B92A>I +96 DIIIII<147E903803FF8090380FC1E0EB1F87 +90383F0FF0137EA213FCA23901F803C091C7FCADB512FCA3D801F8C7FCB3AB487E387FFF +F8A31C3B7FBA19>III +IIII<2703F00FF0EB1FE000FFD93FFCEB7FF8913AF03F01 +E07E903BF1C01F83803F3D0FF3800FC7001F802603F70013CE01FE14DC49D907F8EB0FC0 +A2495CA3495CB3A3486C496CEB1FE0B500C1B50083B5FCA340257EA445>I<3903F00FF0 +00FFEB3FFCECF03F9039F1C01F803A0FF3800FC03803F70013FE496D7EA25BA35BB3A348 +6C497EB500C1B51280A329257EA42E>II<3903F01FE000FFEB7FF890 +38F1E07E9039F3801F803A07F7000FC0D803FEEB07E049EB03F04914F849130116FC1500 +16FEA3167FAA16FEA3ED01FCA26DEB03F816F06D13076DEB0FE001F614C09039F7803F00 +9038F1E07E9038F0FFF8EC1FC091C8FCAB487EB512C0A328357EA42E>II<3807E01F +00FFEB7FC09038E1E3E09038E387F0380FE707EA03E613EE9038EC03E09038FC00804913 +00A45BB3A2487EB512F0A31C257EA421>II<1318A51338A31378A313F8120112031207001FB5FCB6 +FCA2D801F8C7FCB215C0A93800FC011580EB7C03017E13006D5AEB0FFEEB01F81A347FB2 +20>IIIIII<003FB512FCA2EB8003D83E0013F8003CEB07F00038EB0FE012300070EB1F +C0EC3F800060137F150014FE495AA2C6485A495AA2495A495A495AA290387F000613FEA2 +485A485A0007140E5B4848130C4848131CA24848133C48C7127C48EB03FC90B5FCA21F24 +7EA325>II<001C131C007F137F39FF80FF80A5397F007F00001C +131C190978B72A>127 D E /Fy 15 122 df12 D<171F4D7E4D7EA24D7EA34C7F +A24C7FA34C7FA34C7FA24C7FA34C8083047F80167E8304FE804C7E03018116F883030381 +4C7E03078116E083030F814C7E031F81168083033F8293C77E4B82157E8403FE824B8002 +01835D840203834B800207835D844AB87EA24A83A3DA3F80C88092C97E4A84A2027E8202 +FE844A82010185A24A820103854A82010785A24A82010F855C011F717FEBFFFCB600F802 +0FB712E0A55B547BD366>65 D76 D86 D97 D<913801FFF8021FEBFF8091B612F0010315FC010F9038C00F +FE903A1FFE0001FFD97FFC491380D9FFF05B4817C048495B5C5A485BA2486F138091C7FC +486F1300705A4892C8FC5BA312FFAD127F7FA27EA2EF03E06C7F17076C6D15C07E6E140F +6CEE1F806C6DEC3F006C6D147ED97FFE5C6D6CEB03F8010F9038E01FF0010390B55A0100 +1580023F49C7FC020113E033387CB63C>99 D<4DB47E0407B5FCA5EE001F1707B3A49138 +01FFE0021F13FC91B6FC010315C7010F9038E03FE74990380007F7D97FFC0101B5FC4948 +7F4849143F484980485B83485B5A91C8FC5AA3485AA412FFAC127FA36C7EA37EA26C7F5F +6C6D5C7E6C6D5C6C6D49B5FC6D6C4914E0D93FFED90FEFEBFF80903A0FFFC07FCF6D90B5 +128F0101ECFE0FD9003F13F8020301C049C7FC41547CD24B>I<913803FFC0023F13FC49 +B6FC010715C04901817F903A3FFC007FF849486D7E49486D7E4849130F48496D7E481780 +48497F18C0488191C7FC4817E0A248815B18F0A212FFA490B8FCA318E049CAFCA6127FA2 +7F7EA218E06CEE01F06E14037E6C6DEC07E0A26C6DEC0FC06C6D141F6C6DEC3F806D6CEC +FF00D91FFEEB03FE903A0FFFC03FF8010390B55A010015C0021F49C7FC020113F034387C +B63D>I<137F497E000313E0487FA2487FA76C5BA26C5BC613806DC7FC90C8FCADEB3FF0 +B5FCA512017EB3B3A6B612E0A51B547BD325>105 D108 D110 D<90397FE003FEB590380FFF80033F13E04B +13F09238FE1FF89139E1F83FFC0003D9E3E013FEC6ECC07FECE78014EF150014EE02FEEB +3FFC5CEE1FF8EE0FF04A90C7FCA55CB3AAB612FCA52F367CB537>114 +D<903903FFF00F013FEBFE1F90B7FC120348EB003FD80FF81307D81FE0130148487F4980 +127F90C87EA24881A27FA27F01F091C7FC13FCEBFFC06C13FF15F86C14FF16C06C15F06C +816C816C81C681013F1580010F15C01300020714E0EC003F030713F015010078EC007F00 +F8153F161F7E160FA27E17E07E6D141F17C07F6DEC3F8001F8EC7F0001FEEB01FE9039FF +C00FFC6DB55AD8FC1F14E0D8F807148048C601F8C7FC2C387CB635>I<007FB500F09038 +7FFFFEA5C66C48C7000F90C7FC6D6CEC07F86D6D5C6D6D495A6D4B5A6F495A6D6D91C8FC +6D6D137E6D6D5B91387FFE014C5A6E6C485A6EEB8FE06EEBCFC06EEBFF806E91C9FCA26E +5B6E5B6F7E6F7EA26F7F834B7F4B7F92B5FCDA01FD7F03F87F4A486C7E4A486C7E020F7F +DA1FC0804A486C7F4A486C7F02FE6D7F4A6D7F495A49486D7F01076F7E49486E7E49486E +7FEBFFF0B500FE49B612C0A542357EB447>120 DI +E end +%%EndProlog +%%BeginSetup +%%Feature: *Resolution 600dpi +TeXDict begin +%%PaperSize: a4 + +%%EndSetup +%%Page: 1 1 +1 0 bop 1081 387 a Fy(V)-11 b(eri\014ed)44 b(Lexical)i(Analysis)1537 +680 y Fx(T)-7 b(obias)27 b(Nipk)n(o)n(w)1260 854 y Fw(T)-6 +b(ec)n(hnisc)n(he)25 b(Univ)n(ersit\177)-38 b(at)26 b(M)r(\177)-41 +b(unc)n(hen)964 945 y(Institut)25 b(f)r(\177)-41 b(ur)27 +b(Informatik,)e(80290)i(M)r(\177)-41 b(unc)n(hen,)27 +b(German)n(y)1237 1036 y Fv(http://www.in.tum.de/~nipko)q(w/)602 +1313 y Fu(Abstract.)42 b Fw(This)34 b(pap)r(er)g(presen)n(ts)g(the)g +(dev)n(elopmen)n(t)e(and)i(v)n(eri\014cation)g(of)h(a)602 +1404 y(\(v)n(ery)27 b(simple\))h(lexical)i(analyzer)f(generator)g(that) +g(tak)n(es)f(a)h(regular)g(expression)602 1495 y(and)i(yields)h(a)g +(functional)g(lexical)h(analyzer.)g(The)f(emphasis)f(is)i(on)e +(simplicit)n(y)602 1587 y(and)20 b(executabilit)n(y)-6 +b(.)20 b(The)h(w)n(ork)f(w)n(as)i(carried)f(out)f(with)h(the)f(help)g +(of)i(the)e(theorem)602 1678 y(pro)n(v)n(er)25 b(Isab)r(elle/HOL.)365 +1979 y Ft(1)112 b(In)m(tro)s(duction)365 2197 y Fx(Admittedly)-7 +b(,)31 b(lexical)e(analysis)f(is)i(not)f(exactly)g(safet)n(y)g +(critical.)g(But)h(if)g(the)g(dream)f(of)h(a)365 2297 +y(v)n(eri\014ed)f(compiler)g(is)h(to)g(b)r(e)g(tak)n(en)f(seriously)-7 +b(,)29 b(it)h(m)n(ust)g(include)g(the)g(fron)n(t)f(end)h(as)f(w)n(ell.) +365 2397 y(Practical)h(applications)h(aside,)g(lexical)h(analysis)e(is) +i(an)f(excellen)n(t)h(example)f(of)h(compu-)365 2496 +y(tational)i(discrete)g(mathematics,)h(and)f(as)g(suc)n(h)g(an)g(ideal) +g(test)h(case)f(for)g(an)n(y)g(aspiring)365 2596 y(theorem)27 +b(pro)n(v)n(er.)490 2699 y(W)-7 b(e)20 b(formalize)e(and)h(v)n(erify)g +(the)h(pro)r(cess)e(of)h(taking)g(a)g(regular)e(expression)h(and)h +(turning)365 2799 y(it)h(in)n(to)f(a)f(lexical)h(analyzer)e(\(also)h +(called)h Fs(sc)l(anner)9 b Fx(\).)19 b(The)g(design)g(goals)e(are)h +(simplicit)n(y)h(and)365 2899 y(executabilit)n(y)-7 b(.)27 +b(The)g(result)f(is)h(an)g(almost)f(executable)g(functional)h(program,) +e(except)i(for)365 2998 y(one)20 b(place,)g(where)f(simplicit)n(y)h +(has)g(prev)-5 b(ailed)20 b(o)n(v)n(er)e(executabilit)n(y)-7 +b(.)20 b(The)g(o)n(v)n(erall)e(structure)365 3098 y(of)j(b)r(oth)f(the) +h(v)n(eri\014ed)f(theories)f(and)h(the)h(main)g(sections)e(of)i(the)f +(pap)r(er)g(is)h(sho)n(wn)e(in)i(Fig.)k(1.)490 3201 y(The)j(v)n +(ertical)f(arro)n(ws)f(describ)r(e)i(the)h(w)n(ell-kno)n(wn)e +(translation)g(of)h(a)g(regular)f(expres-)365 3301 y(sion)i(in)n(to)g +(a)g(deterministic)h(automaton.)e(This)h(is)g(the)h(sub)5 +b(ject)30 b(of)f Fr(x)p Fx(3{4.)f(W)-7 b(e)29 b(follo)n(w)g(the)365 +3401 y(standard)e(textb)r(o)r(ok)g(treatmen)n(t)h(but)g(rely)f(on)g +(functions)h(to)g(represen)n(t)e(automata.)490 3504 y(The)c(horizon)n +(tal)e(arro)n(ws)g(describ)r(e)h(the)i(actual)e(scanner.)g(Roughly)g +(sp)r(eaking,)h(a)f(scan-)365 3604 y(ner)27 b(con)n(v)n(erts)f(a)h +(string)g(in)n(to)g(a)g(list)h(of)f(`tok)n(ens'.)g(W)-7 +b(e)28 b(ha)n(v)n(e)e(simpli\014ed)i(the)g(mo)r(del)g(b)n(y)f(re-)365 +3703 y(placing)22 b(the)h(tok)n(ens)f(b)n(y)h(the)g(substrings)f +(themselv)n(es.)g(In)h(addition,)f(the)h(scanner)f(returns)365 +3803 y(the)35 b(unrecognized)d(su\016x)i(of)g(the)h(input.)g(Th)n(us)e +(function)i Fq(scan)f Fx(tak)n(es)f(a)g(string)h Fp(w)i +Fx(and)365 3903 y(returns)27 b(a)g(pair)g(of)417 4084 +y Fo({)41 b Fx(a)27 b(list)h([)p Fp(u)785 4096 y Fn(1)822 +4084 y Fp(;)14 b(:)g(:)g(:)f(;)h(u)1054 4096 y Fm(n)1099 +4084 y Fx(])28 b(that)f(is)g(obtained)g(b)n(y)h(rep)r(eatedly)e(c)n +(hopping)h(o\013)g(the)h(remaining)506 4184 y(input)h(the)f(maximal)f +(nonempt)n(y)g(pre\014x)g Fp(u)1878 4196 y Fm(i)1933 +4184 y Fx(that)h(is)g(recognized)e(b)n(y)h Fp(A)p Fx(,)417 +4287 y Fo({)41 b Fx(and)28 b(the)g(remaining)f(unrecognized)f(su\016x)h +Fp(v)s Fx(.)365 4465 y(In)38 b(particular)e(this)i(means)f(the)h +(concatenation)e Fp(u)2049 4477 y Fn(1)2100 4465 y Fp(:)14 +b(:)g(:)g(u)2259 4477 y Fm(n)2303 4465 y Fp(v)41 b Fx(yields)d(the)g +(input)g Fp(w)r Fx(.)g(Al-)365 4565 y(though)44 b(this)g(scanning)g +(pro)r(cess)e(is)i(not)g(giv)n(en)g(m)n(uc)n(h)f(atten)n(tion)h(in)h +(the)f(literature,)365 4664 y(a)38 b(precise)f(sp)r(eci\014cation)h +(and)g(a)g(v)n(eri\014ed)f(implemen)n(tation)i(of)f Fq(scan)g +Fx(turns)g(out)g(to)g(b)r(e)365 4764 y(v)n(ery)g(in)n(teresting)g(and)h +(is)g(the)g(sub)5 b(ject)39 b(of)g Fr(x)p Fx(5.)f(All)h(theories)f(are) +g(a)n(v)-5 b(ailable)38 b(online)g(at)365 4863 y Fl(http://www.in.tum)o +(.d)o(e/~)o(is)o(abe)o(ll)o(e/)o(lib)o(ra)o(ry/)o(HO)o(L/L)o(ex)o(/)p +Fx(.)p eop +%%Page: 2 2 +2 1 bop 1819 444 a Fw(regular)27 b(expression)p 2120 +576 4 95 v 2122 576 a Fk(?)p 1929 576 385 4 v 1929 765 +4 189 v 1979 688 a Fj(rexp2nae)p 2311 765 V 1929 768 +385 4 v 2120 860 4 95 v 1415 924 a Fw(nondeterministic)f(automaton)f +(with)h Fi(")p Fw(-mo)n(v)n(es)p 2120 1049 V 2122 1049 +a Fk(?)p 1929 1049 385 4 v 1929 1238 4 189 v 2009 1169 +a Fj(nae2da)p 2311 1238 V 1929 1241 385 4 v 2120 1332 +4 95 v 1710 1396 a Fw(deterministic)f(automaton)p 2120 +1521 V 2122 1521 a Fk(?)p 1929 1521 385 4 v 1929 1710 +4 189 v 2052 1632 a Fj(scan)p 2311 1710 V 1929 1713 385 +4 v 1526 1633 a Fw(string)p 1744 1617 189 4 v 1850 1615 +a Fk(-)p 2311 1617 V 484 w(-)2525 1634 y Fw(\(string)h(list,)g +(string\))1762 1968 y Fu(Fig.)15 b(1.)25 b Fw(The)h(structure)805 +2244 y Fx(W)-7 b(e)40 b(assume)f(that)g(the)h(reader)e(is)h(familiar)g +(with)h(the)g(standard)e(theory)h(of)g(\014nite)681 2343 +y(automata)25 b(and)h(regular)f(expressions)g(as)g(describ)r(ed,)h(for) +g(example,)g(in)h(the)g(textb)r(o)r(ok)f(b)n(y)681 2443 +y(Hop)r(croft)h(and)h(Ullman)d([6)o(].)681 2681 y Fo(1.1)94 +b(Notation)681 2837 y Fx(Although)43 b(w)n(e)f(ha)n(v)n(e)g(talk)n(ed)g +(ab)r(out)h(`strings')f(ab)r(o)n(v)n(e,)f(there)i(is)g(no)f(need)h(for) +f(a)h(new)681 2937 y(datat)n(yp)r(e:)24 b(strings)f(are)h(simply)g +(lists,)h(and)f(w)n(e)g(don't)g(ev)n(en)g(need)h(to)f(\014x)g(the)h +(alphab)r(et.)g(In)681 3036 y(the)32 b(sequel,)f(t)n(yp)r(e)g(v)-5 +b(ariable)31 b Fp(\013)g Fx(alw)n(a)n(ys)f(represen)n(ts)g(this)h +(alphab)r(et)h(and)f(w)n(e)g(use)g(`string')681 3136 +y(as)c(a)g(synon)n(ym)g(for)g(`list)h(o)n(v)n(er)d(t)n(yp)r(e)j +Fp(\013)p Fx('.)805 3236 y(A)k(few)f(w)n(ords)f(ab)r(out)h(notation)f +(in)i(Isab)r(elle/HOL)e(\(abbreviated)g(to)h(HOL)g(b)r(elo)n(w\).)681 +3335 y(List)f(notation)g(is)h(similar)e(to)i(ML)f(\(e.g.)h +Fl(@)f Fx(is)g(`app)r(end')h(and)f Fq(concat)g Fx(distributes)g +Fl(@)h Fx(o)n(v)n(er)681 3435 y(a)j(list)h(of)g(lists\))g(except)f +(that)h(the)h(`cons')e(op)r(eration)f(is)i(denoted)g(b)n(y)g +Fl(#)g Fx(instead)f(of)41 b Fl(::)p Fx(.)681 3534 y(There)e(is)h(also)e +(the)j(function)f Fq(set)g Fx(that)g(returns)f(the)h(set)g(of)f(elemen) +n(ts)h(of)g(a)f(list.)h(Set)681 3634 y(comprehension)26 +b(syn)n(tax)h(is)g Fr(f)p Fp(e)43 b Fl(.)g Fp(P)12 b +Fr(g)p Fx(.)27 b(F)-7 b(unction)28 b(t)n(yp)r(es)g(are)f(denoted)g(b)n +(y)h Fr(\))p Fx(.)805 3734 y(Thanks)h(to)f(Markus)g(W)-7 +b(enzel,)29 b(Isab)r(elle)g(has)f(recen)n(tly)g(acquired)g +Fs(long)j(identi\014ers)37 b Fx(of)681 3833 y(the)28 +b(form)f Fp(T)7 b(:n)27 b Fx(where)g Fp(T)39 b Fx(is)27 +b(the)h(name)g(of)f(a)g(theory)g(and)h Fp(n)f Fx(a)g(name)h(de\014ned)g +(in)g Fp(T)12 b Fx(.)805 3933 y(T)-7 b(o)28 b(distinguish)f(v)-5 +b(ariables)26 b(from)i(constan)n(ts,)e(the)i(latter)g(are)e(sho)n(wn)h +(in)h Fq(sans-serif)p Fx(.)681 4191 y Ft(2)112 b(Automata)681 +4380 y Fx(All)25 b(our)g(automata)f(will)h(b)r(e)h(triples)f(of)g(a)g +(start)g(state,)g(a)f(next)i(state)f(function)h(and)f(a)f(test)681 +4480 y(for)j(\014nal)g(states.)h(W)-7 b(e)28 b(de\014ne)f(three)h +(corresp)r(onding)d(pro)5 b(jections)27 b Fq(sta)n(rt)p +Fx(,)g Fq(next)h Fx(and)f Fq(\014n)p Fx(:)822 4623 y +Fj(sta)n(rt)p Fv(\(q,d,f\))41 b Fh(\021)e Fv(q)235 b +Fj(next)p Fv(\(q,d,f\))41 b Fh(\021)e Fv(d)235 b Fj(\014n)p +Fv(\(q,d,f\))41 b Fh(\021)e Fv(f)805 4764 y Fx(Our)f(formalization)e +(di\013ers)i(from)g(standard)f(automata)g(theory)g(in)h(the)h(follo)n +(wing)681 4863 y(asp)r(ects:)2101 5112 y(2)p eop +%%Page: 3 3 +3 2 bop 417 387 a Fo({)41 b Fx(there)28 b(are)e(no)i(\014niteness)f +(assumptions;)417 488 y Fo({)41 b Fx(neither)27 b(the)h(alphab)r(et)f +(nor)f(the)h(set)g(of)g(states)g(is)g(a)f(comp)r(onen)n(t)h(of)g(the)g +(automaton;)506 588 y(b)r(oth)h(are)f(implicit)h(in)g(the)g +Fs(typ)l(e)g Fx(of)g(the)g(comp)r(onen)n(ts.)365 843 +y Fo(2.1)95 b(Deterministic)29 b(automata)365 1016 y +Fx(Theory)f Fl(DA)f Fx(de\014nes)g(the)h(parameterized)e(t)n(yp)r(e)506 +1159 y Fv(\()p Fi(\013)p Fv(,)p Fi(\033)s Fv(\)da)41 +b(=)e Fi(\033)j Fh(\002)d Fv(\()p Fi(\013)h Fh(\))f Fi(\033)i +Fh(\))e Fi(\033)s Fv(\))h Fh(\002)e Fv(\()p Fi(\033)43 +b Fh(\))c Fv(bool\))365 1295 y Fx(of)24 b(deterministic)h(automata,)e +(where)h Fp(\033)j Fx(is)e(the)f(t)n(yp)r(e)g(of)h(states.)e(The)i +(only)e(painful)i(c)n(hoice)365 1394 y(is)h(the)g(order)f(of)h(argumen) +n(ts)e(of)i(the)g(transition)f(function:)i Fp(\033)f +Fr(\))e Fp(\013)f Fr(\))g Fp(\033)29 b Fx(or)c Fp(\013)f +Fr(\))f Fp(\033)j Fr(\))e Fp(\033)s Fx(?)365 1494 y(Both)34 +b(app)r(ear)g(in)h(the)f(literature)g(and)g(ha)n(v)n(e)f(their)i(minor) +e(adv)-5 b(an)n(tages)33 b(and)h(disadv)-5 b(an-)365 +1594 y(tages.)34 b(I)g(prefer)g(the)h(state)f(transformer)f(view.)h +(Final)g(states)g(are)g(enco)r(ded)g(via)g(a)g(test)365 +1693 y(function)28 b(rather)f(than)h(a)f(set)h(of)f(states)g(to)h(allo) +n(w)e(direct)i(execution.)490 1794 y(The)f(extension)h(of)f +Fq(next)h Fx(to)f(strings)g(is)h(called)f Fq(delta)o +Fx(:)2179 1764 y Fn(1)506 1937 y Fj(delta)38 b Fv(::)i(\()p +Fi(\013)p Fv(,)p Fi(\033)s Fv(\)da)g Fh(\))f Fi(\013)h +Fv(list)g Fh(\))f Fi(\033)j Fh(\))d Fi(\033)506 2028 +y Fj(delta)f Fv(A)i([])157 b(s)40 b(=)f(s)506 2120 y +Fj(delta)f Fv(A)i(\(a#w\))g(s)g(=)f Fj(delta)f Fv(A)i(w)f(\()p +Fj(next)g Fv(A)h(a)f(s\))490 2252 y Fx(A)28 b(w)n(ord)e(is)i(accepted)f +(b)n(y)g(a)h Fl(da)e Fx(if)i Fq(delta)g Fx(maps)f(the)h(start)f(state)g +(to)h(a)f(\014nal)g(state:)506 2394 y Fj(accepts)40 b +Fv(::)79 b(\()p Fi(\013)p Fv(,)p Fi(\033)s Fv(\)da)40 +b Fh(\))f Fi(\013)g Fv(list)i Fh(\))e Fv(bool)506 2486 +y Fj(accepts)h Fv(A)f(w)h Fh(\021)f Fj(\014n)g Fv(A)g(\()p +Fj(delta)f Fv(A)i(w)f(\()p Fj(sta)n(rt)h Fv(A\)\))365 +2781 y Fo(2.2)95 b(Nondeterministic)28 b(automata)365 +2953 y Fx(Nondeterministic)39 b(automata)e(come)g(in)i(t)n(w)n(o)e +(\015a)n(v)n(ours,)f(with)j(and)f(without)g Fp(")p Fx(-mo)n(v)n(es.)365 +3053 y(The)28 b(latter)f(are)g(de\014ned)h(b)n(y)f(the)h(t)n(yp)r(e)506 +3195 y Fv(\()p Fi(\013)p Fv(,)p Fi(\033)s Fv(\)na)41 +b(=)e Fi(\033)j Fh(\002)d Fv(\()p Fi(\013)h Fh(\))f Fi(\033)i +Fh(\))e Fi(\033)j Fv(set\))e Fh(\002)f Fv(\()p Fi(\033)j +Fh(\))d Fv(bool\))365 3332 y Fx(and)e(merely)f(serv)n(e)g(as)g(the)h +(stepping)g(stone)f(to)n(w)n(ards)f(the)j(former.)e(Adjoining)h(a)f +(new)365 3431 y(elemen)n(t)28 b Fp(")f Fx(to)h(the)g(alphab)r(et)f(is)h +(naturally)f(mo)r(deled)g(b)n(y)h(the)g(standard)e(datat)n(yp)r(e)506 +3574 y Fv(\()p Fi(\013)p Fv(\)option)42 b(=)d Fj(None)h +Fv(|)f Fj(Some)h Fi(\013)365 3716 y Fx(where)30 b Fq(None)g +Fx(represen)n(ts)f Fp(")p Fx(.)i(By)f(this)h(device)f(a)g +(nondeterministic)h(automaton)f(with)h Fp(")p Fx(-)365 +3816 y(mo)n(v)n(es)23 b(o)n(v)n(er)g(alphab)r(et)h Fp(\013)h +Fx(is)f(simply)g(a)g(nondeterministic)g(automaton)g(without)g +Fp(")p Fx(-mo)n(v)n(es)365 3916 y(o)n(v)n(er)i(alphab)r(et)i(\()p +Fp(\013)p Fx(\))p Fl(option)p Fx(:)506 4063 y Fv(\()p +Fi(\013)p Fv(,)p Fi(\033)s Fv(\)nae)41 b(=)e(\()p Fi(\013)h +Fv(option,)p Fi(\033)s Fv(\)na)490 4205 y Fx(That)26 +b(w)n(as)g(easy)-7 b(.)26 b(The)h(only)f(c)n(hoice)g(w)n(e)g(had)g(w)n +(as)g(whether)h(to)f(mo)r(del)h(the)g(transition)365 +4305 y(function)38 b(as)e(a)h(set-v)-5 b(alued)37 b(function)g(\(as)g +(w)n(e)g(did\))h(or)e(as)g(a)h(relation.)f(The)h(argumen)n(t)365 +4405 y(in)c(fa)n(v)n(our)e(of)h(a)h(set-v)-5 b(alued)32 +b(function)h(is)f(purely)g(computational:)g(pro)n(vided)g(the)h(set)f +(of)365 4504 y(next)27 b(states)f(of)g(ev)n(ery)f(state)h(is)g +(\014nite,)h(it)g(can)f(b)r(e)h(represen)n(ted)e(b)n(y)h(a)g(list,)g +(and)h(hence)f(the)365 4604 y(transition)31 b(function)h(is)f +(computable.)h(Using)f(a)g(relation,)g(it)h(is)f(unclear)g(in)g(what)h +(sense)365 4704 y(the)c(set)g(of)f(next)h(states)f(is)h(computable.)p +365 4778 473 4 v 382 4832 a Fg(1)442 4863 y Fw(With)21 +b(a)g(di\013eren)n(t)f(order)h(of)h(argumen)n(ts)e(w)n(e)h(could)g(ha)n +(v)n(e)f(de\014ned)g Fj(delta)38 b Fv(A)i Fh(\021)f Fj(foldl)f +Fv(\()p Fj(next)h Fv(A\))p Fw(.)1785 5112 y Fx(3)p eop +%%Page: 4 4 +4 3 bop 805 387 a Fx(Although)26 b(relations)e(are)g(not)h(so)f(nice)i +(for)e(computing,)h(they)h(are)e(handy)h(for)g(reason-)681 +487 y(ing.)i(Hence)h(w)n(e)f(de\014ne)h Fq(step)p Fx(,)f(the)h +(relational)f(v)n(ersion)f(of)h Fq(next)p Fx(:)822 630 +y Fj(step)39 b Fv(::)h(\()p Fi(\013)p Fv(,)p Fi(\033)s +Fv(\)nae)g Fh(\))f Fi(\013)h Fv(option)g Fh(\))f Fv(\()p +Fi(\033)j Fh(\002)d Fi(\033)s Fv(\)set)822 721 y Fj(step)g +Fv(A)h(a)f Fh(\021)g Fv({\(p,q\))i(.)e(q)g Fh(2)h Fj(next)f +Fv(A)h(a)f(p})681 862 y Fx(The)27 b(term)h Fq(eps)43 +b Fl(A)27 b Fx(is)h(short)f(for)g Fq(step)43 b Fl(A)g +Fq(None)27 b Fx(and)g(denotes)h(all)f Fp(")p Fx(-mo)n(v)n(es.)805 +962 y(Before)e(w)n(e)g(can)h(con)n(tin)n(ue,)f(w)n(e)g(need)h(t)n(w)n +(o)f(op)r(erations)g(from)g(the)h(standard)f(theory)g(of)681 +1061 y(relations:)19 b Fl(r^*)f Fx(is)i(the)h(re\015exiv)n(e)d +(transitiv)n(e)h(closure)g(of)27 b Fl(r)19 b Fx(and)h +Fl(s)43 b Fr(\014)g Fl(r)20 b Fx(is)g(the)g(comp)r(osition)681 +1161 y(of)34 b Fl(r)27 b Fx(and)g Fl(s)h Fx(\(mind)g(the)g(order!\):) +822 1308 y Fv(s)39 b Fh(\014)g Fv(r)h Fh(\021)f Fv({\(x,z\).)i +Fh(9)d Fv(y.)i(\(x,y\))g Fh(2)g Fv(r)f Fh(^)h Fv(\(y,z\))g +Fh(2)g Fv(s})805 1450 y Fx(The)28 b(extension)f(of)h +Fq(step)f Fx(to)g(lists)h(is)f(straigh)n(tforw)n(ard:)2546 +1419 y Fn(2)822 1592 y Fj(steps)40 b Fv(::)f(\()p Fi(\013)p +Fv(,)p Fi(\033)s Fv(\)nae)i Fh(\))e Fi(\013)g Fv(list)h +Fh(\))f Fv(\()p Fi(\033)j Fh(\002)d Fi(\033)s Fv(\)set)822 +1684 y Fj(steps)h Fv(A)f([])157 b(=)40 b(\()p Fj(eps)g +Fv(A\)^*)822 1775 y Fj(steps)g Fv(A)f(\(a#w\))h(=)g Fj(steps)f +Fv(A)h(w)79 b Fh(\014)f Fj(step)39 b Fv(A)g(\()p Fj(Some)h +Fv(a\))79 b Fh(\014)f Fv(\()p Fj(eps)40 b Fv(A\)^*)681 +1914 y Fx(The)23 b(term)f Fl(\()p Fq(eps)43 b Fl(A\)^*)21 +b Fx(is)i(the)g(so-called)e Fs(epsilon)27 b(closur)l(e)c +Fx(of)g(an)f Fl(nae)g(A)g Fx(that)h(relates)f(state)681 +2014 y Fl(s)27 b Fx(to)h(state)f Fl(t)g Fx(i\013)35 b +Fl(t)27 b Fx(is)h(reac)n(hable)d(from)j Fl(s)f Fx(b)n(y)g(a)g(\014nite) +i(sequence)e(of)g Fp(")p Fx(-mo)n(v)n(es.)805 2113 y(The)h(w)n(ords)e +(accepted)i(b)n(y)f(an)g Fl(nae)g Fx(are)f(de\014ned)i(as)f(usual:)822 +2256 y Fj(accepts)39 b Fv(::)h(\()p Fi(\013)p Fv(,)p +Fi(\033)s Fv(\)nae)g Fh(\))f Fi(\013)h Fv(list)g Fh(\))f +Fv(bool)822 2347 y Fj(accepts)g Fv(A)h(w)f Fh(\021)g(9)g +Fv(q.)h(\()p Fj(sta)n(rt)f Fv(A,q\))h Fh(2)g Fj(steps)f +Fv(A)h(w)f Fh(^)h Fj(\014n)f Fv(A)g(q)805 2489 y Fx(Note)32 +b(that)g Fq(step)o Fx(,)g Fq(steps)f Fx(and)h Fq(accepts)f +Fx(are)f(used)i(only)f(in)h(pro)r(ofs.)f(Hence)h(their)f(non-)681 +2588 y(executabilit)n(y)c(is)g(of)h(no)f(concern.)805 +2688 y(All)j(the)g(de\014nitions)g(in)g(this)f(subsection)h(reside)e +(in)i(theory)g Fl(NAe)p Fx(.)f(Th)n(us)g(w)n(e)g(can)g(dis-)681 +2787 y(tinguish,)f(for)f(example,)g Fl(DA.)p Fq(accepts)f +Fx(and)h Fl(NAe.)p Fq(accepts)n Fx(.)681 3015 y Fo(2.3)94 +b(Discussion)31 b(of)g(nondeterministic)e(automata)681 +3160 y Fx(Apart)f(from)f(the)i(fact)f(that)g(transition)g(functions)g +(are)f(arbitrary)f(functions)j(and)f(hence)681 3260 y(automata)d(need)h +(not)f(b)r(e)i(\014nite,)f(the)g(ab)r(o)n(v)n(e)f(treatmen)n(t)g(of)h +(nondeterministic)g(automata)681 3359 y(is)f(standard.)f(Ho)n(w)n(ev)n +(er,)f(it)i(w)n(as)f(not)h(un)n(til)h(after)e(a)h(n)n(um)n(b)r(er)g(of) +g(painful)g(iterations)f(that)i(I)681 3459 y(arriv)n(ed)f(at)i(this)g +(form)n(ulation.)f(There)g(are)g(three)h(di\013eren)n(t)g(options)f +(when)h(dealing)f(with)681 3558 y(the)f(extension)f(of)h(the)g(next)g +(state)f(function)h(to)g(w)n(ords,)e(whic)n(h)i(b)r(eha)n(v)n(e)f +(quite)h(di\013eren)n(tly)681 3658 y(in)j(pro)r(ofs:)716 +3803 y(1.)41 b(The)25 b(standard)g(one)g(is)g(of)g(t)n(yp)r(e)h +Fl(\()p Fp(\013)p Fl(,)p Fp(\033)s Fl(\)nae)42 b Fr(\))h +Fl(\()p Fp(\013)p Fl(\)list)f Fr(\))h Fp(\033)k Fr(\))d +Fl(\()p Fp(\033)s Fl(\)set)p Fx(.)24 b(This)822 3902 +y(is)i(ho)n(w)f(w)n(e)h(started,)g(but)g(it)h(leads)e(to)h(pro)r(ofs)g +(with)g(a)g(lot)g(of)g(duplication)g(b)r(ecause)g(of)822 +4002 y(the)i(asymmetry)f(b)r(et)n(w)n(een)g(input)h(\(single)g +(states\))f(and)h(output)g(\(sets)f(of)h(states\).)716 +4102 y(2.)41 b(A)30 b(m)n(uc)n(h)g(slic)n(k)n(er)f(v)n(ersion)g(is)h +(de\014ned)g(directly)g(on)g(sets)g(of)g(states,)g(i.e.)g(it)g(is)g(of) +h(t)n(yp)r(e)822 4201 y Fl(\()p Fp(\013)p Fl(,)p Fp(\033)s +Fl(\)nae)42 b Fr(\))h Fl(\()p Fp(\013)p Fl(\)list)f Fr(\))i +Fl(\()p Fp(\033)s Fl(\)set)e Fr(\))h Fl(\()p Fp(\033)s +Fl(\)set)p Fx(.)32 b(This)h(eliminates)g(the)h(asym-)822 +4301 y(metry)27 b(of)h(the)g(\014rst)f(v)n(ersion)f(and)i(results)f(in) +h(some)f(compact)g(algebraic)e(la)n(ws)i(lik)n(e)822 +4444 y Fj(delta)38 b Fv(A)h(\(u@v\))i(=)e Fj(delta)f +Fv(A)i(v)f Fh(\016)h Fj(delta)e Fv(A)h(u)822 4620 y Fx(Unfortunately)f +(it)g(also)e(leads)i(to)f(v)n(ery)g(complicated)g(argumen)n(ts)f(in)i +(those)g(cases)822 4719 y(where)27 b(only)g(single)g(states)g(are)g(in) +n(v)n(olv)n(ed,)f(e.g.)h(the)h(start)f(state.)p 681 4778 +473 4 v 697 4832 a Fg(2)758 4863 y Fw(I)e(ha)n(v)n(e)g(used)g +Fj(delta)g Fw(for)h(functions)g(and)g Fj(steps)g Fw(for)g(relations.) +2101 5112 y Fx(4)p eop +%%Page: 5 5 +5 4 bop 400 387 a Fx(3.)41 b Fq(steps)35 b Fx(is)h(an)f(excellen)n(t)g +(compromise)f(b)r(ecause)h(it)h(it)g(only)f(talks)g(ab)r(out)g +(individual)506 487 y(states)26 b(in)h(the)f(input)h(and)f(output,)h +(and)f(it)g(is)g(close)f(to)h(our)g(in)n(tuition.)g(On)g(the)h(other) +506 587 y(hand,)h(there)f(are)g(also)g(some)g(dra)n(wbac)n(ks)e(that)j +(w)n(e)f(discuss)g(in)h Fr(x)p Fx(4.)365 751 y(The)41 +b(touc)n(hstone)g(for)f(these)h(di\013eren)n(t)g(form)n(ulations)f(w)n +(as)g(the)h(correctness)e(pro)r(of)h(of)365 850 y(the)34 +b(translation)e(of)h(a)g(regular)f(expression)g(in)n(to)h(an)g +Fl(nae)f Fx(\(see)h Fr(x)p Fx(4\).)g(Our)g(conclusion)f(is)365 +950 y(corrob)r(orated)26 b(b)n(y)i(the)g(corresp)r(onding)e(textb)r(o)r +(ok)i(pro)r(of)d([6)o(]:)j(the)h(latter)f(do)r(es)g(not)g(use)g(a)365 +1050 y(set-v)-5 b(alued)33 b(transition)g(function)h(at)f(all)g +(\(although)g(it)h(has)f(b)r(een)h(de\014ned\))g(but)g(argues)365 +1149 y(informally)27 b(in)h(terms)f(of)h(`paths',)g(whic)n(h)f(corresp) +r(onds)f(to)h(the)h(relation)f Fq(steps)o Fx(.)365 1396 +y Fo(2.4)95 b(Equiv)-5 b(alences)365 1560 y Fx(Ev)n(ery)25 +b Fl(nae)g Fx(can)g(b)r(e)i(translated)d(in)n(to)i(an)f(equiv)-5 +b(alen)n(t)26 b Fl(na)f Fx(whic)n(h)g(can)h(then)g(b)r(e)g(translated) +365 1660 y(in)n(to)38 b(an)h(equiv)-5 b(alen)n(t)38 b +Fl(da)p Fx(.)f(Since)i(w)n(e)f(are)f(not)i(in)n(terested)f(in)g +Fl(na)p Fx(s,)g(w)n(e)g(ha)n(v)n(e)f(de\014ned)i(a)365 +1760 y(direct)24 b(translation)f(from)h Fl(nae)p Fx(s)f(in)n(to)h +Fl(da)p Fx(s)f(whic)n(h)h(com)n(bines)g(the)g(p)r(o)n(w)n(erset)f(and)h +Fp(")p Fx(-closure)365 1859 y(construction:)506 1986 +y Fj(nae2da)39 b Fv(::)h(\()p Fi(\013)p Fv(,)p Fi(\033)s +Fv(\)nae)g Fh(\))f Fv(\()p Fi(\013)p Fv(,)p Fi(\033)k +Fv(set\)da)506 2077 y Fj(nae2da)c Fv(A)h Fh(\021)f Fv(\({)p +Fj(sta)n(rt)g Fv(A},)1016 2168 y Fi(\025)g Fv(a)h(Q.)1297 +2108 y Ff(S)1366 2168 y Fv(\()p Fj(next)f Fv(A)h(\()p +Fj(Some)f Fv(a\))h(``)g(\(\()p Fj(eps)g Fv(A\)^*)g(^^)f(Q\)\),)1016 +2260 y Fi(\025)g Fv(Q.)h Fh(9)f Fv(p)g Fh(2)h Fv(\()p +Fj(eps)g Fv(A\)^*)g(^^)f(Q.)h Fj(\014n)f Fv(A)h(p\))365 +2401 y Fx(W)-7 b(e)25 b(use)f(t)n(w)n(o)f(further)h(standard)f +(constructs,)h(the)g(image)g(of)g(a)g(set)g(under)g(a)g(function)g(and) +365 2501 y(a)j(relation:)506 2627 y Fv(f)40 b(``)g(S)f +Fh(\021)g Fv({f)h(x)f(.)h(x)f Fh(2)g Fv(S})506 2718 y(r)h(^^)g(S)f +Fh(\021)g Fv({y.)h Fh(9)f Fv(x)g Fh(2)h Fv(S.)f(\(x,y\))i +Fh(2)e Fv(r})490 2860 y Fx(The)27 b(actual)h(equiv)-5 +b(alence)27 b(pro)r(of,)g(i.e.)h(the)g(pro)r(of)f(of)971 +3028 y Fl(DA.)p Fq(accepts)42 b Fl(\()p Fq(nae2da)g Fl(A\))h(w)g(=)g +(NAe.)p Fq(accepts)e Fl(A)j(w)499 b Fx(\(1\))365 3197 +y(is)28 b(b)n(y)f(rewriting)g(with)h(the)g(lemma)506 +3339 y Fv(\()p Fj(eps)40 b Fv(A\)^*)g(^^)g(\(DA.)p Fj(delta)f +Fv(\()p Fj(nae2da)g Fv(A\))h(w)f(S\))h(=)f Fj(steps)h +Fv(A)f(w)h(^^)f(S)365 3478 y Fx(whic)n(h)28 b(is)f(pro)n(v)n(ed)f(b)n +(y)i(induction)g(on)f Fl(w)p Fx(.)365 3745 y Ft(3)112 +b(Regular)37 b(expressions)365 3943 y Fx(Regular)27 b(expressions)g +(represen)n(t)g Fs(r)l(e)l(gular)j(sets)p Fx(.)f(The)f(latter)g(are)f +(sets)h(of)g(strings)g(\014nitely)365 4042 y(generated)f(from)h +(\014nite)h(sets)f(b)n(y)f(union,)i(concatenation)e(and)h(iteration)f +(\(the)i(star)e(op)r(er-)365 4142 y(ation\).)h(Concatenation)e(is)i +(de\014ned)g(explicitly)506 4283 y Fj(conc)40 b Fv(::)g +Fi(\013)f Fv(list)h(set)g Fh(\))f Fi(\013)h Fv(list)g(set)g +Fh(\))f Fi(\013)g Fv(list)h(set)506 4374 y Fj(conc)g +Fv(A)f(B)h Fh(\021)f Fv({xs@ys)h(.)g(xs)g Fh(2)f Fv(A)g +Fh(^)h Fv(ys)g Fh(2)f Fv(B})365 4516 y Fx(whereas)27 +b(the)h(star)e(op)r(eration)h(is)g(de\014ned)h(inductiv)n(ely:)506 +4652 y Fj(sta)n(r)40 b Fv(::)g Fi(\013)f Fv(list)h(set)g +Fh(\))f Fi(\013)h Fv(list)g(set)506 4743 y([])g Fh(2)g +Fj(sta)n(r)f Fv(A)506 4835 y(a)h Fh(2)f Fv(A)h Fh(^)f +Fv(as)h Fh(2)f Fj(sta)n(r)h Fv(A)f Fw(=)-13 b Fh(\))39 +b Fv(a@as)h Fh(2)g Fj(sta)n(r)f Fv(A)1785 5112 y Fx(5)p +eop +%%Page: 6 6 +6 5 bop 681 387 a Fx(Tw)n(o)27 b(easy)f(inductions)i(yield)g(an)f +(alternativ)n(e)f(c)n(haracterization)f(of)j Fq(sta)n(r)p +Fx(:)822 530 y Fv(w)39 b Fh(2)h Fj(sta)n(r)f Fv(A)h(=)f(\()p +Fh(9)g Fv(as.)h(\()p Fh(8)f Fv(a)h Fh(2)f Fj(set)h Fv(as.)g(a)f +Fh(2)g Fv(A\))h Fh(^)g Fv(\(w)f(=)h Fj(concat)f Fv(as\)\))805 +661 y Fx(Regular)27 b(expressions)f(are)g(de\014ned)i(as)f(usual)822 +804 y Fv(datatype)41 b Fi(\013)e Fv(rexp)i(=)e Fj(Empt)n(y)1489 +895 y Fv(|)g Fj(A)n(tom)h Fi(\013)1489 986 y Fv(|)f Fj(Union)f +Fv(\()p Fi(\013)i Fv(rexp\))g(\()p Fi(\013)g Fv(rexp\))1489 +1078 y(|)f Fj(Conc)h Fv(\()p Fi(\013)f Fv(rexp\))i(\()p +Fi(\013)f Fv(rexp\))1489 1169 y(|)f Fj(Sta)n(r)g Fv(\()p +Fi(\013)h Fv(rexp\))681 1310 y Fx(as)27 b(is)g(the)h +Fq(lang)o Fx(uage)f(denoted)h(b)n(y)f(a)g(regular)f(expression:)822 +1453 y Fj(lang)38 b Fv(::)i Fi(\013)g Fv(rexp)g Fh(\))f +Fi(\013)g Fv(list)h(set)822 1544 y Fj(lang)e(Empt)n(y)258 +b Fv(=)40 b({})822 1635 y Fj(lang)e Fv(\()p Fj(A)n(tom)i +Fv(a\))133 b(=)39 b({[a]})822 1727 y Fj(lang)f Fv(\()p +Fj(Union)h Fv(r)g(s\))h(=)f(\()p Fj(lang)g Fv(r\))h Fh([)f +Fv(\()p Fj(lang)g Fv(s\))822 1818 y Fj(lang)f Fv(\()p +Fj(Conc)i Fv(r)g(s\))62 b(=)39 b Fj(conc)h Fv(\()p Fj(lang)f +Fv(r\))g(\()p Fj(lang)g Fv(s\))822 1909 y Fj(lang)f Fv(\()p +Fj(Sta)n(r)h Fv(r\))174 b(=)40 b Fj(sta)n(r)f Fv(\()p +Fj(lang)g Fv(r\))681 2049 y Fx(Note)26 b(that)h(there)g(is)f(no)h +(separate)e(constructor)g(for)h(a)g(regular)f(expression)g(denoting)h +(the)681 2148 y(set)h Fr(f)p Fl([])p Fr(g)f Fx(b)r(ecause)h +Fq(Sta)n(r)e(Empt)n(y)i Fx(do)r(es)h(just)g(that.)681 +2404 y Ft(4)112 b(Regular)37 b(expressions)h(in)m(to)e +(nondeterministic)e(automata)681 2591 y Fx(This)29 b(section)g(is)h +(the)f(core)g(of)g(the)h(pap)r(er.)f(It)h(discusses)f(the)g +(transformation)f(of)i(regular)681 2690 y(expressions)36 +b(in)n(to)j(nondeterministic)f(automata)f(with)i Fp(")p +Fx(-transitions.)e(W)-7 b(e)39 b(follo)n(w)e(the)681 +2790 y(spirit)28 b(of)g(the)h(standard)e(inductiv)n(e)i(construction)24 +b([6)o(],)29 b(but)g(simplify)g(things)f(a)g(little:)h(w)n(e)681 +2889 y(do)23 b(not)g(insist)g(that)g(eac)n(h)f(automaton)g(has)h(only)g +(one)f(\014nal)h(state)g(and)g(no)g(transitions)f(out)681 +2989 y(of)j(this)g(state.)h(The)f(simpli\014ed)h(construction)e(of)h +(the)h(union)f(and)g(iteration)g(of)g(automata)681 3089 +y(is)i(sho)n(wn)g(in)h(Fig.)d(2.)i(The)h(capital)f Fp(F)39 +b Fx(represen)n(ts)26 b(a)i(set)f(of)h(\014nal)f(states.)p +799 3750 95 4 v 810 3748 a Fk(-)887 3850 y Fe(\026\025)887 +3650 y(\027\024)953 3757 y Fi(q)987 3765 y Fg(0)1082 +3748 y Fk(\000)1165 3665 y(\000)1188 3642 y(\000)-83 +b(\022)1082 3831 y(@)1165 3914 y(@)1188 3937 y(@)g(R)1121 +3897 y Fi(")1121 3651 y(")1265 3661 y Fe(\026\025)1265 +3461 y(\027\024)1331 3568 y Fi(q)1365 3576 y Fg(1)1265 +4039 y Fe(\026\025)1265 3839 y(\027\024)1331 3946 y Fi(q)1365 +3954 y Fg(2)1737 3661 y Fe(\026\025)1737 3461 y(\027\024)1754 +3644 y(\022\021)1754 3478 y(\023\020)1796 3581 y Fi(F)1845 +3589 y Fg(1)1737 4039 y Fe(\026\025)1737 3839 y(\027\024)1754 +4022 y(\022\021)1754 3856 y(\023\020)1796 3959 y Fi(F)1845 +3967 y Fg(2)1222 3419 y Fe(\037)p 1222 3568 4 18 v 1222 +3703 a(\036)1978 3419 y(\034)p 1978 3568 V 1978 3703 +a(\035)p 1357 3703 491 4 v 1357 3419 V 1222 3797 a(\037)p +1222 3946 4 18 v 1222 4081 a(\036)1978 3797 y(\034)p +1978 3946 V 1978 4081 a(\035)p 1357 4081 491 4 v 1357 +3797 V 2311 3750 95 4 v 2322 3748 a Fk(-)2398 3850 y +Fe(\026\025)2398 3650 y(\027)q(\024)2415 3833 y(\022\021)2415 +3667 y(\023\020)2465 3757 y Fi(q)2499 3765 y Fg(0)p 2594 +3750 189 4 v 2700 3748 a Fk(-)2652 3727 y Fi(")2776 3850 +y Fe(\026\025)2776 3650 y(\027)q(\024)2843 3757 y Fi(q)2877 +3765 y Fg(1)3249 3850 y Fe(\026\025)3249 3650 y(\027\024)3265 +3833 y(\022\021)3265 3667 y(\023\020)3308 3770 y Fi(F)3357 +3778 y Fg(1)2734 3608 y Fe(\037)p 2734 3757 4 18 v 2734 +3892 a(\036)3490 3608 y(\034)p 3490 3757 V 3490 3892 +a(\035)p 2869 3892 491 4 v 2869 3608 V 3348 3654 4 95 +v 2876 3654 V 2878 3654 a Fk(?)2876 3467 y Fe(\023)p +2876 3559 4 12 v 306 w(\020)p 3348 3559 V 2961 3467 307 +4 v 3096 3446 a Fi(")1444 4384 y Fu(Fig.)15 b(2.)25 b +Fw(Union)h(and)f(iteration)i(of)f(automata)805 4664 y +Fx(The)35 b(function)g(w)n(e)g(w)n(an)n(t)f(to)g(de\014ne)h(has)f(to)h +(b)r(e)g(of)f(t)n(yp)r(e)h Fl(\()p Fp(\013)p Fl(\)rexp)42 +b Fr(\))h Fl(\()p Fp(\013)p Fl(,)p Fp(\033)s Fl(\)nae)p +Fx(.)681 4764 y(It)32 b(remains)g(to)g(b)r(e)g(determined)g(what)h +Fp(\033)i Fx(should)d(b)r(e.)h(The)f(main)g(criterion)f(is)h(the)h +(ease)681 4863 y(of)f(renaming)f(the)h(states)f(of)h(an)g(automaton)f +(to)h(ensure)f(they)h(are)f(disjoin)n(t)h(from)f(some)2101 +5112 y(6)p eop +%%Page: 7 7 +7 6 bop 365 387 a Fx(other)36 b(automaton.)f(Graphically)-7 +b(,)34 b(this)j(is)e(easy:)g(simply)h(dra)n(w)f(the)h(t)n(w)n(o)f +(automata)g(in)365 487 y(nono)n(v)n(erlapping)f(areas)g(\(e.g.)i(as)g +(in)g(Fig.)25 b(2)35 b(on)h(the)h(left\).)g(Adding)f(o\013sets)g(to)g +(natural)365 587 y(n)n(um)n(b)r(ers)c(comes)g(to)h(mind,)g(but)g(this)g +(can)f(b)r(e)h(messy)g(in)f(pro)r(ofs.)g(Instead)h(w)n(e)f(use)g(lists) +365 686 y(of)d(Bo)r(oleans)e(and)h(stic)n(k)g Fq(T)-7 +b(rue)29 b Fx(or)e Fq(F)n(alse)h Fx(in)h(fron)n(t)f(to)g(guaran)n(tee)f +(distinctness.)i(Th)n(us)f(the)365 786 y(ab)r(o)n(v)n(e)f +Fp(\033)k Fx(is)c(simply)i Fl(\(bool\)list)23 b Fx(and)28 +b(w)n(e)f(de\014ne)h(the)g(t)n(yp)r(e)506 929 y Fv(\()p +Fi(\013)p Fv(\)bitsNAe)42 b(=)d(\()p Fi(\013)p Fv(,\(bool\)list\)nae) +365 1065 y Fx(and)28 b(the)g(function)506 1189 y Fj(rexp2nae)40 +b Fv(::)g Fi(\013)f Fv(rexp)i Fh(\))e Fi(\013)g Fv(bitsNAe)506 +1280 y Fj(rexp2nae)h(Empt)n(y)219 b Fv(=)39 b(\([],)h +Fi(\025)f Fv(a)h(s.)f({},)h Fi(\025)f Fv(s.)h Fj(F)n(alse)p +Fv(\))506 1372 y Fj(rexp2nae)q Fv(\()p Fj(A)n(tom)g Fv(a\))132 +b(=)40 b Fj(atom)f Fv(a)506 1463 y Fj(rexp2nae)q Fv(\()p +Fj(Union)f Fv(r)i(s\))f(=)h Fj(union)e Fv(\()p Fj(rexp2nae)i +Fv(r\))f(\()p Fj(rexp2nae)h Fv(s\))506 1554 y Fj(rexp2nae)q +Fv(\()p Fj(Conc)g Fv(r)f(s\))62 b(=)40 b Fj(conc)f Fv(\()p +Fj(rexp2nae)h Fv(r\))g(\()p Fj(rexp2nae)g Fv(s\))506 +1646 y Fj(rexp2nae)q Fv(\()p Fj(Sta)n(r)f Fv(r\))174 +b(=)39 b Fj(sta)n(r)h Fv(\()p Fj(rexp2nae)g Fv(r\))365 +1787 y Fx(Let)e(us)g(\014rst)f(examine)g(the)h(translation)f(of)g +Fq(Empt)n(y)p Fx(.)h(The)f(initial)h(state)g(is)f(the)h(empt)n(y)365 +1886 y(list.)g(The)f(transition)f(function)i(alw)n(a)n(ys)d(returns)h +(the)h(empt)n(y)h(set.)f(Hence)g(there)g(is)g(no)365 +1986 y(transition)26 b(out)h(of)g(an)n(y)f(state,)h(in)g(particular)e +(not)i(out)g(of)33 b Fl([])p Fx(.)26 b(Th)n(us)g(the)i(only)e(reac)n +(hable)365 2085 y(state)20 b(is)g Fl([])p Fx(.)f(There)h(is)g(no)g +(\014nal)f(state)h(b)r(ecause)g(the)g(last)g(comp)r(onen)n(t)g(\()p +Fq(\014n)o Fx(\))h(alw)n(a)n(ys)d(returns)365 2185 y +Fq(F)n(alse)p Fx(.)27 b(Hence)h(the)g(automaton)f(accepts)g(no)g(w)n +(ord,)g(as)g(required)f(b)n(y)i Fq(Empt)n(y)o Fx(.)490 +2287 y(The)f(de\014nition)h(of)g Fq(atom)f Fx(is)h(analogous.)490 +2388 y(W)-7 b(e)24 b(could)f(no)n(w)g(go)g(through)g(the)h(remaining)f +(constructions)g(one)g(b)n(y)g(one,)h(but)g(it)g(will)365 +2488 y(su\016ce)k(to)f(examine)g Fq(conc)g Fx(in)h(detail:)506 +2608 y Fj(conc)40 b Fv(::)g Fi(\013)f Fv(bitsNAe)i Fh(\))e +Fi(\013)h Fv(bitsNAe)g Fh(\))f Fi(\013)h Fv(bitsNAe)506 +2699 y Fj(conc)g Fh(\021)f Fi(\025)p Fv(\(ql,dl,fl\)\(qr,dr,fr\).)624 +2791 y(\()p Fj(T)-6 b(rue)p Fv(#ql,)663 2882 y Fi(\025)p +Fv(a)40 b(s.)f(case)h(s)g(of)977 2973 y([])g Fh(\))f +Fv({})899 3065 y(|)g(left#s)i Fh(\))e Fv(if)g(left)i(then)f(\()p +Fj(T)-6 b(rue)39 b Fv(##)h(dl)g(a)f(s\))h Fh([)1879 3156 +y Fv(\(if)g(fl)g(s)f Fh(^)h Fv(a=)p Fj(None)g Fv(then)g({)p +Fj(F)n(alse)p Fv(#qr})2585 3247 y(else)h({}\))1683 3339 +y(else)f Fj(F)n(alse)f Fv(##)h(dr)g(a)f(s,)663 3430 y +Fi(\025)p Fv(s.)h(case)g(s)f(of)h([])g Fh(\))f Fj(F)n(alse)g +Fv(|)g(left#s)i Fh(\))e(:)p Fv(left)h Fh(^)g Fv(fr)f(s\))365 +3563 y Fx(The)d(idea)e(is)i(to)f(pre\014x)f(states)h(of)g(the)h(left)g +(automaton)e(\(let)i(us)f(call)g(it)h Fp(L)p Fx(\))f(with)g +Fq(T)-7 b(rue)365 3662 y Fx(and)30 b(states)f(of)h(the)h(righ)n(t)e +(automaton)g(\(let)h(us)g(call)f(it)i Fp(R)q Fx(\))f(with)g +Fq(F)n(alse)p Fx(.)g(Hence)g(the)g(start)365 3762 y(state)k(of)g(the)g +(concatenation)f(is)h Fq(T)-7 b(rue)p Fl(#ql)p Fx(,)33 +b(where)g Fl(ql)h Fx(is)g(the)g(start)f(state)h(of)g +Fp(L)p Fx(.)g(There)365 3862 y(are)29 b(no)f(transitions)h(out)g(of)g +(the)h(\(unreac)n(hable\))e(state)h Fl([])p Fx(.)g(T)-7 +b(o)29 b(describ)r(e)g(the)g(remaining)365 3961 y(transitions)c(w)n(e)h +(ha)n(v)n(e)f(in)n(tro)r(duced)g(an)h(abbreviation:)f +Fl(##)g Fx(is)h Fl(#)g Fx(lifted)h(to)e(sets)h(of)g(lists,)g(i.e.)365 +4061 y Fl(x##XS)g Fx(stands)h(for)g Fl(\()p Fp(\025)p +Fl(xs.)43 b(x#xs\))e(``)i(XS)p Fx(.)490 4162 y(T)-7 b(ransitions)32 +b(out)h(of)h(a)f(state)g Fl(left#s)e Fx(dep)r(end)j(on)f +Fl(left)p Fx(.)f(If)40 b Fl(left)32 b Fx(is)h Fq(T)-7 +b(rue)p Fx(,)33 b(i.e.)h(w)n(e)365 4262 y(are)29 b(in)h +Fp(L)p Fx(,)f(w)n(e)g(tak)n(e)g(the)h(transitions)f(of)h +Fp(L)f Fx(out)g(of)37 b Fl(s)29 b Fx(together)g(with)h(an)f +Fp(")p Fx(-transition)f(to)365 4362 y Fl(False#qr)p Fx(,)21 +b(where)j Fl(qr)f Fx(is)h(the)g(start)g(state)g(of)g +Fp(R)q Fx(,)g(in)g(case)f Fl(s)h Fx(is)g(a)f(\014nal)h(state)g(of)g +Fp(R)q Fx(.)g(If)31 b Fl(left)365 4461 y Fx(is)f Fq(F)n(alse)o +Fx(,)h(w)n(e)e(simply)h(tak)n(e)f(the)h(transitions)f(of)h +Fp(R)q Fx(.)g(The)g(op)r(eration)f Fl(##)g Fx(lifts)h(states)g(of)g +Fp(L)365 4561 y Fx(and)e Fp(R)g Fx(to)g(states)f(of)g(their)h +(concatenation.)e(The)i(\014nal)f(states)h(are)e(those)h(of)h +Fp(R)q Fx(.)490 4662 y(The)f(de\014nitions)h(of)g Fq(union)e +Fx(and)i Fq(sta)n(r)f Fx(are)g(analogous.)490 4764 y(If)j(the)g(reader) +e(\014nds)i(the)g(ab)r(o)n(v)n(e)e(treatmen)n(t)h(in)h(terms)g(of)f +(bit)h(lists)g(rev)n(oltingly)e(con-)365 4863 y(crete,)g(I)f(cannot)g +(disagree.)f(A)i(more)f(abstract)g(approac)n(h)e(is)j(clearly)e +(desirable.)1785 5112 y(7)p eop +%%Page: 8 8 +8 7 bop 681 387 a Fo(4.1)94 b(The)32 b(pro)s(of)681 546 +y Fx(The)27 b(pro)r(of)g(plan)h(in)g(the)g(large)e(is)h(easy:)g(sho)n +(w)1370 709 y Fq(accepts)43 b Fl(\()p Fq(rexp2nae)g Fl(r\))f(w)i(=)f +(\(w)g Fr(2)h Fq(lang)e Fl(r\))583 b Fx(\(2\))681 872 +y(b)n(y)27 b(induction)h(on)f Fl(r)h Fx(using)f(the)h(ob)n(vious)e +(lemmas)822 1015 y Fj(accepts)39 b Fv(\()p Fj(atom)h +Fv(a\))132 b(w)40 b(=)f(\(w)h(=)f([a]\))822 1106 y Fj(accepts)g +Fv(\()p Fj(union)f Fv(L)i(R\))g(w)f(=)h(\()p Fj(accepts)f +Fv(L)h(w)f Fh(_)g Fj(accepts)h Fv(R)f(w\))822 1198 y +Fj(accepts)g Fv(\()p Fj(conc)h Fv(L)g(R\))70 b(w)40 b(=)f(\()p +Fh(9)g Fv(u)h(v.)f(w)h(=)f(u@v)h Fh(^)g Fj(accepts)f +Fv(L)g(u)h Fh(^)f Fj(accepts)h Fv(R)f(v\))822 1289 y +Fj(accepts)g Fv(\()p Fj(sta)n(r)h Fv(A\))174 b(w)39 b(=)900 +1380 y(\()p Fh(9)g Fv(us.)h(\()p Fh(8)g Fv(u)f Fh(2)g +Fj(set)h Fv(us.)g Fj(accepts)f Fv(A)h(u\))f Fh(^)h Fv(\(w)f(=)h +Fj(concat)f Fv(us\)\))681 1519 y Fx(The)d(realization)g(of)g(this)h +(plan)g(is,)f(unfortunately)-7 b(,)37 b(a)f(textb)r(o)r(ok)h(example)f +(of)h(the)g(gap)681 1619 y(b)r(et)n(w)n(een)25 b(graphical)f(in)n +(tuition)j(and)e(formal)g(pro)r(of.)g(All)h(of)g(the)g(lemmas)f(app)r +(ear)g(ob)n(vious)681 1719 y(giv)n(en)j(a)h(picture)h(of)f(the)h(comp)r +(osition)f(of)g(automata)g(suc)n(h)g(as)f(Fig.)d(2.)k(Y)-7 +b(et)30 b(their)g(pro)r(ofs)681 1818 y(require)37 b(a)g(painful)h +(amoun)n(t)g(of)f(detail.)h(F)-7 b(or)37 b(y)n(our)g(am)n(usemen)n(t,)g +(the)i(lemmas)e(for)g(the)681 1918 y Fq(conc)o Fx(-case)26 +b(are)h(sho)n(wn)g(in)h(Fig.)c(3.)822 2226 y Fd(\014n)31 +b Fc(\()p Fd(conc)g Fc(L)g(R\))g(\()p Fd(T)-5 b(rue)p +Fc(#p\))30 b(=)h Fd(F)n(alse)822 2296 y(\014n)g Fc(\()p +Fd(conc)g Fc(L)g(R\))g(\()p Fd(F)n(alse)q Fc(#p\))f(=)h +Fd(\014n)g Fc(R)f(p)822 2365 y(\()p Fd(T)-5 b(rue)p Fc(#p,q\))30 +b Fb(2)h Fd(step)g Fc(\()p Fd(conc)h Fc(L)e(R\))h(a)g(=)884 +2435 y(\(\()p Fb(9)f Fc(r.)h(q=)p Fd(T)-5 b(rue)p Fc(#r)30 +b Fb(^)h Fc(\(p,r\))f Fb(2)h Fd(step)g Fc(L)g(a\))f Fb(_)h +Fc(\()p Fd(\014n)g Fc(L)f(p)h Fb(^)g Fc(a=)p Fd(None)f +Fb(^)h Fc(q=)p Fd(F)n(alse)q Fc(#)p Fd(sta)n(rt)g Fc(R\)\))822 +2505 y(\()p Fd(F)n(alse)q Fc(#p,q\))f Fb(2)h Fd(step)g +Fc(\()p Fd(conc)g Fc(L)g(R\))g(a)f(=)h(\()p Fb(9)g Fc(r.)f(q)h(=)g +Fd(F)n(alse)q Fc(#r)f Fb(^)h Fc(\(p,r\))f Fb(2)h Fd(step)g +Fc(R)g(a\))822 2575 y(\()p Fd(F)n(alse)q Fc(#p,fq\))f +Fb(2)h Fc(\()p Fd(eps)p Fc(\()p Fd(conc)g Fc(L)g(R\)\)^*)f +Fn(=)-11 b Fb(\))31 b(9)f Fc(q.)h(\(p,q\))f Fb(2)h Fc(\()p +Fd(eps)f Fc(R\)^*)h Fb(^)f Fc(fq)h(=)g Fd(F)n(alse)q +Fc(#q)822 2644 y(\(p,q\))f Fb(2)h Fc(\()p Fd(eps)g Fc(R\)^*)f +Fn(=)-11 b Fb(\))31 b Fc(\()p Fd(F)n(alse)q Fc(#p,)f +Fd(F)n(alse)q Fc(#q\))h Fb(2)f Fc(\()p Fd(eps)p Fc(\()p +Fd(conc)i Fc(L)e(R\)\)^*)822 2714 y(\()p Fd(F)n(alse)q +Fc(#p,fq\))g Fb(2)h Fc(\()p Fd(eps)p Fc(\()p Fd(conc)g +Fc(L)g(R\)\)^*)f(=)h(\()p Fb(9)f Fc(q.)h(fq)f(=)h Fd(F)n(alse)q +Fc(#q)g Fb(^)f Fc(\(p,q\))h Fb(2)f Fc(\()p Fd(eps)h Fc(R\)^*\))822 +2784 y(\()p Fd(F)n(alse)q Fc(#p,fq\))f Fb(2)h Fd(steps)f +Fc(\()p Fd(conc)i Fc(L)f(R\))f(w)h(=)g(\()p Fb(9)f Fc(q.)h(fq)f(=)h +Fd(F)n(alse)q Fc(#q)g Fb(^)f Fc(\(p,q\))p Fb(2)g Fd(steps)h +Fc(R)g(w\))822 2854 y(\(p,q\))f Fb(2)h Fc(\()p Fd(eps)g +Fc(L\)^*)f Fn(=)-11 b Fb(\))31 b Fc(\()p Fd(T)-5 b(rue)p +Fc(#p,)p Fd(T)g(rue)p Fc(#q\))30 b Fb(2)h Fc(\()p Fd(eps)p +Fc(\()p Fd(conc)g Fc(L)g(R\)\)^*)822 2923 y(\(p,q\))f +Fb(2)h Fd(steps)g Fc(L)f(w)h Fn(=)-11 b Fb(\))31 b Fc(\()p +Fd(T)-5 b(rue)p Fc(#p,)p Fd(T)g(rue)p Fc(#q\))31 b Fb(2)f +Fd(steps)h Fc(\()p Fd(conc)h Fc(L)e(R\))h(w)822 2993 +y(\()p Fd(T)-5 b(rue)p Fc(#p,tq\))30 b Fb(2)h Fc(\()p +Fd(eps)p Fc(\()p Fd(conc)g Fc(L)g(R\)\)^*)f Fn(=)-11 +b Fb(\))884 3063 y Fc(\()p Fb(9)30 b Fc(q.)h(tq)f(=)h +Fd(T)-5 b(rue)p Fc(#q)31 b Fb(^)g Fc(\(p,q\))f Fb(2)h +Fc(\()p Fd(eps)f Fc(L\)^*\))h Fb(_)884 3133 y Fc(\()p +Fb(9)f Fc(q)h(r.)f(tq)h(=)g Fd(F)n(alse)q Fc(#q)f Fb(^)h +Fc(\(p,r\))p Fb(2)p Fc(\()p Fd(eps)f Fc(L\)^*)g Fb(^)h +Fd(\014n)g Fc(L)g(r)f Fb(^)h Fc(\()p Fd(sta)n(rt)g Fc(R,q\))f +Fb(2)h Fc(\()p Fd(eps)g Fc(R\)^*\))822 3202 y(\(p,q\))f +Fb(2)h Fc(\()p Fd(eps)g Fc(L\)^*)f Fn(=)-11 b Fb(\))31 +b Fc(\()p Fd(T)-5 b(rue)p Fc(#p,)p Fd(T)g(rue)p Fc(#q\))30 +b Fb(2)h Fc(\()p Fd(eps)p Fc(\()p Fd(conc)g Fc(L)g(R\)\)^*)822 +3272 y(\(p,q\))f Fb(2)h Fd(step)g Fc(R)g Fd(None)f Fn(=)-11 +b Fb(\))31 b Fc(\()p Fd(F)n(alse)q Fc(#p,)p Fd(F)n(alse)q +Fc(#q\))f Fb(2)h Fd(step)g Fc(\()p Fd(conc)g Fc(L)g(R\))g +Fd(None)822 3342 y Fc(\(p,q\))f Fb(2)h Fc(\()p Fd(eps)g +Fc(R\)^*)f Fn(=)-11 b Fb(\))31 b Fc(\()p Fd(F)n(alse)q +Fc(#p,)p Fd(F)n(alse)p Fc(#q\))g Fb(2)f Fc(\()p Fd(eps)p +Fc(\()p Fd(conc)i Fc(L)e(R\)\)^*)822 3412 y Fd(\014n)h +Fc(L)g(p)f Fn(=)-11 b Fb(\))31 b Fc(\()p Fd(T)-5 b(rue)p +Fc(#p,)p Fd(F)n(alse)q Fc(#)p Fd(sta)n(rt)31 b Fc(R\))g +Fb(2)f Fd(eps)p Fc(\()p Fd(conc)i Fc(L)e(R\))822 3481 +y(\(\()p Fd(T)-5 b(rue)p Fc(#p,q\))30 b Fb(2)h Fc(\()p +Fd(eps)p Fc(\()p Fd(conc)g Fc(L)g(R\)\)^*\))f(=)884 3551 +y(\(\()p Fb(9)g Fc(r.)h(\(p,r\))f Fb(2)g Fc(\()p Fd(eps)h +Fc(L\)^*)f Fb(^)h Fc(q)g(=)g Fd(T)-5 b(rue)p Fc(#r\))31 +b Fb(_)915 3621 y Fc(\()p Fb(9)f Fc(r.)h(\(p,r\))f Fb(2)g +Fc(\()p Fd(eps)h Fc(L\)^*)f Fb(^)h Fd(\014n)g Fc(L)g(r)f +Fb(^)1100 3691 y Fc(\()p Fb(9)g Fc(s.)h(\()p Fd(sta)n(rt)g +Fc(R,)f(s\))h Fb(2)g Fc(\()p Fd(eps)f Fc(R\)^*)h Fb(^)f +Fc(q)h(=)g Fd(F)n(alse)q Fc(#s\)\)\))822 3760 y(\()p +Fd(T)-5 b(rue)p Fc(#p,q\))30 b Fb(2)h Fd(steps)g Fc(\()p +Fd(conc)g Fc(L)g(R\))g(w)f Fn(=)-11 b Fb(\))884 3830 +y Fc(\(\()p Fb(9)30 b Fc(r.)h(\(p,r\))f Fb(2)g Fd(steps)h +Fc(L)g(w)g Fb(^)f Fc(q)h(=)g Fd(T)-5 b(rue)p Fc(#r\))62 +b Fb(_)915 3900 y Fc(\()p Fb(9)30 b Fc(u)h(v.)f(w)h(=)g(u@v)f +Fb(^)h Fc(\()p Fb(9)f Fc(r.)h(\(p,r\))f Fb(2)h Fd(steps)g +Fc(L)f(u)h Fb(^)g Fd(\014n)f Fc(L)h(r)g Fb(^)1162 3969 +y Fc(\()p Fb(9)f Fc(s.)g(\()p Fd(sta)n(rt)i Fc(R,s\))e +Fb(2)h Fd(steps)f Fc(R)h(v)g Fb(^)f Fc(q)h(=)g Fd(F)n(alse)q +Fc(#s\)\)\)\))1468 4182 y Fu(Fig.)15 b(3.)25 b Fw(Lemmas)f(for)j +(correctness)g(of)f Fj(conc)805 4465 y Fx(If)35 b(y)n(ou)f(examine)h +(the)g(lemmas)f(in)h(Fig.)25 b(3)34 b(carefully)-7 b(,)34 +b(y)n(ou)g(will)h(\014nd)g(that)g(eac)n(h)f(one)681 4565 +y(is)g(v)n(ery)f(reasonable,)g(i.e.)h(none)h(of)f(them)h(is)f(con)n +(triv)n(ed)g(to)g(\014t)h(the)g(needs)f(of)g(the)h(theo-)681 +4664 y(rem)25 b(pro)n(v)n(er.)e(Apart)i(from)f(the)i(last)f(t)n(w)n(o,) +f(whic)n(h)h(require)f(10)g(and)h(24)f(steps)h(resp)r(ectiv)n(ely)-7 +b(,)681 4764 y(all)39 b(of)g(them)g(are)f(pro)n(v)n(ed)g(in)h(3)g(or)f +(4)h(steps:)g(induction)g(plus)g(\(automatic\))g(predicate)681 +4863 y(calculus)30 b(reasoning)g(and)h(a)f(bit)i(of)f +(simpli\014cation.)g(Ho)n(w)n(ev)n(er,)f(b)r(ecause)g(of)h(the)h(form)f +(of)2101 5112 y(8)p eop +%%Page: 9 9 +9 8 bop 365 387 a Fx(the)33 b(lemmas,)f(predicate)g(calculus)g +(reasoning)f(dominates.)h(F)-7 b(ortunately)g(,)32 b(Isab)r(elle)g(no)n +(w)365 487 y(pro)n(vides)f(the)i(righ)n(t)f(kind)g(of)h(automation)24 +b([10)o(],)32 b(whereas)f(the)i(previous)e(generation)g(of)365 +587 y(Isab)r(elle's)h(predicate)f(calculus)h(reasoning)e(to)r(ols)24 +b([9])32 b(\015oundered)g(on)f(some)h(of)g(the)g(lem-)365 +686 y(mas.)24 b(Unfortunately)-7 b(,)24 b(predicate)g(calculus)g +(reasoning)e(is)i(inheren)n(tly)g(less)g(pleasan)n(t)f(than)365 +786 y(simpli\014cation)29 b(b)r(ecause)g(a)g(failed)g(attempt)h(of)f +(an)g(automatic)g(pro)r(cedure)f(yields)h(no)g(in-)365 +886 y(formation)g(on)g(what)g(is)g(missing.)g(Hence)g(y)n(ou)g(ha)n(v)n +(e)f(to)h(start)g(y)n(our)f(o)n(wn)g(man)n(ual)h(single)365 +985 y(step)j(pro)r(of)e(to)h(disco)n(v)n(er)e(where)i(things)g(go)f +(wrong,)g(whic)n(h)h(is)g(ho)n(w)g(w)n(e)f(found)i(the)f(lem-)365 +1085 y(mas)26 b(in)h(Fig.)e(3.)h(This)h(is)f(in)h(con)n(trast)e(to)h +(simpli\014cation,)h(where)f(a)g(failed)h(pro)r(of)f(attempt)365 +1184 y(results)e(in)h(a)f(new)h(goal)e(that,)i(in)g(man)n(y)f(cases,)f +(is)i(a)f(strong)f(clue)i(as)f(to)g(what)h(the)g(missing)365 +1284 y(lemma)33 b(is.)g(Hence)h(the)f(design)g(decision)g(for)f(a)h +(relational)f(treatmen)n(t)h(as)f(discussed)h(in)365 +1384 y Fr(x)p Fx(2.3)27 b(also)f(has)i(its)f(dra)n(wbac)n(ks.)f(F)-7 +b(or)27 b(example,)g(in)h(a)f(functional)h(st)n(yle,)f(the)h(lemma)506 +1526 y Fv(\()p Fj(F)n(alse)p Fv(#p,fq\))41 b Fh(2)e Fj(steps)h +Fv(\()p Fj(conc)g Fv(L)f(R\))h(w)f(=)585 1618 y(\()p +Fh(9)g Fv(q.)h(fq)f(=)h Fj(F)n(alse)o Fv(#q)g Fh(^)g +Fv(\(p,q\))g Fh(2)f Fj(steps)h Fv(R)f(w\))365 1773 y +Fx(b)r(ecomes)506 1900 y Fj(delta)f Fv(\()p Fj(conc)i +Fv(L)g(R\))f(a)h(\()p Fj(F)n(alse)f Fv(##)h(Q\))f(=)h +Fj(F)n(alse)f Fv(##)g Fj(delta)f Fv(R)i(a)f(Q)365 2050 +y Fx(Despite)34 b(these)g(di\016culties,)f(the)h(relational)e(approac)n +(h)g(app)r(ears)g(simpler.)h(Prop)r(onen)n(ts)365 2149 +y(of)g(relation)g(algebra)e(migh)n(t)i(p)r(oin)n(t)g(out)g(that)h(the)f +(reduction)g(to)g(predicate)g(calculus)f(is)365 2249 +y(resp)r(onsible)19 b(for)f(all)h(complications,)g(and)g(a)g(purely)g +(relation-algebraic)d(treatmen)n(t)j(w)n(ould)365 2348 +y(ha)n(v)n(e)27 b(b)r(een)h(m)n(uc)n(h)f(slic)n(k)n(er.)f(They)i(ma)n +(y)f(w)n(ell)g(b)r(e)h(righ)n(t.)490 2463 y(The)d(deriv)-5 +b(ation)25 b(of)g(the)h(lemmas)f(for)f Fq(union)h Fx(and)g +Fq(sta)n(r)g Fx(is)g(en)n(tirely)g(similar.)f(If)i(w)n(e)f(no)n(w)365 +2562 y(put)k(\(1\))e(and)h(\(2\))f(together,)g(w)n(e)g(obtain)h(the)g +(main)f(correctness)f(theorem:)506 2710 y Fv(DA.)p Fj(accepts)40 +b Fv(\()p Fj(nae2da)p Fv(\()p Fj(rexp2nae)g Fv(r\)\))g(w)g(=)f(\(w)h +Fh(2)f Fj(lang)g Fv(r\))365 3091 y Ft(5)112 b(The)38 +b(scanner)365 3363 y Fx(W)-7 b(e)32 b(will)f(no)n(w)g(turn)h +(deterministic)f(automata)f(in)n(to)h(scanners)f(as)h(describ)r(ed)g +(in)h(the)f(in-)365 3463 y(tro)r(duction.)d(It)f(is)h(easy)e(to)h(see)g +(that)h(the)g(concept)f(of)g(rep)r(eatedly)g(c)n(hopping)g(a)g(maximal) +365 3562 y(pre\014x)h(o\013)g(a)f(string)h(is)f(indep)r(enden)n(t)i(of) +f(automata)f(theory)g(and)h(can)f(b)r(e)i(parameterized)365 +3662 y(b)n(y)23 b(an)f(arbitrary)f(predicate)h(on)h(strings.)e(Th)n(us) +i(w)n(e)f(will)h(\014rst)g(do)f(a)h(bit)g(of)g(list)g(pro)r(cessing,) +365 3761 y(follo)n(w)n(ed)33 b(b)n(y)h(t)n(w)n(o)f(applications:)g(the) +i(scanner,)e(and,)g(as)h(an)f(afterthough)n(t,)h(paragraph)365 +3861 y(\014lling.)29 b(The)f(nice)h(thing)g(is)f(that)h(the)g(hard)f +(part)g(of)g(the)h(dev)n(elopmen)n(t,)f(including)g(most)365 +3961 y(of)g(the)g(pro)r(ofs,)f(is)g(con\014ned)h(to)f(the)h(generic)f +(list)g(pro)r(cessing)g(functions.)365 4283 y Fo(5.1)95 +b(Chopping)31 b(up)h(lists)365 4521 y Fx(W)-7 b(e)32 +b(start)f(b)n(y)h(sp)r(ecifying)f(the)h(requiremen)n(ts.)f(What)h(do)r +(es)f(it)h(mean)f(to)h(c)n(hop)f(a)g(list)h(up)365 4621 +y(in)n(to)c(maximal)f(pre\014xes?)g(The)g(pre\014x)g(ordering)f(on)i +(lists)f(is)h(de\014ned)g(as)f(usual:)506 4764 y Fv(xs)40 +b Fh(\024)f Fv(zs)79 b Fh(\021)f(9)39 b Fv(ys.)h(zs)g(=)f(xs@ys)1785 +5112 y Fx(9)p eop +%%Page: 10 10 +10 9 bop 681 387 a Fx(Note)39 b(the)g(o)n(v)n(erloading)e(of)i +Fr(\024)p Fx(.)g(Then)g(what)g(is)g(a)g(maximal)f(pre\014x)h(of)g(a)g +(list)g(w.r.t.)g(a)681 487 y(predicate?)27 b(The)h(answ)n(er)e(is)h +(almost)g(ob)n(vious)822 630 y Fj(is)p 875 630 24 4 v +27 w(maxp)n(ref)40 b Fv(P)g(xs)f(ys)h Fh(\021)822 721 +y Fv(xs)g Fh(\024)f Fv(ys)g Fh(^)h Fv(\(xs=[])g Fh(_)g +Fv(P)f(xs\))h Fh(^)f Fv(\()p Fh(8)h Fv(zs.)f(zs)h Fh(\024)f +Fv(ys)h Fh(^)f Fv(P)h(zs)f Fh(\000)-13 b(!)39 b Fv(zs)h +Fh(\024)f Fv(xs\))681 873 y Fx(except)23 b(that)h(w)n(e)f(also)g(allo)n +(w)g Fl([])g Fx(to)g(b)r(e)h(a)f(maximal)g(pre\014x)g(in)h(case)f +Fl(ys)f Fx(has)h(no)g(pre\014x)g(that)681 973 y(satis\014es)j +Fl(P)p Fx(.)h(This)g(de\014nition)g(mak)n(es)f(sense)h(in)g(our)f(con)n +(text)h(where)f(the)i(maximal)e(pre\014x)681 1072 y(should)f(nev)n(er)f +(b)r(e)i(empt)n(y)f(\(b)r(ecause)g(c)n(hopping)f(it)i(o\013)f(should)g +(reduce)g(the)g(list\).)h(Th)n(us)f(w)n(e)681 1172 y(can)i(use)g +Fl([])g Fx(as)g(an)h(indication)f(that)h(there)f(is)h(no)f(nonempt)n(y) +g(pre\014x)h(that)f(satis\014es)g Fl(P)p Fx(.)805 1282 +y(W)-7 b(e)33 b(no)n(w)f(come)g(to)h(the)g(main)f(sp)r(eci\014cation.)g +(The)h(class)e(of)i(functions)g(w)n(e)f(w)n(an)n(t)g(to)681 +1382 y(sp)r(ecify)c(are)e(of)i(t)n(yp)r(e)822 1518 y +Fi(\013)39 b Fv(chopper)80 b(=)f Fi(\013)40 b Fv(list)g +Fh(\))f Fi(\013)g Fv(list)h(list)h Fh(\002)e Fi(\013)g +Fv(list)681 1670 y Fx(The)27 b(sp)r(eci\014cation)h(is)f(a)g(predicate) +822 1813 y Fj(is)p 875 1813 V 27 w(maxchopp)r(er)40 b +Fv(::)g(\()p Fi(\013)f Fv(list)h Fh(\))f Fv(bool\))i +Fh(\))e Fi(\013)g Fv(chopper)i Fh(\))e Fv(bool)681 1965 +y Fx(that)33 b(expresses)e(when)j(its)f(second)f(argumen)n(t)g +(correctly)f(c)n(hops)h(up)i(lists)f(according)e(to)681 +2064 y(its)d(\014rst)f(argumen)n(t:)822 2207 y Fj(is)p +875 2207 V 27 w(maxchopp)r(er)40 b Fv(P)f(chopper)i Fh(\021)822 +2298 y(8)e Fv(xs)g(zs)h(yss.)979 2390 y(\(chopper\(xs\))i(=)d +(\(yss,zs\)\))j(=)979 2481 y(\(xs)e(=)f Fj(concat)g Fv(yss)h(@)g(zs)f +Fh(^)h Fv(\()p Fh(8)f Fv(ys)h Fh(2)f Fj(set)h Fv(yss.)g(ys)f +Fh(6)p Fw(=)g Fv([]\))h Fh(^)979 2572 y Fv(\(case)g(yss)g(of)1097 +2664 y([])f Fh(\))g Fj(is)p 1383 2664 V 28 w(maxp)n(ref)h +Fv(P)f([])h(xs)1018 2755 y(|)g(us#uss)g Fh(\))f Fj(is)p +1540 2755 V 28 w(maxp)n(ref)g Fv(P)h(us)g(xs)f Fh(^)1489 +2846 y Fv(chopper\()p Fj(concat)r Fv(\(uss\)@zs\))i(=)e(\(uss,zs\)\)\)) +681 2998 y Fx(Let's)27 b(recast)g(this)h(in)n(to)f(w)n(ords:)f +Fl(chopper\(xs\))e Fx(returns)i Fl(\(yss,zs\))f Fx(i\013)716 +3207 y(1.)41 b(the)28 b(concatenation)e(of)i(the)g(outputs)g(yields)f +(the)h(input,)716 3318 y(2.)41 b(all)27 b(elemen)n(ts)h(of)34 +b Fl(yss)26 b Fx(are)h(nonempt)n(y)-7 b(,)27 b(and)716 +3428 y(3.)41 b(if)34 b Fl(yss)26 b Fx(is)i(empt)n(y)-7 +b(,)27 b(then)h(there)f(is)g(no)g(nonempt)n(y)h(pre\014x)e(of)34 +b Fl(xs)27 b Fx(that)g(satis\014es)g Fl(P)p Fx(,)g(and)822 +3528 y(if)33 b Fl(yss)43 b(=)g(us#uss)p Fx(,)24 b(then)j +Fl(us)f Fx(is)g(the)h(maximal)f(pre\014x)h(of)32 b Fl(xs)26 +b Fx(w.r.t.)h Fl(P)f Fx(and)g(c)n(hopping)822 3627 y(up)i(the)g +(remaining)e(list)i(yields)g Fl(\(uss,zs\))p Fx(.)681 +3825 y(Note)38 b(that)h(instead)f(of)h(an)f(unjusti\014ed)h(axiom)f(sp) +r(ecifying)g(a)g(constan)n(t)g Fq(chopp)r(er)p Fx(,)g(the)681 +3925 y(predicate)27 b Fq(is)p 1098 3925 25 4 v 29 w(maxchopp)r(er)h +Fx(is)f(merely)g(an)h(abbreviation.)805 4035 y(Note)39 +b(also)e(that)h(although)g(the)g(sp)r(eci\014cation)g(only)g(sa)n(ys)f +(that)h(the)h(\014rst)f(elemen)n(t)681 4135 y Fl(us)26 +b Fx(of)33 b Fl(yss)25 b Fx(m)n(ust)i(b)r(e)g(a)g(maximal)f(pre\014x,)g +(the)h(remaining)f(elemen)n(ts)g(are)g(co)n(v)n(ered)f(b)n(y)h(the)681 +4235 y(\\recursiv)n(e")18 b(call)j(of)27 b Fl(chopper)18 +b Fx(in)k(the)f(\014nal)g(line.)g(A)g(direct)g(sp)r(eci\014cation)g(of) +g(the)g(maximal)681 4334 y(pre\014x)j(prop)r(ert)n(y)f(for)h(all)h +(elemen)n(ts)f(of)31 b Fl(yss)24 b Fx(is)g(more)g(in)n(v)n(olv)n(ed)f +(b)r(ecause)h(the)h(list)g(of)g(whic)n(h)681 4434 y(they)j(are)e(a)h +(pre\014x)h(is)f(not)h(directly)f(at)g(hand.)805 4544 +y(No)n(w)g(that)h(w)n(e)g(ha)n(v)n(e)e(the)i(main)f(sp)r +(eci\014cation,)h(let)g(us)f(lo)r(ok)g(at)h(an)f(implemen)n(tation:)716 +4753 y(1.)41 b(function)28 b Fq(maxsplit)f Fx(splits)h(a)f(list)h(in)n +(to)f(a)h(maximal)f(pre\014x)g(and)g(the)h(remaining)f(list;)716 +4863 y(2.)41 b(function)28 b Fq(chop)f Fx(iterates)g(the)h(pro)r(cess)e +(of)i(splitting)g(o\013)f(a)h(pre\014x.)2080 5112 y(10)p +eop +%%Page: 11 11 +11 10 bop 365 387 a Fx(T)-7 b(o)28 b(mak)n(e)e(things)i(more)f(mo)r +(dular,)g(w)n(e)g(in)n(tro)r(duce)g(the)h(t)n(yp)r(e)506 +524 y Fi(\013)40 b Fv(splitter)80 b(=)f Fi(\013)39 b +Fv(list)i Fh(\))e Fi(\013)g Fv(list)h Fh(\002)f Fi(\013)h +Fv(list)365 686 y Fx(and)28 b(a)f(separate)f(sp)r(eci\014cation)506 +829 y Fj(is)p 559 829 24 4 v 28 w(maxsplitter)38 b Fv(::)i(\()p +Fi(\013)f Fv(list)i Fh(\))e Fv(bool\))h Fh(\))f Fi(\013)g +Fv(splitter)i Fh(\))f Fv(bool)506 920 y Fj(is)p 559 920 +V 28 w(maxsplitter)e Fv(P)h(splitf)i Fh(\021)506 1011 +y Fv(\()p Fh(8)f Fv(xs)f(ps)h(qs.)g(\(splitf)h(xs)e(=)h(\(ps,qs\)\))h +(=)e(\(xs=ps@qs)j Fh(^)d Fj(is)p 2497 1011 V 27 w(maxp)n(ref)h +Fv(P)g(ps)f(xs\)\))365 1174 y Fx(that)28 b Fq(maxsplit)f +Fx(should)h(satisfy)-7 b(.)27 b(The)h(de\014nition)g(of)506 +1316 y Fj(maxsplit)38 b Fv(::)i(\()p Fi(\013)g Fv(list)g +Fh(\))f Fv(bool\))h Fh(\))f Fi(\013)h Fv(list)g Fh(\002)f +Fi(\013)h Fv(list)g Fh(\))f Fi(\013)g Fv(list)977 1408 +y Fh(\))g Fi(\013)h Fv(splitter)506 1499 y Fj(maxsplit)e +Fv(P)i(r)f(ps)h([])197 b(=)39 b(\(if)h(P)f(ps)h(then)g(\(ps,[]\))h +(else)f(r\))506 1590 y Fj(maxsplit)e Fv(P)i(r)f(ps)h(\(q#qs\))h(=)e +Fj(maxsplit)f Fv(P)i(\(if)f(P)h(ps)g(then)g(\(ps,q#qs\))h(else)f(r\)) +1722 1682 y(\(ps@[q]\))i(qs)365 1844 y Fx(is)33 b(fairly)g(easy:)f +Fl(r)h Fx(is)g(the)g(maximal)g(result)g(found)g(so)g(far,)f +Fl(ps)h Fx(the)g(pre\014x)g(accum)n(ulated)365 1943 y(since)39 +b(the)h(initial)f(call,)g(and)g Fl(qs)f Fx(is)h(the)h(su\016x)f(that)g +(remains)f(to)h(b)r(e)h(examined;)f Fl(r)f Fx(is)365 +2043 y(up)r(dated)28 b(ev)n(ery)f(time)h(a)f(longer)f(pre\014x)i(that)f +(satis\014es)g Fl(P)g Fx(is)h(found.)490 2164 y(Once)f(y)n(ou)g(come)g +(up)h(with)g(and)f(pro)n(v)n(e)f(\(b)n(y)i(induction)g(on)f +Fl(qs)p Fx(\))g(the)h(lemma)506 2311 y Fv(\()p Fj(maxsplit)39 +b Fv(P)g(r)h(ps)f(qs)h(=)f(\(xs,ys\)\))i(=)506 2402 y(\(if)f +Fh(9)f Fv(us.)h(us)g Fh(\024)f Fv(qs)g Fh(^)h Fv(P\(ps@us\))546 +2494 y(then)g(xs@ys=ps@qs)i Fh(^)d Fj(is)p 1356 2494 +V 27 w(maxp)n(ref)h Fv(P)g(xs)f(\(ps@qs\))i(else)f(\(xs,ys\)=r\))365 +2656 y Fx(it)28 b(follo)n(ws)f(easily)g(that)h Fq(maxsplit)o +Fx(,)g(suitably)f(initialized,)h(meets)g(its)g(sp)r(eci\014cation:)506 +2798 y Fj(is)p 559 2798 V 28 w(maxsplitter)38 b Fv(P)h(\()p +Fi(\025)h Fv(xs.)g Fj(maxsplit)e Fv(P)h(\([],xs\))i([])f(xs\))490 +2959 y Fx(Note)29 b(that)g Fq(maxsplit)g Fx(tra)n(v)n(erses)d(the)k +(whole)f(list.)g(Iterating)f Fq(maxsplit)h Fx(ma)n(y)f(therefore)365 +3058 y(lead)k(to)g(quadratic)f(run)h(times.)h(This)f(problem)f(could)h +(b)r(e)h(o)n(v)n(ercome)d(if)i(there)g(w)n(ere)g(an)365 +3158 y(additional)26 b(test)g(whether)g Fl(ps)g Fx(can)f(at)h(all)g(b)r +(e)h(extended)f(to)g(a)g(list)g(satisfying)g Fl(P)p Fx(.)g(In)h(terms) +365 3257 y(of)33 b(automata)e(theory)-7 b(,)32 b(this)g(corresp)r(onds) +f(to)h(a)g(test)h(whether)f(the)h(curren)n(t)e(state)h(is)h(an)365 +3357 y(`error')26 b(state)h(whic)n(h)h(do)r(es)f(not)h(lead)f(to)h(an)n +(y)e(\014nal)i(state.)490 3478 y(W)-7 b(e)32 b(no)n(w)f(come)h(to)g +(our)f(main)g(function)i Fq(chop)e Fx(that)h(turns)g(splitters)g(in)n +(to)f(c)n(hopp)r(ers)365 3577 y(b)n(y)d(iterating)f(them:)506 +3720 y Fj(chop)40 b Fv(::)f Fi(\013)h Fv(splitter)h Fh(\))e +Fi(\013)g Fv(chopper)506 3811 y Fj(reducing)g Fv(splitf)h +Fw(=)-13 b Fh(\))585 3903 y Fj(chop)39 b Fv(splitf)i(xs)e(=)h(\(let)g +(\(pre,post\))h(=)f(splitf)g(xs)1291 3994 y(in)g(if)f(pre=[])i(then)f +(\([],xs\))1409 4085 y(else)g(let)g(\(xss,zs\))h(=)e +Fj(chop)g Fv(splitf)i(post)1605 4177 y(in)e(\(pre#xss,zs\)\))365 +4339 y Fx(Note)31 b(that)h(this)f(a)g(direct)g(consequence)f(of)h(the)g +(actual)g(de\014nition)g(b)n(y)g(w)n(ellfounded)g(re-)365 +4438 y(cursion,)c(whic)n(h)h(is)f(not)h(sho)n(wn.)f(The)g(precondition) +g(in)n(v)n(olving)506 4581 y Fj(reducing)39 b Fv(::)h +Fi(\013)f Fv(splitter)i Fh(\))e Fv(bool)506 4672 y Fj(reducing)g +Fv(splitf)h Fh(\021)506 4764 y(8)f Fv(xs)h(ys)g(zs.)g(splitf)g(xs)g(=)f +(\(ys,zs\))i Fh(^)f Fv(ys)f Fh(6)p Fw(=)g Fv([])h Fh(\000)-13 +b(!)39 b Fj(length)f Fv(zs)i(<)f Fj(length)f Fv(xs)1765 +5112 y Fx(11)p eop +%%Page: 12 12 +12 11 bop 681 387 a Fx(is)32 b(necessary)f(to)h(guaran)n(tee)f +(termination)h(of)g Fq(chop)o Fx(.)h(With)g(the)g(help)g(of)f(a)g(few)h +(lemmas)681 487 y(\(pro)n(v)n(ed)26 b(b)n(y)h(induction)h(on)g(the)g +(length)f(of)h(a)f(list\))h(one)f(can)h(establish)822 +634 y Fj(is)p 875 634 24 4 v 27 w(maxsplitter)38 b Fv(P)i(splitf)h +Fw(=)-13 b Fh(\))38 b Fj(is)p 1860 634 V 28 w(maxchopp)r(er)h +Fv(P)h(\()p Fj(chop)f Fv(splitf\))681 904 y Fo(5.2)94 +b(Scanning)681 1049 y Fx(No)n(w)34 b(w)n(e)g(sp)r(ecialize)g(the)h(ab)r +(o)n(v)n(e)e(generic)g(functions)i(to)f(p)r(erform)g(scanning,)g(i.e.)h +(c)n(hop-)681 1148 y(ping)27 b(up)g(strings)g(based)f(on)h(the)h +(acceptance)e(b)n(y)h(a)f(deterministic)i(automaton.)e(A)i(na)-9 +b(\177)-32 b(\020v)n(e)681 1248 y(solution)30 b(is)g(to)h(call)f +Fq(maxsplit)g Fx(with)h(the)g(predicate)f Fl(\()p Fq(accepts)42 +b Fl(A\))p Fx(.)30 b(But)h(since)f Fq(accepts)g Fx(is)681 +1347 y(applied)d(to)h(longer)e(and)i(longer)e(pre\014xes,)h(this)h +(leads)f(to)g(quadratic)g(run)g(times.)805 1447 y(Th)n(us)36 +b(w)n(e)f(need)h(to)g(re-implemen)n(t)f Fq(maxsplit)p +Fx(,)h(replacing)e(the)i(predicate)g(b)n(y)f(an)h(ac-)681 +1547 y(cepting)29 b Fl(da)d Fx(together)h(with)h(its)g(curren)n(t)f +(state:)822 1689 y Fj(auto)p 970 1689 V 27 w(split)38 +b Fv(::)i(\()p Fi(\013)p Fv(,)p Fi(\033)s Fv(\)da)g Fh(\))f +Fi(\033)81 b Fh(\))39 b Fi(\013)g Fv(list)i Fh(\002)e +Fi(\013)g Fv(list)h Fh(\))f Fi(\013)h Fv(list)1371 1781 +y Fh(\))f Fi(\013)h Fv(splitter)822 1872 y Fj(auto)p +970 1872 V 27 w(split)e Fv(A)h(q)h(r)f(ps)h([])197 b(=)39 +b(\(if)h Fj(\014n)f Fv(A)h(q)f(then)h(\(ps,[]\))h(else)f(r\))822 +1963 y Fj(auto)p 970 1963 V 27 w(split)e Fv(A)h(q)h(r)f(ps)h(\(x#xs\))h +(=)861 2055 y Fj(auto)p 1009 2055 V 27 w(split)d Fv(A)i(\()p +Fj(next)f Fv(A)h(x)f(q\))h(\(if)g Fj(\014n)f Fv(A)g(q)h(then)g +(\(ps,x#xs\))h(else)f(r\))g(\(ps@[x]\))h(xs)681 2196 +y Fx(Although)30 b(it)g(ma)n(y)f(seem)g(that)h Fq(maxsplit)g +Fx(is)f(completely)h(sup)r(erseded)f(b)n(y)h Fq(auto)p +3231 2196 25 4 v 29 w(split)f Fx(and)681 2295 y(need)23 +b(nev)n(er)f(ha)n(v)n(e)h(b)r(een)g(de\014ned,)h(the)g(opp)r(osite)f +(is)g(true:)g(it)h(is)f(no)n(w)f(trivial)h(\(an)g(induction)681 +2395 y(on)k Fl(xs)p Fx(\))g(to)h(sho)n(w)822 2542 y Fj(auto)p +970 2542 24 4 v 27 w(split)38 b Fv(A)h(\()p Fj(delta)g +Fv(A)g(ps)h(q\))f(r)h(ps)g(xs)f(=)822 2634 y Fj(maxsplit)f +Fv(\()p Fi(\025)h Fv(ys.)h Fj(\014n)f Fv(A)h(\()p Fj(delta)e +Fv(A)h(ys)h(q\)\))g(r)f(ps)h(xs)681 2775 y Fx(whic)n(h,)27 +b(putting)i(the)f(results)f(of)g Fr(x)p Fx(5.1)g(together,)g(yields)g +(the)h(corollary)822 2918 y Fj(is)p 875 2918 V 27 w(maxchopp)r(er)40 +b Fv(\()p Fj(accepts)f Fv(A\))h(\()p Fj(scan)g Fv(A\))681 +3057 y Fx(where)822 3183 y Fj(scan)f Fv(::)h(\()p Fi(\013)p +Fv(,)p Fi(\033)s Fv(\)da)g Fh(\))f Fi(\013)h Fv(chopper)822 +3275 y Fj(scan)f Fv(A)h Fh(\021)f Fj(chop)g Fv(\()p Fi(\025)g +Fv(xs.)h Fj(auto)p 1798 3275 V 27 w(split)e Fv(A)h(\()p +Fj(sta)n(rt)h Fv(A\))f(\([],xs\))i([])f(xs\))681 3414 +y Fx(is)30 b(our)g(main)g(function.)i(As)e(predicted)h(ab)r(o)n(v)n(e,) +e(sp)r(ecializing)h(the)h(generic)e(dev)n(elopmen)n(t)681 +3513 y(to)e(automata)g(is)g(easy)-7 b(.)805 3613 y(If)23 +b(the)f(whole)f(dev)n(elopmen)n(t)h(app)r(ears)e(o)n(v)n(erly)g(mo)r +(dular,)h(I)h(recommend)g(the)g(follo)n(wing)681 3713 +y(more)27 b(direct)g(de\014nition)h(of)g(the)g(scanner)822 +3839 y Fj(acc)39 b Fv(A)h(s)f(r)h(ps)f([])197 b(ys)40 +b(=)f(\(if)h(ys=[])g(then)g(r)g(else)g(\(ys#)p Fj(fst)r +Fv(\(r\),)p Fj(snd)p Fv(\(r\)\)\))822 3931 y Fj(acc)f +Fv(A)h(s)f(r)h(ps)f(\(x#xs\))i(ys)f(=)f(\(let)h(t)g(=)f +Fj(next)g Fv(A)h(x)f(s)h(in)979 4022 y(if)g Fj(\014n)f +Fv(A)g(t)979 4113 y(then)h Fj(acc)f Fv(A)h(t)f(\()p Fj(acc)h +Fv(A)f(\()p Fj(sta)n(rt)h Fv(A\))f(\([],xs\))i([])f(xs)g([]\))1332 +4205 y(\(ps@[x]\))h(xs)f(\(ps@[x]\))979 4296 y(else)g +Fj(acc)f Fv(A)h(t)f(r)h(\(ps@[x]\))h(xs)e(ys\))681 4437 +y Fx(due)c(to)f(Roland)g(Handl)25 b([5].)35 b(It)g(mixes)f(the)h +(generic)f(and)g(the)h(sp)r(eci\014c)g(and,)g(on)f(top)h(of)681 +4537 y(that,)41 b(is)f(primitiv)n(e)h(recursiv)n(e.)1706 +4506 y Fn(3)1782 4537 y Fx(Although)g Fq(acc)f Fx(confuses)g(me)h(to)g +(this)g(da)n(y)-7 b(,)40 b(Ric)n(hard)p 681 4595 473 +4 v 697 4649 a Fg(3)758 4681 y Fw(Nested)22 b(primitiv)n(e)g(recursion) +h(can)g(b)r(e)f(reduced)g(to)h(ordinary)g(primitiv)n(e)e(recursion)26 +b([3)q(].)d(Handl)758 4772 y(w)n(as)i(forced)g(to)g(use)f(primitiv)n(e) +g(recursion)h(b)r(ecause)g(at)f(the)h(time)e(HOL)h(did)g(not)g(pro)n +(vide)g(easy)758 4863 y(access)j(to)e(w)n(ellfounded)i(recursion.)2080 +5112 y Fx(12)p eop +%%Page: 13 13 +13 12 bop 365 387 a Fx(Ma)n(yr)35 b(managed)f(to)h(v)n(erify)g(it.)h +(Ho)n(w)n(ev)n(er,)e(the)h(pro)r(of)g(is)h(su\016cien)n(tly)f +(unpleasan)n(t)g(that)365 487 y(there)c(had)h(to)f(b)r(e)h(a)f(b)r +(etter)g(w)n(a)n(y)f(to)i(do)f(it.)g(What)h(I)g(presen)n(ted)e(ab)r(o)n +(v)n(e)g(is)i(the)f(result)g(of)365 587 y(m)n(y)d(quest)f(for)g(a)g +(more)g(app)r(ealing)g(solution.)365 834 y Fo(5.3)95 +b(Filling)30 b(paragraphs)365 999 y Fx(After)40 b(the)f(completion)g +(of)g(the)g(ab)r(o)n(v)n(e)e(dev)n(elopmen)n(t)i(I)g(suddenly)g(remem)n +(b)r(ered)f(that)365 1099 y(Bird)30 b(and)g(W)-7 b(adler)24 +b([1])30 b(also)f(de\014ne)h(a)f(function)i Fq(scan)o +Fx(.)f(On)g(lo)r(oking)f(it)h(up,)h(I)f(found)g(that)365 +1198 y(it)c(is)g(used)f(in)h(a)f(similar)g(application,)g(namely)g +(\014lling)g(paragraphs)e(\(pages)i(91{92\).)e(This)365 +1298 y(made)28 b(me)f(realize)g(that)h(one)f(can)g(de\014ne)h(their)g +(function)506 1425 y Fj(\014ll)38 b Fv(::)i(nat)g Fh(\))f +Fv(\()p Fi(\013)h Fv(list)g(list\))g Fh(\))f Fv(\()p +Fi(\013)h Fv(list)g(list)g(list\))365 1555 y Fx(that)29 +b(tak)n(es)f(a)g(list)h(of)f(w)n(ords)f(and)i(returns)e(a)i(list)f(of)h +(lines)f(that)h(are)f(no)g(longer)f(than)i(the)365 1655 +y(giv)n(en)e(line)h(width)g(\(the)g(\014rst)g(parameter\),)e(as)h(an)g +(instance)h(of)f(our)g Fq(scan)p Fx(:)506 1802 y Fj(\014ll)38 +b Fv(n)i Fh(\021)f Fj(fst)q Fv(\()p Fj(scan)g Fv(\(0,)h +Fi(\025)f Fv(xs)h(i.)f(i+)p Fj(length)p Fv(\(xs\)+1,)i +Fi(\025)e Fv(i.)g(i)h Fh(\024)f Fv(n+1\)\))365 1942 y +Fx(The)i(second)g(comp)r(onen)n(t)g(of)f(the)i(result)f(of)g +Fq(scan)f Fx(is)h(dropp)r(ed)g(\()p Fq(fst)g Fx(selects)g(the)h +(\014rst)365 2041 y(comp)r(onen)n(t\))24 b(to)f(mak)n(e)g(the)h +(function)g(conform)e(to)h(the)h(t)n(yp)r(e)g(in)h([1].)e(If)h(none)f +(of)h(the)f(input)365 2141 y(w)n(ords)k(is)g(longer)f(than)i(the)g +(line)g(width,)g(the)g(second)f(comp)r(onen)n(t)g(is)h(alw)n(a)n(ys)e +Fl([])p Fx(.)365 2408 y Ft(6)112 b(Do)s(es)38 b(it)e(run?)365 +2606 y Fx(T)-7 b(o)31 b(b)r(e)g(more)f(precise:)h(can)f(the)i +(de\014nitions)f(of)g(the)g(main)g(functions)g Fq(rexp2nae)p +Fx(,)g Fq(nae2da)365 2706 y Fx(and)h Fq(scan)g Fx(\(and)g(of)h(their)f +(supp)r(orting)g(functions\))g(b)r(e)h(in)n(terpreted)f(directly)g(in)g +(a)g(func-)365 2806 y(tional)39 b(programming)d(language?)i(F)-7 +b(or)38 b Fq(scan)o Fx(,)h(the)g(answ)n(er)f(is)g(y)n(es:)g(only)h +(primitiv)n(e)f(or)365 2905 y(w)n(ellfounded)25 b(recursion)e(on)i +(lists)f(is)h(used.)g(Deterministic)g(automata)e(are)h(also)g(easy)-7 +b(,)24 b(but)365 3005 y(nondeterministic)34 b(automata)e(cause)g(a)h +(little)h(problem:)f(w)n(e)g(need)g(to)h(implemen)n(t)f(sets.)365 +3105 y(In)g(full)f(generalit)n(y)-7 b(,)31 b(this)h(is)g(imp)r +(ossible,)g(but)h(\014nite)g(sets)f(can)f(b)r(e)i(represen)n(ted)e(as)g +(lists,)365 3204 y(whic)n(h)f(is)f(one)g(of)g(the)h(standard)e +(examples)h(of)g(implemen)n(tation)h(concepts)e(for)h(abstract)365 +3304 y(data)e(t)n(yp)r(es.)h(F)-7 b(ortunately)g(,)27 +b(the)i(sets)e(arising)f(in)i Fq(rexp2nae)g Fx(are)e(all)i(\014nite,)g +(thanks)f(to)h(the)365 3403 y(\014nite)f(nature)e(of)h(regular)e +(expressions.)h(Hence)h Fq(rexp2nae)f Fx(is)h(also)f(executable)h +(\(although)365 3503 y(a)h(replacemen)n(t)f(of)h(\014nite)g(sets)g(b)n +(y)g(lists)g(w)n(ould)f(b)r(e)i(tric)n(ky)e(to)h(p)r(erform)f +(automatically)g(in)365 3603 y(HOL\).)490 3702 y(The)37 +b(real)f(problem)h(arises)f(with)i(the)f(de\014nition)h(of)f +Fq(nae2da)o Fx(,)g(whic)n(h)h(con)n(tains)e(the)365 3802 +y(inductiv)n(ely)28 b(de\014ned)f(transitiv)n(e)g(closure)f(op)r +(erator)f Fl(^*)i Fx(and)g(is)g(therefore)g(de\014nitely)g(not)365 +3902 y(directly)39 b(executable.)f(Ev)n(en)f(if)i(all)f(sets)h(in)f +(sigh)n(t)g(are)g(\014nite,)h(w)n(e)f(w)n(ould)g(still)h(need)g(a)365 +4001 y(recursiv)n(e)24 b(function)i(for)f(computing)h(the)g(transitiv)n +(e)e(closure.)h(Hence)g(the)h(answ)n(er)e(to)i(the)365 +4101 y(section)h(title)i(is)e(`almost'.)490 4201 y(There)g(are)g(a)g(n) +n(um)n(b)r(er)g(of)h(solutions)e(to)i(this)g(problem:)417 +4365 y Fo({)41 b Fx(Sho)n(w)d(that)f Fq(rexp2nae)h Fx(only)f(pro)r +(duces)g(\014nite)h(automata)f(and)g(de\014ne)h(a)f(recursiv)n(e)506 +4465 y(v)n(ersion)h(of)h Fl(^*)f Fx(that)i(op)r(erates)e(on)g(\014nite) +i(relations.)e(This)h(is)g(p)r(ossible)g(but)g(most)506 +4565 y(lik)n(ely)28 b(messier)e(than)i(the)g(next)g(alternativ)n(e.)417 +4664 y Fo({)41 b Fx(Generate)25 b(a)g(nondeterministic)h(automaton)f +Fs(without)33 b Fp(")p Fx(-steps)25 b(directly)g(from)g(a)h(reg-)506 +4764 y(ular)e(expression.)f(Although)i(this)f(complicates)g(the)h +(construction)e(a)h(little,)i(I)e(exp)r(ect)506 4863 +y(the)k(pro)r(ofs)f(actually)g(b)r(ecome)h(simpler)f(b)r(ecause)g +Fp(")p Fx(-steps)g(are)g(eliminated.)1765 5112 y(13)p +eop +%%Page: 14 14 +14 13 bop 733 387 a Fo({)41 b Fx(Giv)n(e)20 b(a)f(concrete)g(\014nite)i +(represen)n(tation)d(of)i(the)g(transition)f(function)i(of)f(automata)e +(in)822 487 y(terms)25 b(of,)h(for)f(example,)g(asso)r(ciation)f +(lists.)h(This)h(do)r(es)f(en)n(tail)g(rephrasing)f Fq(rexp2nae)822 +587 y Fx(in)j(terms)g(of)h(this)f(represen)n(tation,)f(but)i(I)f(b)r +(eliev)n(e)g(that)h(one)f(can)g(reuse)f(most)h(of)g(the)822 +686 y(pro)r(ofs)e(b)n(y)h(sho)n(wing)f(that)i(the)f(concrete)g +(represen)n(tation)e(is)i(a)g(correct)f(implemen)n(ta-)822 +786 y(tion)j(of)f(the)h(abstract)f(automaton)f(mo)r(del)i(of)g(this)g +(pap)r(er.)681 957 y(W)-7 b(e)41 b(in)n(tend)g(to)g(in)n(v)n(estigate)f +(the)h(last)f(t)n(w)n(o)h(options)f(in)h(the)g(near)f(future.)i(Note)e +(that)681 1056 y(there)34 b(is)g(a)f(fundamen)n(tal)i(di\013erence)f(b) +r(et)n(w)n(een)g(them.)g(P)n(erforming)f(the)h(con)n(v)n(ersion)e(of) +681 1156 y(nondeterministic)e(automata)f(on)h(our)g(functional)g +(represen)n(tation)f(p)r(ostp)r(ones)h(most)g(of)681 +1256 y(the)e(w)n(ork)e(un)n(til)i(run)f(time,)h(where)f(states)g(of)h +(the)g Fl(da)f Fx(are)f(represen)n(ted)h(as)f(sets)i(of)f(states)681 +1355 y(of)35 b(the)g Fl(na)p Fx(,)f(all)h(of)g(whic)n(h)g(ha)n(v)n(e)e +(to)i(b)r(e)h(pro)r(cessed.)d(Giv)n(en)i(a)g(concrete)f(data)g +(structure)681 1455 y(for)h(the)i(transition)e(function)i(of)f(the)g +Fl(na)p Fx(,)f(it)i(is)f(p)r(ossible)f(to)h(eliminate)h(this)f(o)n(v)n +(erhead)681 1555 y(b)n(y)27 b(represen)n(ting)g(eac)n(h)f(of)i(the)g +(\(\014nitely)h(man)n(y!\))e(sets)h(of)g(states)f(b)n(y)g(a)h(single)f +(new)h(state.)681 1654 y(Nev)n(ertheless,)36 b(the)i(sp)r(eedup)g(is)g +(only)f(a)g(constan)n(t)g(factor)g(that)h(dep)r(ends)g(on)f(the)h(size) +681 1754 y(of)h(the)g(state)g(space.)g(Both)g(represen)n(tations)e +(allo)n(w)i Fl(DA.)p Fq(accepts)e Fx(to)j(op)r(erate)e(in)h(time)681 +1853 y(linear)32 b(in)g(the)h(size)f(of)h(the)g(input)g(string.)f +(Scanning,)g(ho)n(w)n(ev)n(er,)e(is)j(quadratic,)e(b)r(ecause)681 +1953 y(the)23 b(recognition)f(of)h(eac)n(h)f(maximal)h(pre\014x)g +(requires)e(tra)n(v)n(ersing)g(the)i(whole)g(\(remaining\))681 +2053 y(string.)681 2330 y Ft(7)112 b(Related)37 b(w)m(ork)681 +2537 y Fx(I)e(am)g(a)n(w)n(are)e(of)i(three)g(other)g(pap)r(ers)g(on)g +(formalized)f(automata)g(theory)24 b([7,)35 b(4,)g(2],)g(all)681 +2637 y(of)f(whic)n(h)h(use)f(constructiv)n(e)g(t)n(yp)r(e)h(theory)f +(\(i.e.)h(they)f(extract)g(their)h(algorithms)e(from)681 +2737 y(the)d(pro)r(ofs)f(rather)f(than)i(pro)n(viding)e(them)j(as)e +(part)g(of)g(the)h(de\014nitions\))g(and)g(follo)n(w)24 +b([6])681 2836 y(closely)-7 b(.)25 b(The)g(main)h(result)f(of)h(Kreitz) +e([7)o(])i(is)g(the)g(pumping)g(lemma)f(and)g(the)h(main)g(result)681 +2936 y(of)i(Constable)g Fs(et)j(al.)26 b Fx([2)o(])j(the)g(Myhill/Nero) +r(de)f(theorem.)h(Both)f(of)h(them)g(use)g(the)g(Nuprl)681 +3035 y(system.)805 3137 y(Closest)d(to)f(our)h(w)n(ork)e(is)i(that)g(b) +n(y)g(Filli^)-42 b(atre)24 b([4])i(who)g(giv)n(es)e(a)i(constructiv)n +(e)f(pro)r(of)g(for)681 3236 y(the)e(translation)g(of)g(regular)e +(expressions)h(in)n(to)h(nondeterministic)g(\014nite)h(automata)e(with) +681 3336 y Fp(")p Fx(-mo)n(v)n(es)32 b(in)i(the)h(Co)r(q)f(system.)1707 +3306 y Fn(4)1778 3336 y Fx(Although)g(the)h(transition)e(relation)h(of) +g(the)g(resulting)681 3436 y(automaton)c(has)h(a)g(nice)g(concrete)g +(represen)n(tation)e(as)i(a)g(\014nite)h(set)f(of)g(triples,)h(he)f(do) +r(es)681 3535 y(not)41 b(consider)e(the)j(further)e(con)n(v)n(ersion)f +(in)n(to)i(a)f(deterministic)h(automaton)f(\(nor)g(the)681 +3635 y(scanning)24 b(asp)r(ect\).)h(It)g(is)g(the)g(latter)g(con)n(v)n +(ersion)d(where)j(executabilit)n(y)f(breaks)g(do)n(wn)g(for)681 +3734 y(us)j(b)r(ecause)h(w)n(e)f(use)g(the)h(transitiv)n(e)f(closure)f +(op)r(erator)g Fl(^*)p Fx(.)805 3836 y(Thompson)f([11)o(])c(presen)n +(ts)g(an)g(implemen)n(tation)h(\(no)f(pro)r(ofs\))g(of)h(regular)d +(expressions)681 3935 y(and)27 b(\014nite)h(automata)f(in)h(Miranda.) +681 4212 y Ft(8)112 b(Conclusion)681 4420 y Fx(W)-7 b(e)30 +b(ha)n(v)n(e)e(seen)h(a)g(formalization)f(of)i(a)f(\(v)n(ery)f +(simple\))i(lexical)f(analyzer)f(generator)f(tak-)681 +4519 y(ing)k(us)h(from)f(a)h(regular)e(expression)g(righ)n(t)h(to)g +(the)i(actual)e(scanner.)f(Almost)i(all)g(of)f(the)p +681 4595 473 4 v 697 4649 a Fg(4)758 4681 y Fw(Con)n(trary)c(to)h(the)f +(title)h(of)g(that)g(pap)r(er,)g(the)f(opp)r(osite)h(direction)g(is)g +(not)f(men)n(tioned.)g(I)g(ha)n(v)n(e)758 4772 y(formalized)i(and)g(v)n +(eri\014ed)f(the)h(translation)h(of)g(automata)e(in)n(to)h(regular)h +(sets)g(as)f(a)g(recursiv)n(e)758 4863 y(algorithm)d(similar)g(to)g(W) +-6 b(arshall's.)27 b(The)f(details)h(are)f(b)r(ey)n(ond)f(the)g(curren) +n(t)g(pap)r(er.)2080 5112 y Fx(14)p eop +%%Page: 15 15 +15 14 bop 365 387 a Fx(functions)30 b(in)n(v)n(olv)n(ed)e(are)g +(directly)h(executable.)g(Ignoring)f(the)i(small)f(executabilit)n(y)g +(gap)365 487 y(in)e(our)f(dev)n(elopmen)n(t)h(\(see)d +Fr(x)p Fx(6\),)j(this)g(w)n(ork)f(sho)n(ws)f(that)i(HOL)g(is)g(eminen)n +(tly)g(suitable)f(to)365 587 y(v)n(erify)f(\(total\))h(functional)g +(programs,)d(although)i(HOL)g(is)h(neither)f(constructiv)n(e)g(\(where) +365 686 y(y)n(ou)30 b(often)h(w)n(orry)e(if)i(the)g(extracted)f +(program)f(will)i(b)r(e)g(what)g(y)n(ou)f(think)h(it)g(should)g(b)r +(e\))365 786 y(nor)c(a)g(quan)n(ti\014er-free)f(logic)h(of)h(recursiv)n +(ely)d(de\014ned)j(functions.)490 886 y(The)20 b(size)g(of)g(the)g(com) +n(bined)g(theories)f(and)h(pro)r(ofs)f(is)h(quite)g(acceptable:)f +(roughly)g(1000)365 985 y(lines)33 b(dedicated)g(to)g(automata)f(and)g +(regular)g(expressions,)f(and)h(few)n(er)h(than)g(400)e(lines)365 +1085 y(in)n(v)n(olving)f(the)h(scanner.)f(My)h(\014rst)f(attempts)i(in) +f(this)g(direction)f(go)g(bac)n(k)g(a)h(n)n(um)n(b)r(er)f(of)365 +1184 y(y)n(ears)21 b(and)i(include)g(dead)f(alleys)g(explored)g(b)n(y)g +(studen)n(ts.)h(The)g(bulk)g(of)g(the)g(dev)n(elopmen)n(t)365 +1284 y(presen)n(ted)k(in)h(this)g(pap)r(er)f(to)r(ok)g(me)h(ab)r(out)g +(3)f(in)n(tensiv)n(e)g(w)n(eeks.)490 1384 y(Although)36 +b(the)g(w)n(ork)e(w)n(as)g(not)i(in)n(tended)g(as)f(a)g(formalization)g +(of)g(a)g(sp)r(eci\014c)h(text-)365 1483 y(b)r(o)r(ok)27 +b(\(in)g(con)n(trast)e(to)g([2)o(])i(or)f([8]\),)h(I)g(feel)g(that)g +(Hop)r(croft)f(and)h(Ullman's)f(treatmen)n(t)h(has)365 +1583 y(in\015uenced)j(me)f(more)f(than)h(necessary)-7 +b(,)27 b(and)i(that)g(a)g(dev)n(elopmen)n(t)f(b)n(ypassing)f +Fp(")p Fx(-mo)n(v)n(es)365 1683 y(migh)n(t)h(ha)n(v)n(e)e(b)r(een)i(b)r +(etter.)g(This)g(will)g(b)r(e)g(explored)e(in)i(the)g(future.)365 +1864 y Fs(A)l(cknow)t(le)l(dgment)51 b Fx(Stefan)35 b(W)-7 +b(eb)r(er)35 b(help)r(ed)g(with)g(an)f(initial)g(v)n(ersion)f(of)i(the) +f(pro)r(ofs)g(in)365 1964 y Fr(x)p Fx(4.)28 b(Da)n(vid)g(Basin,)f(Da)n +(vid)h(v)n(on)f(Oheim)n(b,)h(Larry)e(P)n(aulson)g(and)i(Markus)f(W)-7 +b(enzel)29 b(read)e(a)365 2064 y(draft)h(and)f(commen)n(ted)h(on)f(it)h +(at)f(short)g(notice,)h(for)f(whic)n(h)g(I)h(am)f(v)n(ery)g(grateful.) +365 2315 y Ft(References)404 2489 y Fw(1.)42 b(R.)25 +b(Bird)31 b(and)g(P)-6 b(.)25 b(W)-6 b(adler.)50 b Fa(Intr)l(o)l +(duction)34 b(to)f(F)-6 b(unctional)33 b(Pr)l(o)l(gr)l(amming)p +Fw(.)51 b(Pren)n(tice-Hall,)505 2580 y(1988.)404 2672 +y(2.)42 b(R.)25 b(Constable,)36 b(P)-6 b(.)25 b(Jac)n(kson,)36 +b(P)-6 b(.)25 b(Naumo)n(v,)34 b(and)g(J.)26 b(Urib)r(e.)62 +b(Constructiv)n(ely)35 b(formalizing)505 2763 y(automata.)40 +b(In)27 b(G.)f(Plotkin)i(and)f(M.)e(T)-6 b(ofte,)29 b(editors,)g +Fa(Pr)l(o)l(of,)g(L)l(anguage)i(and)f(Inter)l(action:)505 +2854 y(Essays)f(in)e(Honour)i(of)e(R)l(obin)g(Milner)p +Fw(.)f(MIT)g(Press,)h(1998.)36 b(T)-6 b(o)26 b(app)r(ear.)404 +2946 y(3.)42 b(W.)25 b(F)-6 b(elsc)n(her.)35 b Fa(Ber)l(e)l(chenb)l +(arkeit)p Fw(.)j(Springer-V)-6 b(erlag,)26 b(1993.)404 +3037 y(4.)42 b(J.-C.)32 b(Filli^)-38 b(atre.)51 b(Finite)31 +b(automata)f(theory)h(in)f(Co)r(q.)i(A)e(constructiv)n(e)g(pro)r(of)i +(of)f(Kleene's)505 3128 y(theorem.)42 b(T)-6 b(ec)n(hnical)29 +b(Rep)r(ort)f(97-04,)i(Lab)r(oratoire)h(de)d(l'Informatique)g(du)g(P)n +(arall)n(\023)-36 b(elisme,)505 3220 y(Ecole)27 b(Normale)e(Sup)n(\023) +-36 b(erieure)25 b(de)h(Ly)n(on,)f(1997.)404 3311 y(5.)42 +b(R.)25 b(Handl.)41 b(V)-6 b(eri\014k)l(ation)27 b(eines)i(Scanners)f +(\(mit)f(Isab)r(elle\).)42 b(Master's)30 b(thesis,)f(Institut)e(f)r +(\177)-41 b(ur)505 3402 y(Informatik,)25 b(TU)h(M)r(\177)-41 +b(unc)n(hen,)26 b(1993.)404 3494 y(6.)42 b(J.)26 b(E.)31 +b(Hop)r(croft)h(and)f(J.)25 b(D.)31 b(Ullman.)50 b Fa(Intr)l(o)l +(duction)34 b(to)f(A)n(utomata)h(The)l(ory,)g(L)l(anguages,)505 +3585 y(and)28 b(Computation.)35 b Fw(Addison-W)-6 b(esley)g(,)24 +b(1979.)404 3676 y(7.)42 b(C.)26 b(Kreitz.)32 b(Constructiv)n(e)21 +b(automata)g(theory)f(implemen)n(ted)e(with)j(the)f(Nuprl)g(pro)r(of)i +(dev)n(el-)505 3768 y(opmen)n(t)g(system.)33 b(T)-6 b(ec)n(hnical)25 +b(Rep)r(ort)e(TR)h(86-779,)i(Dept.)e(of)g(Computer)f(Science,)i +(Cornell)505 3859 y(Univ)n(ersit)n(y)-6 b(,)25 b(1986.)404 +3950 y(8.)42 b(T.)26 b(Nipk)n(o)n(w.)34 b(Winsk)n(el)25 +b(is)h(\(almost\))g(righ)n(t:)g(T)-6 b(o)n(w)n(ards)26 +b(a)g(mec)n(hanized)f(seman)n(tics)g(textb)r(o)r(ok.)505 +4041 y(In)37 b(V.)25 b(Chandru)37 b(and)g(V.)25 b(Vina)n(y)-6 +b(,)37 b(editors,)h Fa(F)-6 b(oundations)41 b(of)d(Softwar)l(e)i(T)-6 +b(e)l(chnolo)l(gy)40 b(and)505 4133 y(The)l(or)l(etic)l(al)35 +b(Computer)f(Scienc)l(e)p Fw(,)f(v)n(olume)d(1180)k(of)e +Fa(L)l(e)l(ct.)i(Notes)h(in)d(Comp.)h(Sci.)p Fw(,)e(pages)505 +4224 y(180{192.)e(Springer-V)-6 b(erlag,)26 b(1996.)404 +4315 y(9.)42 b(L.)25 b(C.)36 b(P)n(aulson.)62 b(Generic)36 +b(automatic)e(pro)r(of)i(to)r(ols.)63 b(In)34 b(R.)25 +b(V)-6 b(ero\013,)35 b(editor,)g Fa(A)n(utomate)l(d)505 +4407 y(R)l(e)l(asoning)j(and)f(its)g(Applic)l(ations)p +Fw(.)g(MIT)f(Press,)h(1997.)65 b(Also)37 b(Rep)r(ort)e(396,)i(Computer) +505 4498 y(Lab)r(oratory)-6 b(,)26 b(Univ)n(ersit)n(y)f(of)h(Cam)n +(bridge.)365 4589 y(10.)43 b(L.)25 b(C.)19 b(P)n(aulson.)33 +b(A)17 b(generic)i(tableau)g(pro)n(v)n(er)f(and)f(its)i(in)n(tegration) +g(with)g(Isab)r(elle.)32 b(T)-6 b(ec)n(hnical)505 4681 +y(Rep)r(ort)25 b(441,)i(Univ)n(ersit)n(y)e(of)i(Cam)n(bridge,)e +(Computer)g(Lab)r(oratory)-6 b(,)27 b(1998.)365 4772 +y(11.)43 b(S.)25 b(Thompson.)63 b(Regular)35 b(expressions)h(and)f +(automata)h(using)f(Miranda.)64 b(Av)l(ailable)36 b(at)505 +4863 y Fv(http://www.cs.ukc.ac.uk/pubs/)q(1995/)q(212)p +Fw(,)c(1995.)1765 5112 y Fx(15)p eop +%%Page: 16 16 +16 15 bop 681 387 a Fw(This)26 b(article)h(w)n(as)g(t)n(yp)r(eset)e +(using)h(the)f(L)1859 370 y Fg(A)1892 387 y Fw(T)1934 +403 y(E)1978 387 y(X)g(macro)g(pac)n(k)l(age)h(with)g(the)g(LLNCS2E)g +(class.)2080 5112 y Fx(16)p eop +%%Trailer +end +userdict /end-hook known{end-hook}if +%%EOF