(original) (raw)

%!PS-Adobe-2.0 %%Creator: dvips 5.511 Copyright 1986, 1993 Radical Eye Software %%Title: All.dvi %%CreationDate: Thu Jul 25 12:07:05 1996 %%Pages: 4 %%PageOrder: Ascend %%BoundingBox: 0 0 596 842 %%EndComments %DVIPSCommandLine: dvips -pp 11-14 All.dvi -o /home/blagny/lib/algo/seminars/sem93-94/zimmermann.ps %DVIPSSource: TeX output 1996.07.25:0820 %%BeginProcSet: tex.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 /@rigin{isls{[0 -1 1 0 0 0] concat}if 72 Resolution div 72 VResolution div neg scale isls{Resolution hsize -72 div mul 0 TR}if Resolution VResolution vsize -72 div 1 add mul TR matrix currentmatrix dup dup 4 get round 4 exch put dup dup 5 get round 5 exch put 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 add]{ch-image}imagemask restore}B /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 showpage userdict /eop-hook known{eop-hook}if}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 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 %%BeginProcSet: special.pro TeXDict begin /SDict 200 dict N SDict begin /@SpecialDefaults{/hs 612 N /vs 792 N /ho 0 N /vo 0 N /hsc 1 N /vsc 1 N /ang 0 N /CLIP 0 N /rwiSeen false N /rhiSeen false N /letter{}N /note{}N /a4{}N /legal{}N}B /@scaleunit 100 N /@hscale{@scaleunit div /hsc X}B /@vscale{@scaleunit div /vsc X}B /@hsize{/hs X /CLIP 1 N}B /@vsize{/vs X /CLIP 1 N}B /@clip{/CLIP 2 N}B /@hoffset{/ho X}B /@voffset{/vo X}B /@angle{/ang X}B /@rwi{10 div /rwi X /rwiSeen true N}B /@rhi {10 div /rhi X /rhiSeen true N}B /@llx{/llx X}B /@lly{/lly X}B /@urx{/urx X}B /@ury{/ury X}B /magscale true def end /@MacSetUp{userdict /md known{userdict /md get type /dicttype eq{userdict begin md length 10 add md maxlength ge{/md md dup length 20 add dict copy def}if end md begin /letter{}N /note{}N /legal{ }N /od{txpose 1 0 mtx defaultmatrix dtransform S atan/pa X newpath clippath mark{transform{itransform moveto}}{transform{itransform lineto}}{6 -2 roll transform 6 -2 roll transform 6 -2 roll transform{itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll curveto}}{{closepath}}pathforall newpath counttomark array astore /gc xdf pop ct 39 0 put 10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack}if}N /txpose{pxs pys scale ppr aload pop por{noflips{pop S neg S TR pop 1 -1 scale}if xflip yflip and{pop S neg S TR 180 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{pop S neg S TR pop 180 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{ppr 1 get neg ppr 0 get neg TR}if}{noflips{TR pop pop 270 rotate 1 -1 scale}if xflip yflip and{TR pop pop 90 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{TR pop pop 90 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{TR pop pop 270 rotate ppr 2 get ppr 0 get neg sub neg 0 S TR}if}ifelse scaleby96{ppr aload pop 4 -1 roll add 2 div 3 1 roll add 2 div 2 copy TR .96 dup scale neg S neg S TR}if}N /cp{pop pop showpage pm restore}N end}if}if}N /normalscale{Resolution 72 div VResolution 72 div neg scale magscale{DVImag dup scale}if 0 setgray}N /psfts{S 65781.76 div N}N /startTexFig{/psf$SavedState save N userdict maxlength dict begin /magscale false def normalscale currentpoint TR /psf$ury psfts /psf$urx psfts /psf$lly psfts /psf$llx psfts /psf$y psfts /psf$x psfts currentpoint /psf$cy X /psf$cx X /psf$sx psf$x psf$urx psf$llx sub div N /psf$sy psf$y psf$ury psf$lly sub div N psf$sx psf$sy scale psf$cx psf$sx div psf$llx sub psf$cy psf$sy div psf$ury sub TR /showpage{}N /erasepage{}N /copypage{}N /p 3 def @MacSetUp}N /doclip{psf$llx psf$lly psf$urx psf$ury currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll S lineto S lineto S lineto closepath clip newpath moveto}N /endTexFig{end psf$SavedState restore}N /@beginspecial{ SDict begin /SpecialSave save N gsave normalscale currentpoint TR @SpecialDefaults count /ocount X /dcount countdictstack N}N /@setspecial{CLIP 1 eq{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlineto closepath clip}if ho vo TR hsc vsc scale ang rotate rwiSeen{rwi urx llx sub div rhiSeen{ rhi ury lly sub div}{dup}ifelse scale llx neg lly neg TR}{rhiSeen{rhi ury lly sub div dup scale llx neg lly neg TR}if}ifelse CLIP 2 eq{newpath llx lly moveto urx lly lineto urx ury lineto llx ury lineto closepath clip}if /showpage{}N /erasepage{}N /copypage{}N newpath}N /@endspecial{count ocount sub{pop}repeat countdictstack dcount sub{end}repeat grestore SpecialSave restore end}N /@defspecial{SDict begin}N /@fedspecial{end}B /li{lineto}B /rl{ rlineto}B /rc{rcurveto}B /np{/SaveX currentpoint /SaveY X N 1 setlinecap newpath}N /st{stroke SaveX SaveY moveto}N /fil{fill SaveX SaveY moveto}N /ellipse{/endangle X /startangle X /yrad X /xrad X /savematrix matrix currentmatrix N TR xrad yrad scale 0 0 1 startangle endangle arc savematrix setmatrix}N end %%EndProcSet TeXDict begin 39158280 55380996 1000 300 300 (/a/home/pommard/algo/salvy/Tex/Sem/Sem94/All.dvi) @start /Fa 11 122 df<01FE0007FF001FFF803E0780380300700000700000E00000E00000E00000E00000E0 0000E000007000007001C03801C03E03C01FFF8007FF0001FC0012147D9318>99 D<01F00007FC001FFE003E0F00380780700380700380E001C0E001C0FFFFC0FFFFC0FFFFC0E000 007000007001C03801C03E03C01FFF8007FF0001FC0012147D9318>101 D<03800007C00007C00007C0000380000000000000000000000000007FC000FFC0007FC00001C0 0001C00001C00001C00001C00001C00001C00001C00001C00001C00001C00001C00001C00001C0 00FFFF00FFFF80FFFF00111D7C9C18>105 D<7FE000FFE0007FE00000E00000E00000E00000E0 0000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E0 0000E00000E00000E00000E00000E0007FFFC0FFFFE07FFFC0131C7E9B18>108 D<7CE0E000FFFBF8007FFFF8001F1F1C001E1E1C001E1E1C001C1C1C001C1C1C001C1C1C001C1C 1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C007F1F1F00FFBFBF807F 1F1F001914819318>I<7E3E00FEFF807FFFC00FC1C00F80E00F00E00E00E00E00E00E00E00E00 E00E00E00E00E00E00E00E00E00E00E00E00E00E00E07FC3FCFFE7FE7FC3FC1714809318>I<01 E38007FB801FFF803E1F80380F80700780700780E00380E00380E00380E00380E00380E0038070 0780700780380F803C1F801FFF800FFB8003E38000038000038000038000038000038000038000 0380003FF8003FF8003FF8151E7E9318>113 D<07F7003FFF007FFF00780F00E00700E00700E0 07007C00007FE0001FFC0003FE00001F00600780E00380E00380F00380F80F00FFFF00FFFC00E7 F00011147D9318>115 D<0180000380000380000380000380007FFFC0FFFFC0FFFFC003800003 80000380000380000380000380000380000380000380000380400380E00380E00380E001C1C001 FFC000FF80003E0013197F9818>I<7E07E0FE0FE07E07E00E00E00E00E00E00E00E00E00E00E0 0E00E00E00E00E00E00E00E00E00E00E00E00E00E00E01E00F03E007FFFC03FFFE01FCFC171480 9318>I<7F8FF0FF8FF87F8FF00E01C00E03800E0380070380070700070700038700038600038E 0001CE0001CE0000CC0000CC0000DC0000780000780000780000700000700000700000F00000E0 0079E0007BC0007F80003F00001E0000151E7F9318>121 D E /Fb 1 80 df<000C1F8000107FE0002087F000C381F0018700F0030600F8060E00F80E1C00781C1C00781C 3800783820007838000078780000787000007070000070F00000F0F00000E0F00000E0F00001E0 F00001C0F0000180F8000380F8000700780006007C000C007E0010003F0020001FC1C0000FFF00 0003F800001D1E7E9C21>79 D E /Fc 4 111 df<01000F00F700070007000700070007000700 070007000700070007000700070007000700FFF80D137C9215>49 D<000C00000C00001C00003C 00003C00005C00009C00019C00011C00021C00061C00041C00081C00101C00301C00201C00401C 00C01C00FFFFC0001C00001C00001C00001C00001C00001C00001C0001FFC0121B7F9215>52 D<07C00C301818300C700C600EE006E006E007E007E007E0076007600F300F18170C2707C70006 0006000E300C780C78187018203030C00F80101C7E9215>57 D<381F004E61804681C04701C08F 01C08E01C00E01C00E01C01C03801C03801C03801C0700380710380710380E10380E2070064030 038014127E9119>110 D E /Fd 20 120 df<0003F020001E0C60003002E000E003C001C001C0 038001C0070000C00E0000801E0000801C0000803C0000803C0000007800000078000000780000 00F0000000F0000000F0000000F0000000F0000400F0000400F0000400F0000800700008007000 100038002000180040000C0180000706000001F800001B1E7A9C1E>67 D<01FE0007F8003E0007 80002E000F00002E001700002E001700002E002700004E002E00004E004E00004E004E00004E00 8E00008E011C00008E011C00008E021C00008E021C000107043800010704380001070838000107 1038000207107000020720700002072070000207407000040740E000040780E000040700E0000C 0700E0001C0601E000FF861FFC00251C7D9B25>77 D<01FC03FE001C0070003C0060002E004000 2E0040002E0040004700800047008000470080004380800083810000838100008181000081C100 0101C2000101C2000100E2000100E2000200E40002007400020074000200740004003800040038 00040038000C0018001C001000FF8010001F1C7D9B1F>I<000F8400304C00403C008018010018 03001803001806001006001006000007000007000003E00003FC0001FF00007F800007C00001C0 0001C00000C00000C02000C02000C0600180600180600300600200F00400CC180083E000161E7D 9C17>83 D<1FFFFFC01C0701C0300E00C0200E0080600E0080400E0080401C0080801C0080801C 0080001C0000003800000038000000380000003800000070000000700000007000000070000000 E0000000E0000000E0000000E0000001C0000001C0000001C0000001C0000003C000007FFE0000 1A1C799B1E>I<03CC063C0C3C181C3838303870387038E070E070E070E070E0E2C0E2C0E261E4 62643C380F127B9115>97 D<01F007080C08181C3838300070007000E000E000E000E000E000E0 08E010602030C01F000E127B9113>99 D<01E007100C1018083810701070607F80E000E000E000 E000E000E0086010602030C01F000D127B9113>101 D<0FC00001C00001C00003800003800003 80000380000700000700000700000700000E78000E8C000F0E000E0E001C0E001C0E001C0E001C 0E00381C00381C00381C00383800703880703880707080707100E03200601C00111D7D9C15> 104 D<01800380010000000000000000000000000000001C002600470047008E008E000E001C00 1C001C0038003800710071007100720072003C00091C7C9B0D>I<1F8003800380070007000700 07000E000E000E000E001C001C001C001C0038003800380038007000700070007000E400E400E4 00E40068003800091D7C9C0B>108 D<3C1E0780266318C04683A0E04703C0E08E0380E08E0380 E00E0380E00E0380E01C0701C01C0701C01C0701C01C070380380E0388380E0388380E0708380E 0710701C0320300C01C01D127C9122>I<3C3C002646004687004707008E07008E07000E07000E 07001C0E001C0E001C0E001C1C00381C40381C40383840383880701900300E0012127C9117>I< 01E007180C0C180C380C300E700E700EE01CE01CE01CE018E038E030E06060C031801E000F127B 9115>I<07870004D98008E0C008E0C011C0E011C0E001C0E001C0E00381C00381C00381C00381 800703800703000707000706000E8C000E70000E00000E00001C00001C00001C00001C00003C00 00FF8000131A7F9115>I<3C3C26C2468747078E068E000E000E001C001C001C001C0038003800 380038007000300010127C9112>114 D<01F006080C080C1C18181C001F001FC00FF007F00078 00386030E030C030806060C01F000E127D9111>I<00C001C001C001C00380038003800380FFE0 0700070007000E000E000E000E001C001C001C001C00384038403840388019000E000B1A7D990E >I<1E0300270700470700470700870E00870E000E0E000E0E001C1C001C1C001C1C001C1C0038 38803838801838801839001C5900078E0011127C9116>I<1E0183270387470387470383870701 8707010E07010E07011C0E021C0E021C0E021C0E04180C04181C04181C081C1C100C263007C3C0 18127C911C>119 D E /Fe 15 104 df0 D<70F8F8F87005057C8D0D>I<400004C0000C6000183000301800600C00C00601800303000186 0000CC0000780000300000300000780000CC000186000303000601800C00C01800603000306000 18C0000C40000416187A9623>I<000000C0000003C000000F0000003C000000F0000003C00000 070000001C00000078000001E00000078000001E00000078000000E0000000780000001E000000 0780000001E0000000780000001C0000000700000003C0000000F00000003C0000000F00000003 C0000000C0000000000000000000000000000000000000000000000000000000007FFFFF80FFFF FFC01A247C9C23>20 DI<0000020000000003000000000300000000018000000000C000000000C00000000060 007FFFFFF000FFFFFFFC000000000E00000000038000000001F0000000007C00000000F0000000 03C000000007000000000C00FFFFFFF8007FFFFFF0000000006000000000C00000000180000000 018000000003000000000300000000020000261A7D972D>41 D<00000010000000003000000000 F000000000F000000000F000000001F000000001F000000002F000000002F000000004F0000000 0CF000000008F000000018F000000010F000000020F000000020F000000040F8000000C0F80000 008078000001807800000300780000020078000006007800000DFFF800000FFFF8000018007800 00300078000060007C0040E0007C00C0C0003C00E380003C00FF00003E00FE00003F80FE00001F 00780000000021237FA024>65 D<00301F8000F07FE003E187F000E301F001E600F001EC00F001 F800F001F800E001F000C001F0018003E0030003E0060003C0180003C0E00003C3FC00078FFE00 07803F0007801F8007000FC0070007C00F0003C00F0003C00E0003C00E0003C01E0003801C0003 801C0007003C00060039800C003FC0180077F0600063FF8000C0FE00001C217F9F1E>I<0000FC 0007FE001C3E00201E00C01E01801C03801C07003C0600380E00381C00601C00003C0000380000 380000780000780000700000700000F00000F00000F00000F00000F00000F00000F80018F80030 7800707C00C07E00803F83001FFC0007F0001721809F18>I<00007FFFE00003FFFFF0000E3801 E000303800C0006078000000E078000001C070000001807000000000F000000000F000000000E0 00000000E000000001E000000001C000000001C000000003FFF8000003FFF00000038000000007 0000000007000000000F000000000E000000000E000000001C000000001C000000003800000000 3800000030700000007870000000FCC00000007F800000003E0000000024207F9E21>70 D<0001FE00000FFF8000181F8000600780008007000300070007000E000E000C000E0018001C00 30001C0000003800000038000000780000007000000070000200F0000E00F0001C00F0001C00F0 003C00F0003C00F0007800F8007800F800F8007C01F0007E0370003F06F0001FF8E0000FE0E000 0001C0000001C0000003800000030000380600007E0C00007FF000001FC0000019257E9F1B>I< 00FC00002003FE0000E0043E0001C0181E0001C0301E000380701E000380F01E000700C01C0007 00001C000E00003C000E00003C001E00003C001C000038001C00003BFFFC00007FFFF800007800 38000070007800007000700000F000700000E000F00000E000F00001E000E00001E000E00001C0 01E00001C001E00003C001E000038001E000038001E000078001E040070001E1C0060001F3000C 0001FE00000000F80023217F9E26>I<000407E000081FF8003061FC0060C07E00C1803E018300 1E0307001F060E001F0E0E000F1C1C000F1C18000F3830000F3800000F7800000F7800000E7000 000E7000001EF000001EF000001CF000001CF0000038F0000038F0000070F8000060F80000E078 0001C07C0001807C0002003E0004003F8018001FE0E00007FF800001FC000020217D9F24>79 D<000F0038006000E001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C0 038007001E00F8001E000700038001C001C001C001C001C001C001C001C001C001C001C001C001 C001C001C000E000600038000F102D7DA117>102 DI E /Ff 6 118 df<0F80180020006000C000FE00C00080008000C000C00061003E00090D7D8C 0E>15 D<200E00203F00406180404080808080808080810080810100810300C20600721C003FF0 000FC0000600000400000400000C00000C000008000011137E8C16>39 D<00200060006000C000 C000C0018001800180030003000300060006000C000C000C001800180018003000300030006000 60006000C000C000C0000B1D7E9511>61 D<3E0006000C000C000C000C001800187018B8193832 30340038003E006300631063106310C320C1C00D147E9312>107 D<30F8590C4E0C9C0C980C18 0C180C30183019303130316032601C100D7F8C15>110 D<380C4C0C4C0C8C1898181818181830 3030323032307218B40F1C0F0D7F8C14>117 D E /Fg 8 89 df<0000180000300000600000E0 0000C0000180000380000700000600000E00000C00001C0000380000380000700000700000E000 00E00001E00001C00001C0000380000380000380000780000700000700000F00000E00000E0000 1E00001E00001E00001C00001C00003C00003C00003C00003C0000380000780000780000780000 780000780000780000780000780000700000F00000F00000F00000F00000F00000F00000F00000 F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000 F00000F00000F00000F00000F00000F00000700000780000780000780000780000780000780000 7800007800003800003C00003C00003C00003C00001C00001C00001E00001E00001E00000E0000 0E00000F000007000007000007800003800003800003800001C00001C00001E00000E00000E000 007000007000003800003800001C00000C00000E000006000007000003800001800000C00000E0 000060000030000018157C768121>32 DI<0018007800F001E003C007800F001F001E003E003C007C007C007800F800F800F8 00F800F800F800F800F800F800F800F800F800F800F800F800F800F800F800F800F800F800F800 F8000D25707E25>56 D58 D<007C007C007C007C007C007C007C007C007C007C007C007C00 7C007C007C007C007C007C007C007C007C007C007C007C00F800F800F800F001F001E003E003C0 078007000E001C003800F000C000F00038001C000E000700078003C003E001E001F000F000F800 F800F8007C007C007C007C007C007C007C007C007C007C007C007C007C007C007C007C007C007C 007C007C007C007C007C007C0E4D798025>60 D62 D80 D88 D E /Fh 5 107 df0 D<0F001E003BC061806060804040310040801A0020800E0020800E0020800E0020800B00204011 80404020C0C030C07B800F001E001B0D7E8C21>49 D<00E0030006000600060006000600060006 0006000600060006001C00F0001C00060006000600060006000600060006000600060006000300 00E00B1D7E9511>102 DI106 D E /Fi 25 122 df<70F8FCFC74040404080810102040060E7B840F>44 D<70F8F8F87005057B840F>46 D66 D70 D<7FFFFFF878078078600780184007800840078008C007800C80078004800780048007 800480078004000780000007800000078000000780000007800000078000000780000007800000 078000000780000007800000078000000780000007800000078000000780000007800000078000 00078000000FC00003FFFF001E1F7D9E24>84 D<001800001800001800003C00003C00004E0000 4E00004E000087000087000187800103800103800201C00201C003FFC00400E00400E008007008 00701800703C0078FE01FF18177F961C>97 DI<007E080381980700780C00381C001838001878000870 0008F00000F00000F00000F00000F00000F00000F000007000087800083800081C00100C001007 0060038180007E0015177E961B>IIII<007E080381980700780C00381C0018380018780008700008F00000F00000 F00000F00000F00000F007FFF000787000387800383800381C00380C00380700380380D8007F08 18177E961D>III107 DIII<00FE000383800E00E01C00703C007838003878003C70001CF000 1EF0001EF0001EF0001EF0001EF0001EF0001E70001C78003C3800383C00781C00700E00E00383 8000FE0017177E961D>II114 D<0F84306C601C400CC004C004C004E00070007F003FE01FF801FC001C000E 0006800680068006C004E008D81087E00F177E9615>I<7FFFFC70381C403804403804C0380680 380280380280380200380000380000380000380000380000380000380000380000380000380000 3800003800003800007C0007FFC017177F961B>II121 D E /Fj 8 62 df<01020408103020606040C0C0C0C0C0C0C0C0C0C0406060203010080402 01081E7E950D>40 D<80402010080C0406060203030303030303030303020606040C0810204080 081E7E950D>I<006000006000006000006000006000006000006000006000006000006000FFFF F0FFFFF000600000600000600000600000600000600000600000600000600000600014167E9119 >43 D<0F0030C0606060604020C030C030C030C030C030C030C030C030C03040206060606030C0 0F000C137E9211>48 D<0C001C00EC000C000C000C000C000C000C000C000C000C000C000C000C 000C000C000C00FFC00A137D9211>I<1F0060C06060F070F030603000700070006000C001C001 80020004000810101020207FE0FFE00C137E9211>I<0FC030707038703870380038003000E00F C0007000380018001C601CF01CF018E03860701FC00E137F9211>I<7FFFE0FFFFF00000000000 00000000000000000000000000FFFFF07FFFE0140A7E8B19>61 D E /Fk 26 123 df<007E01C007000E001C003C003800780078007FF0F000F000F0007000700070003000 18000C1807E00F147E9312>15 D<04001E0008007F001000FF801001C1C0200300C02002004040 060040400400404008004040080040C0000080C010008040100100401003006020060038201C00 1F20F8000FFFE00007FFC00000FE000000C0000000C0000000C0000001C0000001C00000018000 00018000000380000003800000030000001A1E7E931E>39 D<70F8F8F87005057C840D>58 D<70F8FCFC74040404080810102040060E7C840D>I<000001C00000078000001E000000780000 01E00000078000000E00000038000000F0000003C000000F0000003C000000F0000000F0000000 3C0000000F00000003C0000000F0000000380000000E0000000780000001E0000000780000001E 0000000780000001C01A1A7C9723>I<000100030003000600060006000C000C000C0018001800 1800300030003000600060006000C000C000C00180018001800300030003000600060006000C00 0C000C00180018001800300030003000600060006000C000C000C000102D7DA117>I<00000200 0000060000000E0000000E0000001E0000001F0000002F0000002F0000004F0000008F0000008F 0000010F0000010F0000020F0000040F0000040F0000080F800008078000100780002007800020 0780007FFF800040078000800780018007800100078002000780020007C0040003C00C0003C01E 0007C0FF807FFC1E207E9F22>65 D<00FFFFE0000F0078000F003C000F001C000F001E001E001E 001E001E001E001E001E001E003C003C003C003C003C0078003C00F0007803C0007FFF80007803 C0007801E000F000F000F000F000F000F000F0007001E000F001E000F001E000F001E000E003C0 01E003C003C003C0038003C00F0007801E00FFFFF0001F1F7E9E22>I<0000FE0200078186001C 004C0038003C0060003C00C0001C01C0001803800018070000180F0000181E0000101E0000103C 0000003C00000078000000780000007800000078000000F0000000F0000000F0000000F0000000 F00000807000008070000080700001003800010038000200180004000C001800060020000381C0 0000FE00001F217E9F21>I<00FFFFFF000F000E000F0006000F0002000F0002001E0002001E00 02001E0002001E0002003C0004003C0400003C0400003C04000078080000781800007FF8000078 180000F0100000F0100000F0100000F0100001E0000001E0000001E0000001E0000003C0000003 C0000003C0000003C0000007C00000FFFE0000201F7E9E1D>70 D<00007E0100038183000E0046 0038002E0070001E00E0000E01C0000C0380000C0700000C0F00000C1E0000081E0000083C0000 003C00000078000000780000007800000078000000F0000000F0007FFCF00001E0F00001E0F000 03C0700003C0700003C0700003C038000780380007801C000F800C000B80060033000380C10000 7F000020217E9F24>I<00FFF80FF8000F8003E0000F000380000F000200000F000400001E0008 00001E002000001E004000001E008000003C010000003C040000003C080000003C180000007838 000000787C000000793C0000007A3C000000F41E000000F81E000000F01E000000F00F000001E0 0F000001E00F000001E007800001E007800003C007800003C003C00003C003C00003C003C00007 C003E000FFFC3FFC00251F7E9E27>75 D<7FFC1FF807C003C00780010007800100078001000F00 02000F0002000F0002000F0002001E0004001E0004001E0004001E0004003C0008003C0008003C 0008003C00080078001000780010007800100078001000F0002000F0002000F0002000F0004000 F0004000700080007001000030020000380400000C18000007E000001D207C9E1F>85 D<007FFFF800FC00F000E001E000C003C0018007800100078003000F0002001E0002003C000400 78000000F8000000F0000001E0000003C00000078000000F0000000F0000001E0000003C000000 78008000F0008001F0010001E0010003C00300078002000F0006001E0004003E000C003C003C00 7800F800FFFFF8001D1F7D9E1F>90 D<00F1800389C00707800E03801C03803C03803807007807 00780700780700F00E00F00E00F00E00F00E10F01C20F01C20703C20705C40308C400F07801414 7E9318>97 D<07803F8007000700070007000E000E000E000E001C001C001CF01D0C3A0E3C0E38 0F380F700F700F700F700FE01EE01EE01EE01CE03CE038607060E031C01F0010207E9F14>I<00 7C01C207010E0F1E0F1C0E3C04780078007800F000F000F000F000F00070017002300418380FC0 10147E9314>I<0000780003F80000700000700000700000700000E00000E00000E00000E00001 C00001C000F1C00389C00707800E03801C03803C0380380700780700780700780700F00E00F00E 00F00E00F00E10F01C20F01C20703C20705C40308C400F078015207E9F18>I<00007C0000CE00 019E00039E00030C000700000700000700000700000E00000E00000E0000FFF0000E00000E0000 1C00001C00001C00001C00001C0000380000380000380000380000380000700000700000700000 700000700000E00000E00000E00000E00000C00001C000318000798000F300006200003C000017 297E9F16>102 D<00E001E001E000C000000000000000000000000000000E0013002380438043 8043808700070007000E000E001C001C001C20384038403840388019000E000B1F7E9E10>105 D<01E0000FE00001C00001C00001C00001C0000380000380000380000380000700000700000701 E00706100E08700E10F00E20F00E40601C80001D00001E00001FC000387000383800383800381C 20703840703840703840701880E01880600F0014207E9F18>107 D<1E07802318C023A06043C0 704380704380708700E00700E00700E00700E00E01C00E01C00E01C00E03821C03841C07041C07 081C03083803101801E017147E931B>110 D<007C018203010603060706060E00078007F803FC 01FE001F00077007F006F006E004400820301FC010147E9315>115 D<00C000E001C001C001C0 01C003800380FFF8038007000700070007000E000E000E000E001C001C001C001C103820382038 20384018800F000D1C7F9B10>I<0F00601180702180E021C0E041C0E04380E08381C00701C007 01C00701C00E03800E03800E03800E03840E07080C07080C07080E0F1006131003E1E016147E93 1A>I<01E02003F04007F8C00C1F8008010000020000040000080000100000600000C000010000 0200000400800801001003003F060061FC0040F80080700013147E9315>122 D E /Fl 34 122 df<00003FE00000E01000018038000380780003007800070030000700000007 000000070000000E0000000E0000000E000000FFFFE0000E00E0001C01C0001C01C0001C01C000 1C01C0001C03800038038000380380003803800038070000380700007007000070071000700E20 00700E2000700E2000E00E2000E0064000E0038000E0000000C0000001C0000001C00000318000 0079800000F3000000620000003C0000001D29829F1A>12 D<0001000200040008001000200060 00C0018001800300070006000E000C001C0018003800380030007000700060006000E000E000C0 00C000C000C000C000C000C000C000C000C000C000C000C0004000600060002000100010000800 102E79A113>40 D<00100000080000040000060000020000030000030000030000010000018000 018000018000018000018000018000018000038000038000038000030000030000030000070000 0700000600000600000E00000C00000C00001C0000180000380000300000700000600000E00000 C0000180000100000300000600000C0000180000300000600000800000112E80A113>I<1C3C3C 3C3C040408081020204080060E7D840E>44 D<70F8F8F0E005057B840E>46 D<070F1F1F0E0000000000000000000070F8F8F0E008147B930E>58 D<00000200000006000000 060000000E0000001E0000001E0000003F0000002F0000004F0000004F0000008F0000010F0000 010F0000020F0000020F0000040F00000C0F0000080F0000100F0000100F0000200F80003FFF80 0040078000C007800080078001000780010007800200078002000780060007801E000F80FF807F F81D207E9F22>65 D<01FFFFC0001E00F0001E0078001E0038001E003C003C003C003C003C003C 003C003C003C0078007800780078007800F0007801E000F0078000FFFE0000F00F8000F003C001 E001C001E001E001E001E001E001E003C001E003C001E003C001E003C001C0078003C007800780 07800F0007801E000F007800FFFFE0001E1F7D9E20>I<01FFFFFE001E001C001E000C001E0004 001E0004003C0004003C0004003C0004003C00040078080800780800007808000078180000F030 0000FFF00000F0300000F0300001E0200001E0200001E0200001E0001003C0002003C0002003C0 004003C00040078000800780018007800100078007000F001F00FFFFFE001F1F7D9E1F>69 D<0000FC040007030C001C00980030007800E0007801C000380380003003800030070000300E00 00301E0000201E0000203C0000003C00000078000000780000007800000078000000F0000000F0 00FFF0F0000780F0000780F0000F0070000F0070000F0070000F0070001E0038001E0018003E00 1C002E000E00CC000383040000FC00001E217A9F23>71 D<00F1800389C00707800E03801C0380 3C0380380700780700780700780700F00E00F00E00F00E00F00E20F01C40F01C40703C40705C40 308C800F070013147C9317>97 D<07803F8007000700070007000E000E000E000E001C001C001C F01D0C3A0E3C0E380F380F700F700F700F700FE01EE01EE01EE01CE03CE038607060E031C01F00 10207B9F15>I<007E0001C1000300800E07801E07801C07003C0200780000780000780000F000 00F00000F00000F00000F0000070010070020030040018380007C00011147C9315>I<00007800 03F80000700000700000700000700000E00000E00000E00000E00001C00001C000F1C00389C007 07800E03801C03803C0380380700780700780700780700F00E00F00E00F00E00F00E20F01C40F0 1C40703C40705C40308C800F070015207C9F17>I<007C01C207010E011C013C013802780C7BF0 7C00F000F000F000F0007000700170023804183807C010147C9315>I<00007800019C00033C00 033C000718000700000700000E00000E00000E00000E00000E0001FFE0001C00001C00001C0000 1C0000380000380000380000380000380000700000700000700000700000700000700000E00000 E00000E00000E00000C00001C00001C0000180003180007B0000F300006600003C00001629829F 0E>I<003C6000E27001C1E00380E00700E00F00E00E01C01E01C01E01C01E01C03C03803C0380 3C03803C03803C07003C07001C0F001C17000C2E0003CE00000E00000E00001C00001C00301C00 783800F0700060E0003F8000141D7E9315>I<01E0000FE00001C00001C00001C00001C0000380 00038000038000038000070000070000071E000763000E81800F01C00E01C00E01C01C03801C03 801C03801C0380380700380700380700380E10700E20700C20701C20700C40E00CC06007001420 7D9F17>I<00C001E001E001C000000000000000000000000000000E0033002300438043004700 87000E000E000E001C001C001C003840388030807080310033001C000B1F7C9E0E>I<01E0000F E00001C00001C00001C00001C0000380000380000380000380000700000700000703C00704200E 08E00E11E00E21E00E40C01C80001D00001E00001FC00038E00038700038700038384070708070 7080707080703100E03100601E0013207D9F15>107 D<03C01FC0038003800380038007000700 070007000E000E000E000E001C001C001C001C0038003800380038007000700070007100E200E2 00E200E200640038000A207C9F0C>I<1C0F80F0002630C318004740640C004780680E00470070 0E004700700E008E00E01C000E00E01C000E00E01C000E00E01C001C01C038001C01C038001C01 C038001C01C0708038038071003803806100380380E10038038062007007006600300300380021 147C9325>I<1C0F802630C04740604780604700704700708E00E00E00E00E00E00E00E01C01C0 1C01C01C01C01C03843803883803083807083803107003303001C016147C931A>I<007C0001C3 000301800E01C01E01C01C01E03C01E07801E07801E07801E0F003C0F003C0F003C0F00780F007 00700F00700E0030180018700007C00013147C9317>I<01C1E002621804741C04781C04701E04 701E08E01E00E01E00E01E00E01E01C03C01C03C01C03C01C0380380780380700380E003C1C007 2380071E000700000700000E00000E00000E00000E00001C00001C0000FFC000171D809317>I< 00F0400388C00705800E03801C03803C0380380700780700780700780700F00E00F00E00F00E00 F00E00F01C00F01C00703C00705C0030B8000F3800003800003800007000007000007000007000 00E00000E0000FFE00121D7C9315>I<1C1E002661004783804787804707804703008E00000E00 000E00000E00001C00001C00001C00001C00003800003800003800003800007000003000001114 7C9313>I<00FC030206010C030C070C060C000F800FF007F803FC003E000E700EF00CF00CE008 401020601F8010147D9313>I<018001C0038003800380038007000700FFF007000E000E000E00 0E001C001C001C001C003800380038003820704070407080708031001E000C1C7C9B0F>I<0E00 C03300E02301C04381C04301C04701C08703800E03800E03800E03801C07001C07001C07001C07 101C0E20180E20180E201C1E200C264007C38014147C9318>I<0E03803307802307C04383C043 01C04700C08700800E00800E00800E00801C01001C01001C01001C02001C02001C04001C04001C 08000E300003C00012147C9315>I<0E00C1C03300E3C02301C3E04381C1E04301C0E04701C060 870380400E0380400E0380400E0380401C0700801C0700801C0700801C0701001C0701001C0602 001C0F02000C0F04000E13080003E1F0001B147C931E>I<0383800CC4401068E01071E02071E0 2070C040E00000E00000E00000E00001C00001C00001C00001C040638080F38080F38100E58100 84C60078780013147D9315>I<0E00C03300E02301C04381C04301C04701C08703800E03800E03 800E03801C07001C07001C07001C07001C0E00180E00180E001C1E000C3C0007DC00001C00001C 00003800F03800F07000E06000C0C0004380003E0000131D7C9316>I E /Fm 27 118 df<000FE000007FF80000F81C0001E07C0003E07C0007C07C0007C07C0007C03800 07C0000007C0000007C0000007C1FE00FFFFFE00FFFFFE0007C03E0007C03E0007C03E0007C03E 0007C03E0007C03E0007C03E0007C03E0007C03E0007C03E0007C03E0007C03E0007C03E0007C0 3E0007C03E0007C03E003FF9FFC03FF9FFC01A20809F1D>12 D<387CFEFEFE7C3807077C860F> 46 D<00E00001E0000FE000FFE000F3E00003E00003E00003E00003E00003E00003E00003E000 03E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E000 03E00003E000FFFF80FFFF80111D7C9C1A>49 D<07F0001FFE00383F007C1F80FE0FC0FE0FC0FE 0FE0FE07E07C07E03807E0000FE0000FC0000FC0001F80001F00003E0000780000F00000E00001 C0000380600700600E00601C00E01FFFC03FFFC07FFFC0FFFFC0FFFFC0131D7D9C1A>I<01FC00 07FF000E0F801E0FC03F07E03F07E03F07E03F07E01E0FC0000FC0000F80001F0001FC0001FC00 000F800007C00003E00003F00003F83803F87C03F8FE03F8FE03F8FE03F0FC03F07807E03C0FC0 1FFF8003FC00151D7E9C1A>I<0001C00003C00007C00007C0000FC0001FC0003BC00073C00063 C000C3C00183C00383C00703C00E03C00C03C01803C03803C07003C0E003C0FFFFFEFFFFFE0007 C00007C00007C00007C00007C00007C000FFFE00FFFE171D7F9C1A>I<3803803FFF803FFF003F FE003FFC003FF0003F800030000030000030000030000033F80037FE003C1F00380F801007C000 07C00007E00007E07807E0FC07E0FC07E0FC07E0FC07C0780FC0600F80381F001FFC0007F00013 1D7D9C1A>I<003F0001FFC007E0E00F81E01F03F01E03F03E03F07C03F07C01E07C0000FC1000 FCFF00FDFFC0FD03E0FE01F0FE01F0FC01F8FC01F8FC01F8FC01F87C01F87C01F87C01F83C01F0 3E01F01E03E00F07C007FF8001FE00151D7E9C1A>I<0007FC02003FFF0E00FE03DE03F000FE07 E0003E0FC0001E1F80001E3F00000E3F00000E7F0000067E0000067E000006FE000000FE000000 FE000000FE000000FE000000FE000000FE0000007E0000007E0000067F0000063F0000063F0000 0C1F80000C0FC0001807E0003803F0007000FE01C0003FFF800007FC001F1F7D9E26>67 D<0007FC0200003FFF0E0000FE03DE0003F000FE0007E0003E000FC0001E001F80001E003F0000 0E003F00000E007F000006007E000006007E00000600FE00000000FE00000000FE00000000FE00 000000FE00000000FE003FFFE0FE003FFFE07E00007E007E00007E007F00007E003F00007E003F 00007E001F80007E000FC0007E0007E0007E0003F000FE0000FE01FE00003FFF8E000007FC0600 231F7D9E29>71 D73 D<03FC080FFF381E03F83800F8700078700038F00038F00018F00018F80000FC00007FC0007FFE 003FFF801FFFE00FFFF007FFF000FFF80007F80000FC00007C00003CC0003CC0003CC0003CE000 38E00078F80070FE01E0E7FFC081FF00161F7D9E1D>83 D<07FC001FFF003F0F803F07C03F03E0 3F03E00C03E00003E0007FE007FBE01F03E03C03E07C03E0F803E0F803E0F803E0FC05E07E0DE0 3FF8FE0FE07E17147F9319>97 D<01FE0007FF801F0FC03E0FC03E0FC07C0FC07C0300FC0000FC 0000FC0000FC0000FC0000FC00007C00007E00003E00603F00C01F81C007FF0001FC0013147E93 17>99 D<0007F80007F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000 F801F8F80FFEF81F83F83E01F87E00F87C00F87C00F8FC00F8FC00F8FC00F8FC00F8FC00F8FC00 F87C00F87C00F87E00F83E01F81F07F80FFEFF03F8FF18207E9F1D>I<01FE0007FF800F83C01E 01E03E00F07C00F07C00F8FC00F8FFFFF8FFFFF8FC0000FC0000FC00007C00007C00003E00181E 00180F807007FFE000FF8015147F9318>I<01FC3C07FFFE0F079E1E03DE3E03E03E03E03E03E0 3E03E03E03E01E03C00F07800FFF0009FC001800001800001C00001FFF800FFFF007FFF81FFFFC 3C007C70003EF0001EF0001EF0001E78003C78003C3F01F80FFFE001FF00171E7F931A>103 D<1C003E007F007F007F003E001C00000000000000000000000000FF00FF001F001F001F001F00 1F001F001F001F001F001F001F001F001F001F001F001F00FFE0FFE00B217EA00E>105 D108 DII<01FF0007FFC01F83F03E00F83E00F87C007C7C00 7CFC007EFC007EFC007EFC007EFC007EFC007E7C007C7C007C3E00F83E00F81F83F007FFC001FF 0017147F931A>II114 D<0FE63FFE701E600EE006E006F800FFC07FF83FFC1FFE03FE 001FC007C007E007F006F81EFFFCC7F010147E9315>I<01800180018003800380038007800F80 3F80FFFCFFFC0F800F800F800F800F800F800F800F800F800F800F860F860F860F860F8607CC03 F801F00F1D7F9C14>II E /Fn 71 123 df<00008000000001C000000001C000000003E000000003E000000005F0000000 04F000000008F80000000878000000107C000000103C000000203E000000201E000000401F0000 00400F000000800F80000080078000010007C000010003C000020003E000020001E000040001F0 00040000F000080000F80008000078001000007C001000003C002000003E002000001E007FFFFF FF007FFFFFFF00FFFFFFFF8021207E9F26>1 D<001F800000F0F00001C0380007801E000F000F 000E0007001E0007803C0003C03C0003C07C0003E07C0003E0780001E0F80001F0F84021F0F840 21F0F87FE1F0F87FE1F0F87FE1F0F84021F0F84021F0F80001F0780001E0780001E07C0003E03C 0003C03C0003C01E0007800E0007000F000F0007801E0001C0380000F0F000001F80001C217D9F 23>I6 D<001F83E000F06E3001C078780380F8780300F03007 007000070070000700700007007000070070000700700007007000FFFFFF800700700007007000 070070000700700007007000070070000700700007007000070070000700700007007000070070 000700700007007000070070000700700007007000070070007FE3FF001D20809F1B>11 D<003F0000E0C001C0C00381E00701E00701E0070000070000070000070000070000070000FFFF E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700 E00700E00700E00700E00700E00700E07FC3FE1720809F19>I<003FE000E0E001C1E00381E007 00E00700E00700E00700E00700E00700E00700E00700E0FFFFE00700E00700E00700E00700E007 00E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E007 00E07FE7FE1720809F19>I<001F81F80000F04F040001C07C06000380F80F000300F00F000700 F00F00070070000007007000000700700000070070000007007000000700700000FFFFFFFF0007 007007000700700700070070070007007007000700700700070070070007007007000700700700 070070070007007007000700700700070070070007007007000700700700070070070007007007 00070070070007007007007FE3FE3FF02420809F26>I<7038F87CFC7EFC7E743A040204020402 0804080410081008201040200F0E7E9F17>34 D<0020004000800100020006000C000C00180018 003000300030007000600060006000E000E000E000E000E000E000E000E000E000E000E000E000 6000600060007000300030003000180018000C000C000600020001000080004000200B2E7DA112 >40 D<800040002000100008000C00060006000300030001800180018001C000C000C000C000E0 00E000E000E000E000E000E000E000E000E000E000E000C000C000C001C0018001800180030003 00060006000C00080010002000400080000B2E7DA112>I<000600000006000000060000000600 000006000000060000000600000006000000060000000600000006000000060000000600000006 000000060000FFFFFFF0FFFFFFF000060000000600000006000000060000000600000006000000 06000000060000000600000006000000060000000600000006000000060000000600001C207D9A 23>43 D<70F8FCFC74040404080810102040060E7C840D>II<70F8F8F8 7005057C840D>I<03F0000E1C001C0E00180600380700700380700380700380700380F003C0F0 03C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0F003C070038070 03807003807807803807001806001C0E000E1C0003F000121F7E9D17>48 D<018003800F80F380038003800380038003800380038003800380038003800380038003800380 03800380038003800380038003800380038007C0FFFE0F1E7C9D17>I<03F0000C1C00100E0020 0700400780800780F007C0F803C0F803C0F803C02007C00007C0000780000780000F00000E0000 1C0000380000700000600000C0000180000300000600400C00401800401000803FFF807FFF80FF FF80121E7E9D17>I<03F0000C1C00100E00200F00780F80780780780780380F80000F80000F00 000F00000E00001C0000380003F000003C00000E00000F000007800007800007C02007C0F807C0 F807C0F807C0F00780400780400F00200E001C3C0003F000121F7E9D17>I<1803001FFE001FFC 001FF8001FE00010000010000010000010000010000010000011F000161C00180E001007001007 800003800003800003C00003C00003C07003C0F003C0F003C0E00380400380400700200600100E 000C380003E000121F7E9D17>53 D<03F0000E18001C0C00380600380700700700700380F00380 F00380F003C0F003C0F003C0F003C0F003C07007C07007C03807C0180BC00E13C003E3C0000380 000380000380000700300700780600780E00700C002018001070000FC000121F7E9D17>57 D<70F8F8F8700000000000000000000070F8F8F87005147C930D>I<70F8F8F870000000000000 0000000070F0F8F878080808101010202040051D7C930D>I<7FFFFFE0FFFFFFF0000000000000 0000000000000000000000000000000000000000000000000000FFFFFFF07FFFFFE01C0C7D9023 >61 D<000100000003800000038000000380000007C0000007C0000007C0000009E0000009E000 0009E0000010F0000010F0000010F00000207800002078000020780000403C0000403C0000403C 0000801E0000801E0000FFFE0001000F0001000F0001000F000200078002000780020007800400 03C00E0003C01F0007E0FFC03FFE1F207F9F22>65 DI<000FC0 40007030C001C009C0038005C0070003C00E0001C01E0000C01C0000C03C0000C07C0000407C00 004078000040F8000000F8000000F8000000F8000000F8000000F8000000F8000000F8000000F8 000000780000007C0000407C0000403C0000401C0000401E0000800E0000800700010003800200 01C0040000703800000FC0001A217D9F21>I69 DI<000FE0200078186000E004E0038002E0070001E00F0000E0 1E0000601E0000603C0000603C0000207C00002078000020F8000000F8000000F8000000F80000 00F8000000F8000000F8000000F8007FFCF80003E0780001E07C0001E03C0001E03C0001E01E00 01E01E0001E00F0001E0070001E0038002E000E0046000781820000FE0001E217D9F24>III76 DII<001F800000F0F00001C0380007801E000F000F000E0007001E0007803C0003C0 3C0003C07C0003E0780001E0780001E0F80001F0F80001F0F80001F0F80001F0F80001F0F80001 F0F80001F0F80001F0F80001F0780001E07C0003E07C0003E03C0003C03C0003C01E0007800E00 07000F000F0007801E0001C0380000F0F000001F80001C217D9F23>II82 D<07E0800C198010078030038060018060 0180E00180E00080E00080E00080F00000F000007800007F00003FF0001FFC000FFE0003FF0000 1F800007800003C00003C00001C08001C08001C08001C08001C0C00180C00380E00300F00600CE 0C0081F80012217D9F19>I<7FFFFFE0780F01E0600F0060400F0020400F0020C00F0030800F00 10800F0010800F0010800F0010000F0000000F0000000F0000000F0000000F0000000F0000000F 0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F000000 0F0000000F0000000F0000001F800007FFFE001C1F7E9E21>II87 D<7FFFF87C00F87000F06001E04001E0C003C0C003C0800780800F80800F 00001E00001E00003C00003C0000780000F80000F00001E00001E00003C00403C0040780040F80 040F000C1E000C1E00083C00183C0018780038F801F8FFFFF8161F7D9E1C>90 DI<080410082010201040204020804080408040B85CFC7EFC7E7C 3E381C0F0E7B9F17>II<1FE000303000781800781C00300E0000 0E00000E00000E0000FE00078E001E0E00380E00780E00F00E10F00E10F00E10F01E10781E1038 67200F83C014147E9317>97 D<0E0000FE00000E00000E00000E00000E00000E00000E00000E00 000E00000E00000E00000E3E000EC3800F01C00F00E00E00E00E00700E00700E00780E00780E00 780E00780E00780E00780E00700E00700E00E00F00E00D01C00CC300083E0015207F9F19>I<03 F80E0C1C1E381E380C70007000F000F000F000F000F000F00070007000380138011C020E0C03F0 10147E9314>I<000380003F800003800003800003800003800003800003800003800003800003 8000038003E380061B801C0780380380380380700380700380F00380F00380F00380F00380F003 80F003807003807003803803803807801C07800E1B8003E3F815207E9F19>I<03F0000E1C001C 0E00380700380700700700700380F00380F00380FFFF80F00000F00000F0000070000070000038 00801800800C010007060001F80011147F9314>I<007C00C6018F038F07060700070007000700 070007000700FFF007000700070007000700070007000700070007000700070007000700070007 00070007007FF01020809F0E>I<0000E003E3300E3C301C1C30380E00780F00780F00780F0078 0F00780F00380E001C1C001E380033E0002000002000003000003000003FFE001FFF800FFFC030 01E0600070C00030C00030C00030C000306000603000C01C038003FC00141F7F9417>I<0E0000 FE00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E3E000E4300 0E81800F01C00F01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0 0E01C00E01C00E01C00E01C0FFE7FC16207F9F19>I<1C003E003E003E001C0000000000000000 00000000000E007E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E00 0E000E00FFC00A1F809E0C>I<00E001F001F001F000E0000000000000000000000000007007F0 00F000700070007000700070007000700070007000700070007000700070007000700070007000 70007000706070F060F0C061803F000C28829E0E>I<0E0000FE00000E00000E00000E00000E00 000E00000E00000E00000E00000E00000E00000E0FF00E03C00E03000E02000E04000E08000E10 000E30000E70000EF8000F38000E1C000E1E000E0E000E07000E07800E03800E03C00E03E0FFCF F815207F9F18>I<0E00FE000E000E000E000E000E000E000E000E000E000E000E000E000E000E 000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E00FFE00B20809F0C> I<0E1F01F000FE618618000E81C81C000F00F00E000F00F00E000E00E00E000E00E00E000E00E0 0E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00 E00E000E00E00E000E00E00E000E00E00E00FFE7FE7FE023147F9326>I<0E3E00FE43000E8180 0F01C00F01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0 0E01C00E01C00E01C0FFE7FC16147F9319>I<01F800070E001C03803801C03801C07000E07000 E0F000F0F000F0F000F0F000F0F000F0F000F07000E07000E03801C03801C01C0380070E0001F8 0014147F9317>I<0E3E00FEC3800F01C00F00E00E00E00E00F00E00700E00780E00780E00780E 00780E00780E00780E00700E00F00E00E00F01E00F01C00EC3000E3E000E00000E00000E00000E 00000E00000E00000E00000E0000FFE000151D7F9319>I<03E0800619801C05803C0780380380 780380700380F00380F00380F00380F00380F00380F003807003807803803803803807801C0B80 0E138003E380000380000380000380000380000380000380000380000380003FF8151D7E9318> I<0E78FE8C0F1E0F1E0F0C0E000E000E000E000E000E000E000E000E000E000E000E000E000E00 FFE00F147F9312>I<1F9030704030C010C010C010E00078007F803FE00FF00070803880188018 C018C018E030D0608F800D147E9312>I<020002000200060006000E000E003E00FFF80E000E00 0E000E000E000E000E000E000E000E000E000E080E080E080E080E080610031001E00D1C7F9B12 >I<0E01C0FE1FC00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E 01C00E01C00E01C00E01C00E03C00603C0030DC001F1FC16147F9319>III<7FC3FC0F01E00701C00701 8003810001C20000E40000EC00007800003800003C00007C00004E000087000107000303800201 C00601E01E01E0FF07FE1714809318>II<3FFF380E200E 201C40384078407000E001E001C00380078007010E011E011C0338027006700EFFFE10147F9314 >I E /Fo 10 118 df<03FFFFC0003E00F0003C0078003C003C003C003E003C001E003C003E00 78003E0078003E0078003E0078003E0078003C0078007C00F0007800F000F000F001E000F00780 00FFFE0000F0000001E0000001E0000001E0000001E0000001E0000001E0000003C0000003C000 0003C0000003C0000003C0000003C000000780000007C00000FFFC00001F227EA121>80 D<01FFFFF803F000F003C001E0038003C0030003C00600078004000F0004001E000C001E000800 3C00080078000000F0000000F0000001E0000003C0000007C00000078000000F0000001E000000 3E0000003C00000078004000F0004001F0004001E0008003C00080078000800F8001800F000100 1E0003003C0007007C001F0078007E00FFFFFE001D227DA11E>90 D<03FC000606000F03000F03 800601800001C0000380000380007F8003E3800F03801C0380380700780700F00708F00708F00F 08F00F08F017107867A01F83C015157D9418>97 D<00FE000383800701C00C00E01C00E03800E0 7800E07000E0FFFFE0F00000F00000F00000F00000E00000E00000F00040700080300080180300 0E0C0003F00013157D9416>101 D<006000F001F001F000E00000000000000000000000000000 000001C00FC001C001C001C001C00380038003800380038003800700070007000700070007000E 000F00FFE00C227FA10E>105 D<007803F800700070007000700070007000E000E000E000E000 E000E001C001C001C001C001C001C0038003800380038003800380070007000700070007000700 0E000F00FFE00D237FA20E>108 D<01C1F807E01FC60C183001D80E603801E007801C01E00780 1C01C007001C03C00F003803800E003803800E003803800E003803800E003803800E003807001C 007007001C007007001C007007001C007007001C007007001C00700E003800E00F003C00F0FFE3 FF8FFE27157F942A>I<01C3F01FCC1801D00C01E00E01E00E01C00E03C01C03801C03801C0380 1C03801C03801C0700380700380700380700380700380700380E00700F0078FFE7FF18157F941B >I<01C7C01FC8E001D1E001E1E001E0C001C00003C00003800003800003800003800003800007 00000700000700000700000700000700000E00000F0000FFF00013157F9413>114 D<0E0070FE07F00E00F00E00700E00700E00701C00E01C00E01C00E01C00E01C00E01C00E03801 C03801C03801C03801C03803C03805C0380B801C13C007E3F815157C941B>117 D E /Fp 15 122 df<00038000000380000007C0000007C0000007C000000FE000000FE000001F F000001BF000001BF0000031F8000031F8000061FC000060FC0000E0FE0000C07E0000C07E0001 803F0001FFFF0003FFFF8003001F8003001F8006000FC006000FC00E000FE00C0007E0FFC07FFE FFC07FFE1F1C7E9B24>65 DI<0FF8001C1E003E0F803E07803E07C01C07C00007C0007FC007 E7C01F07C03C07C07C07C0F807C0F807C0F807C0780BC03E13F80FE1F815127F9117>97 DI<03FC000E0E001C1F003C1F00781F00780E00F80000F8 0000F80000F80000F80000F800007800007801803C01801C03000E0E0003F80011127E9115>I< 03F8F00E0F381E0F381C07303C07803C07803C07803C07801C07001E0F000E0E001BF800100000 1800001800001FFF001FFFC00FFFE01FFFF07801F8F00078F00078F000787000707800F01E03C0 07FF00151B7F9118>103 DI<1E003F003F003F003F001E 00000000000000000000000000FF00FF001F001F001F001F001F001F001F001F001F001F001F00 1F001F001F00FFE0FFE00B1E7F9D0E>I108 D<01FC000F07801C01C03C01E07800F07800F0F800F8F800F8F800F8F800F8F800F8 F800F87800F07800F03C01E01E03C00F078001FC0015127F9118>111 DI114 D<1FD830786018E018E018F000FF807FE07F F01FF807FC007CC01CC01CE01CE018F830CFC00E127E9113>I<0300030003000300070007000F 000F003FFCFFFC1F001F001F001F001F001F001F001F001F001F0C1F0C1F0C1F0C0F08079803F0 0E1A7F9913>I121 D E /Fq 20 118 df<0003FE0080001FFF818000FF01E380 01F8003F8003E0001F8007C0000F800F800007801F800007803F000003803F000003807F000001 807E000001807E00000180FE00000000FE00000000FE00000000FE00000000FE00000000FE0000 0000FE00000000FE000000007E000000007E000001807F000001803F000001803F000003801F80 0003000F8000030007C000060003F0000C0001F800380000FF00F000001FFFC0000003FE000021 227DA128>67 D<0003FE0040001FFFC0C0007F00F1C001F8003FC003F0000FC007C00007C00FC0 0003C01F800003C03F000001C03F000001C07F000000C07E000000C07E000000C0FE00000000FE 00000000FE00000000FE00000000FE00000000FE00000000FE00000000FE000FFFFC7E000FFFFC 7F00001FC07F00001FC03F00001FC03F00001FC01F80001FC00FC0001FC007E0001FC003F0001F C001FC003FC0007F80E7C0001FFFC3C00003FF00C026227DA12C>71 D82 D<01FC0407FF8C1F03FC3C007C7C003C78001C78001CF8000CF8000C FC000CFC0000FF0000FFE0007FFF007FFFC03FFFF01FFFF80FFFFC03FFFE003FFE0003FF00007F 00003F00003FC0001FC0001FC0001FE0001EE0001EF0003CFC003CFF00F8C7FFE080FF8018227D A11F>I85 D<07FC001FFF803F07C03F03E03F 01E03F01F01E01F00001F00001F0003FF003FDF01FC1F03F01F07E01F0FC01F0FC01F0FC01F0FC 01F07E02F07E0CF81FF87F07E03F18167E951B>97 DI<00FF8007FFE00F83F01F03F03E03F07E03F07C01E07C0000FC00 00FC0000FC0000FC0000FC0000FC00007C00007E00007E00003E00301F00600FC0E007FF8000FE 0014167E9519>I<0001FE000001FE0000003E0000003E0000003E0000003E0000003E0000003E 0000003E0000003E0000003E0000003E0000003E0001FC3E0007FFBE000F81FE001F007E003E00 3E007E003E007C003E00FC003E00FC003E00FC003E00FC003E00FC003E00FC003E00FC003E00FC 003E007C003E007C003E003E007E001E00FE000F83BE0007FF3FC001FC3FC01A237EA21F>I<00 FE0007FF800F87C01E01E03E01F07C00F07C00F8FC00F8FC00F8FFFFF8FFFFF8FC0000FC0000FC 00007C00007C00007E00003E00181F00300FC07003FFC000FF0015167E951A>I<003F8000FFC0 01E3E003C7E007C7E00F87E00F83C00F80000F80000F80000F80000F80000F8000FFFC00FFFC00 0F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F8000 0F80000F80000F80000F80000F80007FF8007FF80013237FA211>I<1C003E007F007F007F003E 001C000000000000000000000000000000FF00FF001F001F001F001F001F001F001F001F001F00 1F001F001F001F001F001F001F001F001F00FFE0FFE00B247EA310>105 D108 DII<00FE0007FFC00F83E01E00F03E00F87C007C7C007C7C007CFC007EFC007EFC007EFC007E FC007EFC007EFC007E7C007C7C007C3E00F81F01F00F83E007FFC000FE0017167E951C>I114 D<0FF3003FFF00781F00600700E00300E00300F00300FC00007FE0007FF8003FFE000FFF0001FF 00000F80C00780C00380E00380E00380F00700FC0E00EFFC00C7F00011167E9516>I<01800001 80000180000180000380000380000780000780000F80003F8000FFFF00FFFF000F80000F80000F 80000F80000F80000F80000F80000F80000F80000F80000F80000F81800F81800F81800F81800F 81800F830007C30003FE0000F80011207F9F16>II E /Fr 59 128 df<007E0001C1800301800703C00E03C00E01800E00000E00000E00000E00000E 0000FFFFC00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E 01C00E01C00E01C00E01C00E01C07F87F8151D809C17>12 D<007FC001C1C00303C00703C00E01 C00E01C00E01C00E01C00E01C00E01C00E01C0FFFFC00E01C00E01C00E01C00E01C00E01C00E01 C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C07FCFF8151D809C17 >I16 D<3C42818181423C0807759D1F>23 D<6060F0F0F8F86868080808080808101010 102020404080800D0C7F9C15>34 D<004000800100020006000C000C0018001800300030007000 600060006000E000E000E000E000E000E000E000E000E000E000E000E000600060006000700030 003000180018000C000C00060002000100008000400A2A7D9E10>40 D<80004000200010001800 0C000C000600060003000300038001800180018001C001C001C001C001C001C001C001C001C001 C001C001C0018001800180038003000300060006000C000C00180010002000400080000A2A7E9E 10>I<60F0F0701010101020204080040C7C830C>44 DI<60F0F0600404 7C830C>I<030007003F00C7000700070007000700070007000700070007000700070007000700 0700070007000700070007000700070007000F80FFF80D1C7C9B15>49 D<07C01830201C400C40 0EF00FF80FF807F8077007000F000E000E001C001C00380070006000C00180030006010C011801 10023FFE7FFEFFFE101C7E9B15>I<07E01830201C201C781E780E781E381E001C001C00180030 006007E00030001C001C000E000F000F700FF80FF80FF80FF00E401C201C183007E0101D7E9B15 >I<000C00000C00001C00003C00003C00005C0000DC00009C00011C00031C00021C00041C000C 1C00081C00101C00301C00201C00401C00C01C00FFFFC0001C00001C00001C00001C00001C0000 1C00001C0001FFC0121C7F9B15>I<300C3FF83FF03FC020002000200020002000200023E02430 2818301C200E000E000F000F000F600FF00FF00FF00F800E401E401C2038187007C0101D7E9B15 >I<60F0F0600000000000000000000060F0F06004127C910C>58 D<0006000000060000000600 00000F0000000F0000000F00000017800000178000001780000023C0000023C0000023C0000041 E0000041E0000041E0000080F0000080F0000180F8000100780001FFF80003007C0002003C0002 003C0006003E0004001E0004001E000C001F001E001F00FF80FFF01C1D7F9C1F>65 DI<001F808000E0618001801980070007800E0003801C0003801C 00018038000180780000807800008070000080F0000000F0000000F0000000F0000000F0000000 F0000000F0000000F0000000700000807800008078000080380000801C0001001C0001000E0002 00070004000180080000E03000001FC000191E7E9C1E>I70 D<001F808000E0618001801980070007800E0003801C0003801C00018038000180780000807800 008070000080F0000000F0000000F0000000F0000000F0000000F0000000F000FFF0F0000F8070 0007807800078078000780380007801C0007801C0007800E00078007000B800180118000E06080 001F80001C1E7E9C21>I73 D77 D80 D<07E0801C1980300580700380600180E00180E00080E00080 E00080F00000F800007C00007FC0003FF8001FFE0007FF0000FF80000F800007C00003C00001C0 8001C08001C08001C0C00180C00180E00300D00200CC0C0083F800121E7E9C17>83 D<7FFFFFC0700F01C0600F00C0400F0040400F0040C00F0020800F0020800F0020800F0020000F 0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F000000 0F0000000F0000000F0000000F0000000F0000000F0000000F0000001F800003FFFC001B1C7F9B 1E>I86 D<7FFFF07C01F07001E06003C06003C0400780400F80400F00401E00001E 00003C00007C0000780000F00000F00001E00003E00003C0100780100780100F00101F00301E00 203C00203C00607800E0F803E0FFFFE0141C7E9B19>90 DI<080810102020 40404040808080808080B0B0F8F8787830300D0C7A9C15>II<1FC0003070 00783800781C00301C00001C00001C0001FC000F1C00381C00701C00601C00E01C40E01C40E01C 40603C40304E801F870012127E9115>97 DI<07E00C3018 78307870306000E000E000E000E000E000E00060007004300418080C3007C00E127E9112>I<00 3F0000070000070000070000070000070000070000070000070000070000070003E7000C170018 0F00300700700700600700E00700E00700E00700E00700E00700E0070060070070070030070018 0F000C370007C7E0131D7E9C17>I<03E00C301818300C700E6006E006FFFEE000E000E000E000 60007002300218040C1803E00F127F9112>I<00F8018C071E061E0E0C0E000E000E000E000E00 0E00FFE00E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E007FE00F 1D809C0D>I<00038003C4C00C38C01C3880181800381C00381C00381C00381C001818001C3800 0C300013C0001000003000001800001FF8001FFF001FFF803003806001C0C000C0C000C0C000C0 6001803003001C0E0007F800121C7F9215>II<18003C00 3C0018000000000000000000000000000000FC001C001C001C001C001C001C001C001C001C001C 001C001C001C001C001C001C00FF80091D7F9C0C>I<00C001E001E000C0000000000000000000 00000000000FE000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E0 00E000E000E000E060E0F0C0F1C061803E000B25839C0D>IIIII<03F0000E1C00180600 300300700380600180E001C0E001C0E001C0E001C0E001C0E001C0600180700380300300180600 0E1C0003F00012127F9115>II<03C1000C3300180B00300F00700700700700E0 0700E00700E00700E00700E00700E00700600700700700300F00180F000C370007C70000070000 0700000700000700000700000700000700003FE0131A7E9116>II<1F9030704030C010 C010E010F8007F803FE00FF000F880388018C018C018E010D0608FC00D127F9110>I<04000400 040004000C000C001C003C00FFE01C001C001C001C001C001C001C001C001C001C101C101C101C 101C100C100E2003C00C1A7F9910>IIII<7F8FF00F03800F030007020003840001C8 0001D80000F00000700000780000F800009C00010E00020E000607000403801E07C0FF0FF81512 809116>II<7FFC70386038407040F040E041C003C0038007000F040E041C043C 0C380870087038FFF80E127F9112>II<6060F0F0F0F060600C047C9C15> 127 D E end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%PaperSize: A4 %%EndSetup %%Page: 11 1 11 0 bop 232 292 a Fq(Random)18 b(Generation)f(of)i(Unlab)r(elled)e(Com)n (binatorial)h(Structures)776 420 y Fo(P)o(aul)e(Zimmerm)n(ann)816 489 y Fn(INRIA)h(Lorraine)805 590 y(Octob)q(er)f(25,)e(1993)684 691 y([summary)g(b)o(y)h(Eithne)h(Murra)o(y])884 840 y Fp(Abstract)211 905 y Fr(A)i(systematic)h(metho)q(d)e(for)h(generating)h(unlab)q(elled)f(com) o(binatorial)e(structures)21 b(uniformly)16 b(at)149 955 y(random)9 b(is)h(presen)o(ted.)19 b(It)11 b(applies)f(to)h(structures)i(that)e(are)g (decomp)q(osable,)f(i.e.,)g(formally)e(sp)q(eci\014able)149 1005 y(b)o(y)h(grammars)e(in)o(v)o(olving)h(unions,)i(pro)q(ducts,)i (sequences,)h(m)o(ultisets)8 b(and)i(cycles.)18 b(All)9 b(suc)o(h)i (structures)149 1055 y(of)f(size)j Fc(n)e Fr(can)g(b)q(e)i(generated)f (uniformly)d(b)o(y)i(either)i(sequen)o(tial)e(algorithms)e(of)i(w)o (orst-case)i(arithmetic)149 1104 y(complexit)o(y)e Fb(O)q Fr(\()p Fc(n)434 1089 y Fj(2)453 1104 y Fr(\))j(or)f(b)o(y)g(\\b)q(oustrophedonic")h (algorithms)d(of)i(w)o(orst-case)i(complexit)o(y)c Fb(O)q Fr(\()p Fc(n)c Fr(log)g Fc(n)p Fr(\).)149 1154 y(The)15 b(random)e(generation)i(pro)q (cedures)h(are)g(deriv)o(ed)f(automatically)c(from)i(a)h(high)g(lev)o(el)h (description)149 1204 y(of)d(the)i(com)o(binatorial)d(structures.)20 b(An)14 b(implemen)o(tatio)o(n)d(of)i(this)g(system)h(in)f(the)h(computer)f (algebra)149 1254 y(system)g(Maple)h(is)g(brie\015y)g(describ)q(ed.)798 1388 y Fm(1.)25 b(In)o(tro)q(duction)50 1469 y Fn(Presen)o(ted)c(here)h(is)g (a)f(systematic)h(metho)q(d)f(for)g(generating)h(unlab)q(elled)i(com)o (binatorial)e(structures)g(at)0 1523 y(random.)j(Giv)o(en)18 b(a)f(grammar-lik)o(e)g(sp)q(eci\014cation)i(of)d(a)h(class)h Fe(C)h Fn(of)e(suc)o(h)h(structures,)f(there)g(is)g(a)g(metho)q(d)h(to)0 1577 y(automatically)d(pro)q(duce)h(pro)q(cedures)g(for)f(the)g(random)g (generation)g(of)g(ob)s(jects)f(in)i Fe(C)i Fn(of)c(a)h(\014xed)h(size)g Fk(n)p Fn(.)k(The)0 1631 y(analysis)e(of)g(the)f(lab)q(elled)k(case)c(has)h (already)g(b)q(een)h(done)f([1)o(].)27 b(The)18 b(unlab)q(elled)j(case)c(is)h (more)g(complicated)0 1685 y(b)q(ecause)e(of)f(the)g(symmetries)h(in)g(unlab) q(elled)i(ob)s(jects.)50 1740 y(The)h(sp)q(eci\014cation)j(language)d (consists)h(of)f(union,)i(cartesian)f(pro)q(duct,)g(sequence,)i(m)o(ultiset)e (and)f(cycle,)0 1794 y(as)h(w)o(ell)g(as)g(t)o(w)o(o)e(basic)j(initial)h(ob)s (jects:)29 b(the)20 b(structure)f Fk(\017)i Fn(of)e(size)i(0,)f(and)g Fk(Z)s Fn(,)h(an)f(atomic)g(no)q(de)g(of)g(size)h(1.)0 1848 y(Our)15 b(metho)q(d)g(can)g(b)q(e)g(used)g(on)g(an)o(y)f Fl(de)n(c)n(omp)n (osable)j Fn(class)e(of)f(ob)s(jects)g(that)g(can)h(b)q(e)g(sp)q(eci\014ed)i (b)o(y)d(using)i(these)0 1902 y(constructions)f(iterativ)o(ely)h(or)f (recursiv)o(ely)l(.)50 1958 y(T)o(ypical)h(examples)f(of)g(decomp)q(osable)h (classes)g(are)e(in)o(teger)h(partitions,)g(nec)o(klaces,)h(unlab)q(elled)i (trees)d(and)0 2011 y(forests,)d(random)h(mapping)h(patterns,)f(term)g(trees) g(under)h(asso)q(ciativ)o(e)g(and)f(comm)o(utativ)o(e)g(la)o(ws,)g(and)h (deriv)m(a-)0 2065 y(tion)k(trees)g(of)f(all)i(con)o(text-free)f(languages.) 28 b(As)18 b(an)g(example)h(of)e(a)h(sp)q(eci\014cation)h(consider)g(the)f (class)h Fe(H)f Fn(of)0 2119 y(unlab)q(elled)d(hierarc)o(hies,)f(that)e(are)g (de\014ned)h(as)f(non-plane)h(trees)f(in)h(whic)o(h)h(the)e(degrees)g(of)g (the)g(in)o(ternal)h(no)q(des)0 2173 y(are)i(alw)o(a)o(ys)f(at)h(least)g(2.) 20 b(W)l(e)15 b(de\014ne)h Fe(H)g Fn(with)g(the)f(sp)q(eci\014cation)i (language)f(b)o(y)647 2262 y Fe(H)d Fn(=)g Fk(Z)h Fn(+)c Fa(multiset)o Fn(\()p Fe(H)p Fk(;)e Fn(card)k Fe(\025)h Fn(2\))p Fk(:)0 2350 y Fn(\(Unlab)q(elled)18 b(hierarc)o(hies)e(are)f(relev)m(an)o(t)h(to)f (statistical)g(classi\014cation)i(theory)l(.\))836 2461 y Fm(2.)26 b(Coun)o(ting)50 2542 y Fn(If)c(w)o(e)g(kno)o(w)f(the)h(n)o(um)o(b)q(er)g(of) g(ob)s(jects)f Fk(c)799 2549 y Ff(n)843 2542 y Fn(in)i(a)e(decomp)q(osable)i (class)g Fe(C)h Fn(of)d(size)i Fk(n)p Fn(,)h(w)o(e)d(can)h(generate)0 2596 y(an)f(elemen)o(t)h(of)f(size)h Fk(n)g Fn(uniformly)g(at)f(random.)38 b(Lo)q(oking)22 b(at)e(the)i(ordinary)f(generating)h(functions)g(that)0 2650 y(corresp)q(ond)16 b(to)e(eac)o(h)h(construction)h(in)g(the)f(sp)q (eci\014cation)i(language,)e(w)o(e)g(get)g(the)g(follo)o(wing)h(theorem.)954 2749 y Fr(11)p eop %%Page: 12 2 12 1 bop 50 141 a Fi(Theorem)18 b Fn(1)e(\()p Fi(F)o(olk)h(theorem)h(of)g (combina)m(torial)e(anal)m(ysis)p Fn(\))p Fi(.)k Fl(Given)15 b(a)i(sp)n(e)n(ci\014c)n(ation)d Fn(\006)i Fl(for)h(a)0 195 y(class)f Fk(C)s Fl(,)g(a)h(set)f(of)h(e)n(quations)f(for)h(the)g(c)n(orr)n (esp)n(onding)e(gener)n(ating)h(functions)g(is)g(obtaine)n(d)h(automatic)n (al)r(ly)g(by)0 249 y(the)g(fol)r(lowing)e(tr)n(anslation)h(rules:)378 305 y Fg(8)378 342 y(>)378 355 y(>)378 367 y(>)378 380 y(>)378 392 y(>)378 405 y(>)378 417 y(>)378 430 y(>)378 442 y(>)378 455 y(>)378 467 y(>)378 479 y(>)378 492 y(<)378 567 y(>)378 579 y(>)378 592 y(>)378 604 y(>)378 616 y(>)378 629 y(>)378 641 y(>)378 654 y(>)378 666 y(>)378 679 y(>)378 691 y(>)378 704 y(>)378 716 y(:)435 337 y Fk(C)g Fn(=)d Fk(A)d Fn(+)g Fk(B)179 b Fn(=)-8 b Fe(\))42 b Fk(C)s Fn(\()p Fk(z)r Fn(\))12 b(=)h Fk(A)p Fn(\()p Fk(z)r Fn(\))d(+)g Fk(B)r Fn(\()p Fk(z)r Fn(\))435 391 y Fk(C)16 b Fn(=)d Fk(A)d Fe(\002)g Fk(B)179 b Fn(=)-8 b Fe(\))42 b Fk(C)s Fn(\()p Fk(z)r Fn(\))12 b(=)h Fk(A)p Fn(\()p Fk(z)r Fn(\))d Fe(\001)g Fk(B)r Fn(\()p Fk(z)r Fn(\))435 467 y Fk(C)16 b Fn(=)d Fa(sequence)o Fn(\()p Fk(A)p Fn(\))41 b(=)-8 b Fe(\))42 b Fk(C)s Fn(\()p Fk(z)r Fn(\))12 b(=)1182 437 y(1)p 1108 457 171 2 v 1108 499 a(1)e Fe(\000)h Fk(A)p Fn(\()p Fk(z)r Fn(\))435 584 y Fk(C)16 b Fn(=)d Fa(multiset)o Fn(\()p Fk(A)p Fn(\))41 b(=)-8 b Fe(\))42 b Fk(C)s Fn(\()p Fk(z)r Fn(\))12 b(=)h(exp)1180 512 y Fg( )1227 531 y Fh(1)1213 543 y Fg(X)1213 632 y Ff(k)q Fj(=1)1287 553 y Fn(1)p 1286 573 26 2 v 1286 615 a Fk(k)1316 584 y(A)p Fn(\()p Fk(z)1391 565 y Ff(k)1411 584 y Fn(\))1429 512 y Fg(!)435 706 y Fk(C)j Fn(=)d Fa(cycle)o Fn(\()p Fk(A)p Fn(\))113 b(=)-8 b Fe(\))42 b Fk(C)s Fn(\()p Fk(z)r Fn(\))12 b(=)1117 653 y Fh(1)1103 666 y Fg(X)1103 755 y Ff(k)q Fj(=1)1176 675 y Fk(')p Fn(\()p Fk(k)q Fn(\))p 1176 696 91 2 v 1209 737 a Fk(k)1279 706 y Fn(log)1434 675 y(1)p 1350 696 192 2 v 1350 737 a(1)e Fe(\000)g Fk(A)p Fn(\()p Fk(z)1503 724 y Ff(k)1524 737 y Fn(\))0 833 y Fl(wher)n(e)16 b Fk(')p Fn(\()p Fk(k)q Fn(\))g Fl(denotes)g(the)g(Euler)g(totient)g(function.)50 930 y Fn(Th)o(us,)f(to)g(coun)o(t)g(the)h(n)o(um)o(b)q(er)f(of)g(ob)s(jects)g (of)g(size)i Fk(n)e Fn(of)h(a)f(structure)g(giv)o(en)h(b)o(y)f(a)g(grammar)f (sp)q(eci\014cation,)0 984 y(w)o(e)i(can)h(use)g(its)g(corresp)q(onding)h(en) o(umerating)e(generating)h(function)h(that)e(is)h(built)h(up)f(from)f(the)g (grammar)0 1038 y(according)g(to)e(the)i(rules)f(of)g(the)h(theorem.)674 1152 y Fm(3.)25 b(Standard)19 b(Sp)q(eci\014cations)50 1232 y Fn(W)l(e)11 b(transform)f(eac)o(h)h(grammar)f(in)o(to)h(a)g(kind)h(of)f (Chomsky)g(Normal)g(form.)18 b(Th)o(us,)12 b(eac)o(h)f(union)h(and)g(pro)q (duct)0 1286 y(will)j(b)q(e)g(binary)l(,)f(w)o(e)f(use)h(unions)h(and)e(pro)q (ducts)h(in)h(place)f(of)f(sequences,)i(and)f(w)o(e)f(rewrite)h(m)o(ultiset)g (and)g(cycle)0 1340 y(using)i(the)g(p)q(oin)o(ting)g(op)q(erator,)e(\002,)i (where)g(\002)p Fk(A)f Fn(can)h(b)q(e)g(in)o(terpreted)g(as)f(p)q(oin)o(ting) i(at)d(an)o(y)h(of)g(the)h(atoms)e(of)h(a)0 1394 y(structure)g Fk(A)p Fn(.)20 b(Analytically)l(,)d(w)o(e)e(ha)o(v)o(e)298 1505 y Fk(C)g Fn(=)e(\002)p Fk(A)117 b Fn(=)-8 b Fe(\))117 b Fk(C)s Fn(\()p Fk(z)r Fn(\))12 b(=)h(\002)p Fk(A)p Fn(\()p Fk(z)r Fn(\))46 b(where)f(\002)p Fk(f)5 b Fn(\()p Fk(z)r Fn(\))13 b(=)g Fk(z)f Fe(\001)1513 1474 y Fk(d)p 1502 1495 47 2 v 1502 1536 a(dz)1554 1505 y(f)5 b Fn(\()p Fk(z)r Fn(\))p Fk(:)50 1612 y Fn(Using)16 b(the)f(generating)g(function)h(from)f(the)g(ab)q(o)o(v)o (e)g(theorem,)f(w)o(e)h(see)h(that)e(if)i Fk(A)d Fn(=)g Fa(multiset)n Fn(\()p Fk(B)r Fn(\),)i(then)461 1701 y(\002)p Fk(A)p Fn(\()p Fk(z)r Fn(\))d(=)h Fk(A)p Fn(\()p Fk(z)r Fn(\))d Fe(\002)g Fn(\(\002)p Fk(B)r Fn(\()p Fk(z)r Fn(\))h(+)f(\002)p Fk(B)r Fn(\()p Fk(z)1113 1683 y Fj(2)1133 1701 y Fn(\))g(+)g(\002)p Fk(B)r Fn(\()p Fk(z)1318 1683 y Fj(3)1338 1701 y Fn(\))f(+)i Fe(\001)d(\001)g(\001)e Fn(\))50 1793 y(W)l(e)13 b(will)i(rewrite)f(this)g (expression)g(using)g(a)g(new)f(op)q(erator)g(in)h(the)g(follo)o(wing)g(w)o (a)o(y:)k(\002)p Fk(A)c Fn(marks)f(an)g(atom)f(of)0 1847 y(an)i(ob)s(ject)f (of)g Fk(A)p Fn(.)19 b(When)14 b Fk(A)f Fn(=)g Fa(multiset)o Fn(\()p Fk(B)r Fn(\),)h(an)f(ob)s(ject)h(of)f Fk(A)g Fn(is)i(a)e(collection,) j(with)e(rep)q(etitions,)g(of)g(ob)s(jects)0 1901 y(of)i(B.)h(Th)o(us)f(w)o (e)h(can)g(think)g(of)g(marking)f(an)h(atom)f(of)g(an)h Fk(A)f Fn(ob)s(ject)g(as)h(really)g(marking)g(the)g(corresp)q(onding)0 1955 y(B)h(ob)s(ject,)f(so)g(w)o(e)h(w)o(ould)f(lik)o(e)i(to)e(sa)o(y)g(that) g(\002)p Fk(A)g Fn(=)g Fk(A)12 b Fe(\002)g Fn(\002)p Fk(B)21 b Fn(\(as)16 b(in)j(the)f(lab)q(elled)i(case\).)27 b(Ho)o(w)o(ev)o(er,)16 b(in)j(the)0 2009 y(unlab)q(elled)g(case)e(this)f(is)h(not)f(quite)h (accurate.)23 b(W)l(e)16 b(cannot)g(distinguish)i(b)q(et)o(w)o(een)f Fe(f)p Fk(b;)8 b(b;)g(c)p Fe(g)13 b Fn(with)j(the)h(\014rst)e Fk(b)0 2063 y Fn(mark)o(ed,)e(and)h(the)g(same)g(set)f(with)i(the)e(second)i Fk(b)e Fn(mark)o(ed)h(at)f(the)h(same)f(atom.)19 b(So)13 b(instead,)i(w)o(e)e (will)j(think)e(of)0 2116 y(marking)h(not)g(one)g Fk(b)p Fn(,)g(but)g(all)h (of)f(them)g(\\stac)o(k)o(ed")f(together.)19 b(Th)o(us,)c(\002)p Fk(A)e Fn(=)g Fk(stack)q Fn(\(\002\()p Fk(B)r Fn(\)\))d Fe(\002)h Fa(multiset)o Fn(\()p Fk(B)r Fn(\).)50 2172 y(W)l(e)16 b(denote)g(this)g (\\stac)o(king")f(function,)h(or)f(the)h Fl(diagonal)p Fn(,)f(b)o(y)h(\001.) 21 b(Then)16 b(is)g(is)h(easily)f(demonstrated)g(that)0 2226 y(the)f(generating)h(function)g(corresp)q(onding)g(to)e(\001)h(is)h(giv)o(en) g(b)o(y)f(the)g(follo)o(wing.)50 2323 y Fi(Theorem)j Fn(2)p Fi(.)i Fn(\001)p Fk(F)6 b Fn(\()p Fk(z)r Fn(\))12 b(=)h Fk(F)6 b Fn(\()p Fk(z)r Fn(\))k(+)h Fk(F)6 b Fn(\()p Fk(z)748 2306 y Fj(2)767 2323 y Fn(\))j(+)i Fk(F)6 b Fn(\()p Fk(z)916 2306 y Fj(3)935 2323 y Fn(\))k(+)g Fe(\001)e(\001)g(\001)50 2419 y Fn(Then)14 b(w)o(e)f(can)g(rewrite)h(our)f(expression)h(for)f(m)o(ultiset)h (as)f Fk(A)g Fn(=)g Fa(multiset)o Fn(\()p Fk(B)r Fn(\))f Fe(\))h Fn(\002)p Fk(A)g Fn(=)g(\001\002)p Fk(B)d Fe(\002)c Fk(A)p Fn(,)14 b(whic)o(h)0 2473 y(is)i(exactly)f(what)g(w)o(e)g(started)f(with.)50 2529 y(Giv)o(en)h(a)g(n)o(umeric)h(sequence)h Fe(f)p Fk(u)p Fn(\()p Fk(k)q Fn(\))p Fe(g)714 2513 y Fh(1)714 2540 y Ff(k)q Fj(=1)775 2529 y Fn(,)e(the)g Fl(gener)n(alise)n(d)g(diagonal)20 b Fn(is)15 b(de\014ned)i(b)o(y)750 2650 y(\001)788 2657 y Fh(f)p Ff(u)p Fj(\()p Ff(k)q Fj(\))p Fh(g)901 2650 y Fn(=)962 2597 y Fh(1)949 2609 y Fg(X)949 2699 y Ff(k)q Fj(=1)1017 2650 y Fk(u)p Fn(\()p Fk(k)q Fn(\)\001)1142 2631 y Fj(\()p Ff(k)q Fj(\))1187 2650 y Fk(:)954 2749 y Fr(12)p eop %%Page: 13 3 13 2 bop 0 141 a Fn(Com)o(binatorially)l(,)14 b(this)g(means)f(taking)g(a)f (w)o(eigh)o(ted)h(com)o(bination)h(of)f(diagonals.)19 b(Analytically)l(,)d (this)d(also)g(de-)0 195 y(\014nes)e(a)g(linear)h(op)q(erator)d(o)o(v)o(er)h (generating)h(functions)g(in)o(v)o(olving)h(a)f(w)o(eigh)o(ted)g(com)o (bination)g(of)f Fk(A)p Fn(\()p Fk(z)r Fn(\))p Fk(;)e(A)p Fn(\()p Fk(z)1834 179 y Fj(2)1852 195 y Fn(\))p Fk(;)g(:)g(:)g(:)325 307 y(C)15 b Fn(=)e(\001)459 314 y Fh(f)p Ff(u)p Fj(\()p Ff(k)q Fj(\))p Fh(g)559 307 y Fk(A)117 b Fn(=)-8 b Fe(\))117 b Fk(C)s Fn(\()p Fk(z)r Fn(\))12 b(=)h(\001)1092 314 y Fh(f)p Ff(u)p Fj(\()p Ff(k)q Fj(\))p Fh(g)1192 307 y Fk(A)p Fn(\()p Fk(z)r Fn(\))f(=)1359 254 y Fh(1)1345 266 y Fg(X)1345 356 y Ff(k)q Fj(=1)1413 307 y Fk(u)p Fn(\()p Fk(k)q Fn(\))p Fk(A)p Fn(\()p Fk(z)1575 288 y Ff(k)1595 307 y Fn(\))p Fk(:)50 422 y Fn(Th)o(us,)j(w)o(e)g (can)g(rewrite)g(our)g(expression)h(for)f(m)o(ultiset)g(as)487 503 y Fk(A)e Fn(=)g Fa(multiset)o Fn(\()p Fk(B)r Fn(\))f Fe(\))h Fn(\002)p Fk(A)p Fn(\()p Fk(z)r Fn(\))g(=)g Fk(A)p Fn(\()p Fk(z)r Fn(\))d Fe(\001)f Fn(\001)1267 510 y Fh(f)p Fj(1)p Fh(g)1320 503 y Fn(\002)p Fk(B)s Fn(\()p Fk(z)r Fn(\))p Fk(:)0 583 y Fn(W)l(e)15 b(also)g(\014nd)h(that)534 654 y Fk(A)d Fn(=)g Fa(cycle)o Fn(\()p Fk(B)r Fn(\))g Fe(\))g Fn(\002)p Fk(A)p Fn(\()p Fk(z)r Fn(\))g(=)g(\001)1118 661 y Fh(f)p Ff(')p Fj(\()p Ff(k)q Fj(\))p Fh(g)1246 623 y Fn(\002)p Fk(B)r Fn(\()p Fk(z)r Fn(\))p 1225 643 174 2 v 1225 685 a(1)c Fe(\000)i Fk(B)r Fn(\()p Fk(z)r Fn(\))1403 654 y Fk(:)50 746 y Fn(F)l(or)h(b)q(oth)i(m)o(ultiset)f (and)h(cycle,)g(w)o(e)f(can)g(deriv)o(e)h(similar)g(relations)g(when)g(w)o(e) e(ha)o(v)o(e)h(an)g(imp)q(osed)h(restriction)0 800 y(on)d(the)f(cardinalit)o (y)l(,)j(th)o(us)d(all)i(cardinalit)o(y)g(restrictions)f(are)f(also)h (expressible)h(in)g(terms)e(of)g(the)h(union,)h(pro)q(duct,)0 854 y(generalised)17 b(diagonal)f(and)f(p)q(oin)o(ting)h(op)q(erations.)814 949 y Fm(4.)26 b(Generation)50 1028 y Fn(Once)21 b(w)o(e)f(kno)o(w)f(ho)o(w)h (to)f(coun)o(t)h(the)h(n)o(um)o(b)q(er)f(of)g(ob)s(jects)f Fk(C)1160 1035 y Ff(n)1202 1028 y Fn(in)i(the)g(decomp)q(osable)g(class)f Fe(C)s Fn(,)h(w)o(e)f(can)0 1082 y(generate)d(ob)s(jects)g(of)h(size)g Fk(n)p Fn(.)28 b(The)17 b(generation)h(of)f(most)g(structures)h(is)g(the)f (same)h(here)g(as)f(in)i(the)e(lab)q(elled)0 1136 y(case,)c(and)f(so)h(w)o(e) f(will)i(only)f(brie\015y)h(discuss)g(the)e(t)o(w)o(o)g(main)h(algorithms.)18 b(Again,)c(details)f(can)g(b)q(e)g(found)g(in)g([1].)50 1191 y(Sa)o(y)18 b Fe(C)k Fn(=)d Fe(A)13 b(\002)g(B)q Fn(.)32 b(Then)19 b Fk(C)567 1198 y Ff(n)608 1191 y Fn(=)663 1158 y Fg(P)707 1202 y Ff(n)737 1191 y Fk(A)771 1198 y Ff(k)791 1191 y Fk(B)825 1198 y Ff(n)p Fh(\000)p Ff(k)912 1191 y Fn(and)g(th)o(us)g(Pr)o(\()p Fk(K)j Fn(=)d Fk(k)q Fn(\))g(=)g Fk(a)1429 1198 y Ff(k)1450 1191 y Fk(b)1470 1198 y Ff(n)p Fh(\000)p Ff(k)1536 1191 y Fk(=c)1579 1198 y Ff(n)1601 1191 y Fn(.)32 b(T)l(o)18 b(generate)h(an)0 1245 y(ob)s(ject)14 b(in)h Fe(C)h Fn(of)e(size)h Fk(n)f Fn(using)h(the)f Fl(se)n(quential)k Fn(algorithm,)c(w)o(e)g(randomly)g(pic)o(k)h(a)f(n)o(um)o (b)q(er)h(b)q(et)o(w)o(een)f(0)g(and)g Fk(c)1915 1252 y Ff(n)1937 1245 y Fn(,)0 1298 y(and)i(then)h(w)o(e)f(sequen)o(tially)l(,)i(\\from)d(the) h(left",)g(add)g(up)h(the)f(probabilities)j(for)c(increasing)j(v)m(alues)f (of)f Fk(k)h Fn(un)o(til)0 1352 y(w)o(e)e(\014nd)g(the)h(in)o(terv)m(al)g(in) g(whic)o(h)f(our)g(random)g(n)o(um)o(b)q(er)g(lies.)21 b(F)l(or)15 b(that)f Fk(k)q Fn(,)h(w)o(e)g(then)g(recursiv)o(ely)h(generate)f(an)0 1406 y(elemen)o(t)h(of)f(size)h Fk(k)g Fn(in)g Fe(A)g Fn(and)f(an)g(ob)s (ject)g(of)f(size)j Fk(n)10 b Fe(\000)g Fk(k)17 b Fn(in)f Fe(B)q Fn(.)50 1461 y(Random)h(generation)g(of)f(a)h(pro)q(duct)g(using)h(the)f (sequen)o(tial)h(algorithm)f(corresp)q(onds)g(to)f(calculating)j(the)0 1515 y(path)c(length)h(of)f(the)g(corresp)q(onding)h(parse)f(tree)g(for)g (the)g(pro)q(duct,)g(and)g(th)o(us)g(is)h(kno)o(wn)f(to)f(ha)o(v)o(e)h(w)o (orst)f(case)0 1569 y(complexit)o(y)i Fe(O)q Fn(\()p Fk(n)313 1552 y Fj(2)332 1569 y Fn(\).)50 1623 y(If)e(instead,)h(w)o(e)e(use)i(the)f Fl(Boustr)n(ophe)n(donic)j Fn(algorithm,)c(w)o(e)h(can)g(reduce)h(the)f(w)o (orst)f(case)h(complexit)o(y)h(from)0 1677 y Fe(O)q Fn(\()p Fk(n)82 1660 y Fj(2)101 1677 y Fn(\))d(to)f Fe(O)q Fn(\()p Fk(n)d Fn(log)g Fk(n)p Fn(\).)19 b(F)l(or)11 b(this)i(algorithm,)f(instead)h (of)e(starting)h(\\on)f(the)i(left")f(and)g(sequen)o(tially)i(adding)e(up)0 1731 y(probabilities)j(to)e(determine)h(whic)o(h)f(v)m(alue)i(of)d Fk(k)i Fn(to)e(use,)i(w)o(e)e(\014rst)h(start)f(at)g(the)h(left,)g(then)h (the)f(righ)o(t,)f(and)i(k)o(eep)0 1785 y(alternating)f(bac)o(k)g(and)g (forth)g(un)o(til)h(w)o(e)f(ha)o(v)o(e)f(either)i(found)f(the)g(v)m(alue)i (of)d Fk(k)i Fn(or)f(the)g(v)m(alue)h(of)f Fk(n)6 b Fe(\000)g Fk(k)q Fn(,)13 b(whic)o(hev)o(er)0 1839 y(is)j(smaller.)k(\()p Fl(Boustr)n(ophe)n(donic)e Fn(means)d(\\turning)h(lik)o(e)g(o)o(xen)f(in)h (ploughing")h(\(W)l(ebster\).\))i(If)c(either)h(v)m(alue)g(is)0 1893 y(small,)i(w)o(e)f(will)j(\014nd)e(it)f(quic)o(kly)l(,)j(and)d(in)h(the) g(w)o(orst)e(case)h(\(when)h Fk(n)f Fn(=)f Fk(k)q Fn(\),)i(the)f(problem)h (will)h(b)q(e)f(split)h(in)o(to)0 1947 y(t)o(w)o(o)d(subproblems)i(of)f (equal)h(size,)g(whic)o(h)g(is)f(also)h(an)f(adv)m(an)o(tage.)25 b(Analysis)18 b(of)f(this)g(problem)h(giv)o(es)g(us)f(the)0 2001 y(follo)o(wing)f(theorem.)50 2082 y Fi(Theorem)i Fn(3)e(\()p Fi(Boustr)o(ophedonic)h(genera)m(tion,)g(unlabelled)j(case)p Fn(\))p Fi(.)f Fl(A)o(ny)d(class)f(of)i(unlab)n(el)r(le)n(d)0 2136 y(structur)n(es)22 b(that)g(admits)g(a)g(\(p)n(ossibly)e(r)n(e)n (cursive\))h(sp)n(e)n(ci\014c)n(ation)e(in)j(terms)f(of)h(the)g(given)f(c)n (onstructions)f(is)0 2190 y(susc)n(eptible)15 b(to)i(a)f(r)n(andom)h(gener)n (ation)e(algorithm)i(of)f(arithmetic)h(c)n(omplexity)g Fe(O)q Fn(\()p Fk(n)8 b Fn(log)g Fk(n)p Fn(\))p Fl(.)50 2272 y Fn(A)13 b(cost)f(analysis)i(of)f(b)q(oth)g(algorithms)g(on)g(a)o(v)o(erage)f(case)h (problems)g(suggests)g(that)f(while)j(the)e(Boustrophe-)0 2326 y(donic)h(algorithm)e(has)h(b)q(etter)f(w)o(orst)f(case)i(b)q(eha)o(viour,)g (in)h(the)e(sequen)o(tial)i(algorithm)f(w)o(e)f(can)h(tak)o(e)f(adv)m(an)o (tage)0 2380 y(of)i(optimisation)h(strategies)f(suggested)h(b)o(y)f(the)h (cost)f(calculus,)i(and)f(it)g(app)q(ears)g(that)f(most)f(classical)j (classes)0 2433 y(of)f(structures)f(can)i(b)q(e)f(generated)h(in)g(time)f (asymptotic)g(to)1067 2416 y Fj(1)p 1067 2423 17 2 v 1067 2449 a(2)1089 2433 y Fk(n)8 b Fn(log)g Fk(n)15 b Fn(or)g(sometimes)g(ev)o(en)g Fe(O)q Fn(\()p Fk(n)p Fn(\))g(on)h(a)o(v)o(erage.)50 2488 y(F)l(or)c(unlab)q (elled)k(ob)s(jects,)c(w)o(e)g(ha)o(v)o(e)h(the)f(new)h(problem)h(of)e (generating)h(elemen)o(ts)g(that)f(use)h(the)g(\001)f(op)q(erator.)0 2542 y(Sa)o(y)k Fe(G)g Fn(=)e(\001)p Fe(F)5 b Fn(.)21 b(Then)16 b Fk(G)444 2549 y Ff(n)480 2542 y Fn(=)529 2510 y Fg(P)573 2553 y Ff(k)q Fh(j)p Ff(n)632 2542 y Fk(F)661 2549 y Ff(n=k)719 2542 y Fn(,)f(and)h(so)g(the)g(probabilit)o(y)h(that)e Fe(G)k Fn(pro)q(duces)d(a)g Fk(k)q Fn(-stac)o(k)f(of)h(size)g Fk(n)g Fn(is)0 2596 y Fk(F)29 2603 y Ff(n=k)87 2596 y Fk(=G)146 2603 y Ff(n)168 2596 y Fn(.)k(No)o(w)13 b(that)g(w)o(e)h(kno)o(w)g(the)g (distribution)i(of)d(probabilities,)j(w)o(e)e(can)g(use)h(a)e(sequen)o(tial)j (algorithm)e(to)0 2650 y(c)o(ho)q(ose)e(the)g(appropriate)h(v)m(alue)g(for)e (the)i(stac)o(k)e(size)i Fk(k)q Fn(,)g(and)f(hence)h(generate)f(the)g(elemen) o(t.)20 b(It)12 b(is)h(imp)q(ortan)o(t)f(to)954 2749 y Fr(13)p eop %%Page: 14 4 14 3 bop 0 141 a Fn(note)14 b(that)g(generating)h(\001)p Fe(F)j Fn(has)d(the)f(same)g(complexit)o(y)i(as)e(generating)g Fe(F)5 b Fn(,)14 b(since)i(w)o(e)e(only)h(need)g(to)f(consider)0 195 y(at)h(most)f(the)h(n)o(um)o(b)q(er)h(of)f(divisors)h(of)e Fk(n)p Fn(.)761 286 y Fm(5.)26 b(Implemen)o(tation)50 365 y Fn(This)18 b(system)g(has)f(b)q(een)i(implemen)o(ted)h(in)e(the)g(Maple)g (language)g(b)o(y)g(P)l(.)g(Zimmermann)g(and)g(E.)f(Murra)o(y)0 419 y(\(for)f(a)g(detailed)i(description)g(of)e(a)g(preliminary)i(v)o (ersion,)f(see)g([2)o(]\).)23 b(The)17 b(program)e(tak)o(es)h(a)g(grammar)f (of)h(an)0 473 y(unlab)q(elled)k(\(or)d(lab)q(elled\))i(structure)e(and)h (rewrites)f(it)h(in)o(to)f(the)g(standard,)g(Chomsky-Normal)g(form)f(using)0 527 y(only)21 b(union,)g(pro)q(duct,)h(p)q(oin)o(ting)f(and)f(stac)o(king.)34 b(Then,)21 b(for)f(eac)o(h)g(non-terminal)h(in)g(the)f(new)g(grammar,)0 581 y(it)g(creates)f(a)g(function)i(based)f(on)f(a)g(pre-existing)i(template) f(to)f(coun)o(t)g(ob)s(jects)g(of)g(size)i Fk(n)e Fn(de\014ned)i(b)o(y)f(the) 0 635 y(non-terminal,)15 b(and)f(another)g(function)g(to)g(dra)o(w)f(an)h(ob) s(ject)f(of)h(size)h Fk(n)f Fn(de\014ned)h(b)o(y)f(the)g(non-terminal.)21 b(These)0 689 y(functions)16 b(are)f(stored)g(in)h(tables,)f(and)h(called)h (when)f(the)f(user)g(asks)g(to)g(coun)o(t)g(or)g(generate)g(an)g(ob)s(ject)g (of)g(the)0 743 y(original)h(sp)q(eci\014cation.)50 797 y(F)l(or)k(example,)i (with)f(the)g(grammar)e(C)i(=)g(Union\(A,B\),)f(the)h(program)f(will)i (create)f(a)f(function)h(gC)g(to)0 851 y(generate)15 b(C)g(ob)s(jects:)45 917 y(gC)g(:=)g(pro)q(cedure\(n)h(:)k(in)o(teger\))129 971 y Fk(U)g Fn(:=Uniform\([0)p Fk(;)8 b Fn(1]\);)129 1025 y(if)15 b Fk(U)j(<)13 b(a)291 1032 y Ff(n)314 1025 y Fk(=c)357 1032 y Ff(n)394 1025 y Fn(then)i(gA\(n\))g(else)h(gB\(n\))f(\014)45 1079 y(end.)50 1146 y(Some)i(examples)h(that)e(ha)o(v)o(e)g(b)q(een)i (implemen)o(ted)h(using)f(this)f(program)f(include)j(2-3)e(trees,)g(binary)g (trees)0 1200 y(of)i(\014xed)i(or)e(b)q(ounded)j(heigh)o(t,)f(arithmetic)f (expressions)h(of)f(one)g(v)m(ariable)h(and)f(circuits)h(with)g(resistors)e (in)0 1254 y(parallel)e(and)e(series.)21 b(F)l(or)14 b(instance,)i(the)f (grammar)f(sp)q(eci\014cation)j(for)e(binary)g(trees)g(of)g(heigh)o(t)h Fe(\024)d Fn(3)i(is)42 1337 y Fe(f)p Fk(B)99 1344 y Fj(0)130 1337 y Fn(=)e Fk(Z)q(;)8 b(B)265 1344 y Fj(1)296 1337 y Fn(=)13 b(Union)q(\()p Fk(Z)q(;)8 b Fn(Pro)q(d)n(\()p Fk(B)683 1344 y Fj(0)702 1337 y Fk(;)g(B)757 1344 y Fj(0)775 1337 y Fn(\)\))p Fk(;)692 1404 y(B)726 1411 y Fj(2)757 1404 y Fn(=)13 b(Union)q(\()p Fk(Z)q(;)8 b Fn(Pro)q(d)o(\()p Fk(B)1145 1411 y Fj(1)1164 1404 y Fk(;)g(B)1219 1411 y Fj(1)1237 1404 y Fn(\)\))p Fk(;)g(B)1328 1411 y Fj(3)1358 1404 y Fn(=)13 b(Union)q(\()p Fk(Z)q(;)8 b Fn(Pro)q(d)o(\()p Fk(B)1746 1411 y Fj(2)1764 1404 y Fk(;)g(B)1819 1411 y Fj(2)1838 1404 y Fn(\)\))p Fe(g)p Fk(:)817 1496 y Fm(6.)25 b(Conclusion)50 1574 y Fn(This)14 b(systematic)g(approac)o(h)g(to)g(random)f (generation)h(not)g(only)h(handles)g(widely)h(di\013eren)o(t)e(problems)h (that)0 1628 y(ha)o(v)o(e)e(b)q(een)i(studied)g(in)g(detail)g(elsewhere)g(on) f(an)g(individual)j(basis,)d(but)g(it)g(also)g(in)h(some)e(cases)h(impro)o(v) o(es)g(the)0 1682 y(w)o(orst)e(case)h(b)q(ounds)h(previously)h(kno)o(wn.)k(F) l(or)13 b(example,)h(the)f(b)q(oustrophedonic)i(algorithm)e(giv)o(es)h Fe(O)q Fn(\()p Fk(n)8 b Fn(log)g Fk(n)p Fn(\))0 1736 y(w)o(orst)14 b(case)i(time)g(to)f(all)h(unam)o(biguous)h(con)o(text-free)e(languages,)g (whereas)h(the)g(b)q(est)g(previous)g(b)q(ound)h(\(due)0 1790 y(to)12 b(Hic)o(k)o(ey)i(and)f(Cohen\))f(is)i Fe(O)q Fn(\()p Fk(n)567 1774 y Fj(2+)p Ff(\017)625 1790 y Fn(\).)19 b(F)l(urther)12 b(areas)h(of)f(researc)o(h)h(in)o(v)o(olv)o(e)g(extending)h(the)f(system)f (to)h(include)0 1844 y(p)q(o)o(w)o(ersets,)18 b(and)g(to)f(consider)i(the)f Fl(unr)n(anking)j Fn(problem:)27 b(giv)o(en)18 b(a)g(structure)g Fk(A)p Fn(,)g(t)o(w)o(o)f(in)o(tegers)h Fk(n)g Fn(and)h(1)e Fe(\024)0 1898 y Fk(i)c Fe(\024)g Fk(A)111 1905 y Ff(n)134 1898 y Fn(,)i(output)h(the)f Fk(i)p Fn(th)g(ob)s(ject)g(of)h(size)g Fk(n)g Fn(in)g Fk(A)p Fn(.)21 b(If)16 b(w)o(e)f(could)i(do)e(this,)h(w)o(e)f (w)o(ould)h(b)q(e)g(able)h(to)e(generate)g(all)0 1952 y(ob)s(jects)g(of)f(a)h (giv)o(en)h(size)g(v)o(ery)f(e\016cien)o(tly)l(.)841 2039 y Fp(Bibliograp)o(h)o(y)0 2114 y Fr([1])20 b(Fla)r(jolet)12 b(\(Philipp)q(e\),) g(Zimmerm)o(an)e(\(P)o(aul\),)i(and)h(V)m(an)f(Cutsem)h(\(Bernard\).)h({)i(A) d(calculus)g(for)f(the)i(random)d(gener-)65 2164 y(ation)g(of)h(lab)q(elled)f (com)o(binatorial)e(structures.)15 b Fd(The)n(or)n(etic)n(al)d(Computer)h (Scienc)n(e)p Fr(,)f(v)o(ol.)f(132,)g(n)1568 2168 y(\027)1599 2164 y(1-2,)h Fc(1994)p Fr(,)f(pp.)g(1{35.)0 2214 y([2])20 b(Zimmerm)o(ann)14 b(\(P)o(aul\).)j({)29 b(Ga)-5 b(\177)-16 b(\020a:)25 b(A)17 b(pac)o(k)n(age)g(for)h(the)g(random)e(generation)i(of)f (com)o(binatorial)d(structures.)20 b Fd(The)65 2264 y(Maple)15 b(T)m(e)n(chnic)n(al)f(Newsletter)p Fr(,)e(v)o(ol.)g(1,)i(n)724 2268 y(\027)754 2264 y(1,)g(Spring)f Fc(1994)p Fr(.)954 2749 y(14)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF