%!PS (but not EPSF; comments have been disabled) %DVIPSCommandLine: dvips tesis1.dvi -o %DVIPSParameters: dpi=600, compressed, comments removed %DVIPSSource: TeX output 1998.05.19:1351 /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 TeXDict begin 40258431 52099146 1000 600 600 (tesis1.dvi) @start /Fa 2 49 df0 D<13E0EA01F0EA03F8A3EA07F0A313E0 A2120F13C0A3EA1F80A21300A25A123EA35AA3127812F8A25A12100D1E7D9F13>48 D E /Fb 1 108 df107 D E /Fc 1 95 df<5AEA0380EA0FE0EA1EF0EA3838EAF01EEA40 040F077A9C1C>94 D E /Fd 4 51 df<1306130C13181330136013E0EA01C0EA0380A2EA 07005A120E121EA2121C123CA35AA512F85AAB7E1278A57EA3121C121EA2120E120F7EEA 0380A2EA01C0EA00E0136013301318130C13060F3B7AAB1A>40 D<12C012607E7E7E120E 7EEA0380A2EA01C013E0120013F0A213701378A3133CA5133E131EAB133E133CA51378A3 137013F0A213E0120113C0EA0380A2EA0700120E120C5A5A5A5A0F3B7DAB1A>I<133813 78EA01F8121F12FE12E01200B3AB487EB512F8A215267BA521>49 D<13FF000313E0380E03F0381800F848137C48137E00787F12FC6CEB1F80A4127CC7FC15 005C143E147E147C5C495A495A5C495A010EC7FC5B5B903870018013E0EA018039030003 0012065A001FB5FC5A485BB5FCA219267DA521>I E /Fe 9 116 df61 D101 DII<133EEA07FEA2EA007CA213FCA25B A21201A25BA21203EC07809038E01FC0EC38600007EB61E014C3EBC187EBC307D80FC613 C09038CC038001B8C7FC13E0487E13FEEB3F80EB0FC0486C7E1303003E1460A2127EECC0 C0127CECC18012FC903801E30038F800FE0070137C1B297CA723>107 D<137CEA0FFCA2EA00F8A21201A213F0A21203A213E0A21207A213C0A2120FA21380A212 1FA21300A25AA2123EA2127EA2EA7C18A3EAF830A21320EA786013C0EA3F80EA0F000E29 7EA715>I<3907801FC0390FE07FF03918F0E0F83930F1807CEBFB00D860FE133C5B5B00 C1147C5B1201A248485BA34A5AEA07C01660EC03E0A23A0F8007C0C0A2EDC180913803C3 00D81F0013C7EC01FE000EEB00F8231B7D9929>110 DI115 D E /Ff 13 115 df<9339FF8001C0030F13E0037F9038F80380913A01 FF807E07913A07F8000F0FDA1FE0EB079FDA3F80903803BF0002FFC76CB4FCD901FC8049 5A4948157E495A495A4948153E017F163C49C9FC5B1201484816385B1207485A1830121F 4993C7FCA2485AA3127F5BA312FF90CCFCA41703A25F1706A26C160E170C171C5F6C7E5F 001F5E6D4A5A6C6C4A5A16076C6C020EC8FC6C6C143C6C6C5C6CB4495A90393FE00FC001 0FB5C9FC010313FC9038007FC03A3D7CBA3B>67 D<0103B812E05BA290260007F8C7123F 4B140FF003C0140F18015DA2141FA25D1980143FA25D1760027F14E095C7FC92C75AA24A 1301A24A495A16070101141F91B6FC94C8FCA2903903FC001F824A130EA21307A24A130C A2010F141CA24A90C9FCA2131FA25CA2133FA25CA2137FA291CBFC497EB612C0A33B397D B835>70 DI<0107B512FCA216F890390007F8005D A2140FA25DA2141FA25DA2143FA25DA2147FA292C7FCA25CA25CA21301A25CA21303A25C A21307A25CA2130FA25CA2131FA25CA2133FA25CA2137FA291C8FC497EB6FCA326397DB8 24>73 D<902603FFF893383FFF80496081D900079438FF80000206DC01BFC7FCA2020E4C 5A1A7E020C1606190CDA1C7E16FE4F5A02181630A20238166162023016C1F00181DA703F 158395380303F002601506A202E0ED0C076202C01518183001016D6C140F06605B028015 C0A20103923801801FDD03005B140092380FC00649173F4D91C8FC01065DA2010E4B5B4D 137E130C6F6C5A011C17FEDCE1805B011802E3C7FCA2013802E6130104EC5C1330ED03F8 017016034C5C01F05CD807FC4C7EB500E0D9C007B512F01680150151397CB851>77 D<4BB4FC031F13F09238FE01FC913903F0007EDA07C0EB1F80DA1F80EB0FC0023EC7EA07 E002FCEC03F0495A4948EC01F8495A4948EC00FC495A49C912FE49167E13FE49167F1201 485AA2485AA2120F5B001F17FFA2485AA34848ED01FEA400FFEE03FC90C9FCA2EF07F8A2 EF0FF0A218E0171F18C0EF3F806C167F180017FE4C5A6C6C5D1603001F4B5A6D4A5A000F ED1F806C6C4AC7FC6D147E0003EC01F8D801FC495AD8007EEB0FC090263F807FC8FC9038 07FFF801001380383D7CBA3F>79 D<0003B812FEA25A903AF8003FC00101C0913880007E 4848163C90C7007F141C121E001C92C7FCA2485CA200305C007017180060130112E0485C A21403C716005DA21407A25DA2140FA25DA2141FA25DA2143FA25DA2147FA292C9FCA25C A25CA21301A25CA21303A25CEB0FFC003FB6FC5AA237397EB831>84 D<16F8ED03FEED0F8792381F0F80ED3E3F167F157CA215FC1700161C4A48C7FCA414035D A414075DA20107B512F0A39026000FE0C7FC5DA4141F5DA4143F92C8FCA45C147EA514FE 5CA413015CA4495AA45C1307A25C121E123F387F8F80A200FF90C9FC131E12FEEA7C3CEA 7878EA1FF0EA07C0294C7CBA29>102 DI107 D110 D<90390F8003F090391FE00FFC903939F03C1F903A70F870 0F80903AE0FDE007C09038C0FF80030013E00001491303018015F05CEA038113015CA2D8 00031407A25CA20107140FA24A14E0A2010F141F17C05CEE3F80131FEE7F004A137E16FE 013F5C6E485A4B5A6E485A90397F700F80DA383FC7FC90387E1FFCEC07E001FEC9FCA25B A21201A25BA21203A25B1207B512C0A32C3583A42A>112 D<3903E001F83907F807FE39 0E3C1E07391C3E381F3A183F703F800038EBE07F0030EBC0FF00705B00601500EC007E15 3CD8E07F90C7FCEAC07EA2120013FE5BA312015BA312035BA312075BA3120F5BA3121F5B 0007C9FC21267EA425>114 D E /Fg 3 82 df67 D76 D<923801FFC0031F13F8037F13FE0203B6FC91260FE01F138091261E000313C00278 010013E04A147FD903C0EC3FF04948141F49C8EA0FF8131E491507137C49ED03FC485AA2 485A48481501A2120F485AA290C9FC5AA24817F8127EA2170312FE18F0A3EF07E0A26C17 C0170F18806DED1F00127F6D153E6D5D6C6C130F01FC013E5B3B1FFF01F801F06CD9FFE0 5B6C91388003C000014948485A26007FE049C7FC90C8121E163816F0ED03E0ED0780033E C8FCEC0FFC0003B500E0140E000F0280143E4801FCC8127C48D9FF8014FC000102F014F8 D8000F01FEEB01F00101D9FFC013E0D9003F9038FC03C0020790B5120002005C031F13F8 030113C0374577BA44>81 D E /Fh 31 122 df<387FFFF8A2B5FCA214F0150579941E> 45 D 67 D71 D<0103B512F8A390390007F8005DA2140FA25DA2141FA25DA2143FA25DA2 147FA292C7FCA25CA25CA21301A25CA21303A25CA21307A25CA2130FA25CA2131FA25CA2 133FA25CA2137FA291C8FC497EB6FCA25C25397CB820>73 D<902607FFF8923807FFF061 4F13E0D9000FEFF0004F5AA2021F167FF1EFC0141DDA1CFCEC01CF023C16DF9538039F80 0238ED071FA20278ED0E3F97C7FC0270151CA202F04B5AF0707E14E0037E14E0010117FE 4D485A02C0EC0380A20103ED0701610280140EA20107ED1C0305385B14006F1370491607 05E05B010EEC01C0A2011E913803800F61011CEC0700A2013C020E131F4C5C1338ED1FB8 0178163F04F091C8FC01705CA201F04A5B187E00015DD807F816FEB500C09039007FFFFC 151E150E4C397AB84A>77 D81 D<0007B812E0A25AD9F800EB001F01C049EB07C0485AD900011403121E001C5C003C1780 1403123800785C00701607140700F01700485CA2140FC792C7FC5DA2141FA25DA2143FA2 5DA2147FA292C9FCA25CA25CA21301A25CA21303A25CA21307A25CA2130FA25CEB3FF000 7FB512F8B6FCA2333971B83B>84 D<14F8EB07FE90381F871C90383E03FE137CEBF80112 0148486C5A485A120FEBC001001F5CA2EA3F801403007F5C1300A21407485C5AA2140F5D 48ECC1C0A2141F15831680143F1587007C017F1300ECFF076C485B9038038F8E391F0F07 9E3907FE03FC3901F000F0222677A42A>97 D<133FEA1FFFA3C67E137EA313FE5BA31201 5BA312035BA31207EBE0F8EBE7FE9038EF0F80390FFC07C013F89038F003E013E0D81FC0 13F0A21380A2123F1300A214075A127EA2140F12FE4814E0A2141F15C05AEC3F80A21500 5C147E5C387801F8007C5B383C03E0383E07C0381E1F80D80FFEC7FCEA01F01C3B77B926 >I<147F903803FFC090380FC1E090381F0070017E13784913383901F801F83803F00312 0713E0120FD81FC013F091C7FC485AA2127F90C8FCA35A5AA45AA3153015381578007C14 F0007EEB01E0003EEB03C0EC0F806CEB3E00380F81F83803FFE0C690C7FC1D2677A426> II<147F903803FFC090380FC1E090383F00F0017E13785B485A485A485A120F4913 F8001F14F0383F8001EC07E0EC1F80397F81FF00EBFFF891C7FC90C8FC5A5AA55AA21530 007C14381578007E14F0003EEB01E0EC03C06CEB0F806CEB3E00380781F83803FFE0C690 C7FC1D2677A426>IIIII<150E153F157FA3157E151C 1500ABEC1F80EC7FC0ECF1F0EB01C090380380F813071401130F130E131EEB1C03133C01 3813F0A2EB0007A215E0A2140FA215C0A2141FA21580A2143FA21500A25CA2147EA214FE A25CA21301A25CA213035C121C387E07E0A238FE0FC05C49C7FCEAF83EEA787CEA3FF0EA 0FC0204883B619>I108 DII<147F903803FFC090380FC1F09038 1F00F8017E137C5B4848137E4848133E0007143F5B120F485AA2485A157F127F90C7FCA2 15FF5A4814FEA2140115FC5AEC03F8A2EC07F015E0140F007C14C0007EEB1F80003EEB3F 00147E6C13F8380F83F03803FFC0C648C7FC202677A42A>I<9039078007C090391FE03F F090393CF0787C903938F8E03E9038787FC00170497EECFF00D9F0FE148013E05CEA01E1 13C15CA2D80003143FA25CA20107147FA24A1400A2010F5C5E5C4B5A131F5EEC80035E01 3F495A6E485A5E6E48C7FC017F133EEC70FC90387E3FF0EC0F8001FEC9FCA25BA21201A2 5BA21203A25B1207B512C0A3293580A42A>II<3903C003F0390FF01FFC391E783C0F381C7C703A3C3EE03F8038383FC0EB7F800078 150000701300151CD8F07E90C7FCEAE0FE5BA2120012015BA312035BA312075BA3120F5B A3121F5BA3123F90C9FC120E212679A423>I<14FE903807FF8090380F83C090383E00E0 4913F00178137001F813F00001130313F0A215E00003EB01C06DC7FC7FEBFFC06C13F814 FE6C7F6D13807F010F13C01300143F141F140F123E127E00FE1480A348EB1F0012E06C13 3E00705B6C5B381E03E06CB45AD801FEC7FC1C267AA422>II<13F8D803FEEB01C0D8078FEB03E0390E0F8007121E 121C0038140F131F007815C01270013F131F00F0130000E015805BD8007E133FA201FE14 005B5D120149137EA215FE120349EBFC0EA20201131E161C15F813E0163CD9F003133814 070001ECF07091381EF8F03A00F83C78E090393FF03FC090390FC00F00272679A42D>I< 01F0130ED803FC133FD8071EEB7F80EA0E1F121C123C0038143F49131F0070140FA25BD8 F07E140000E08013FEC6485B150E12015B151E0003141C5BA2153C000714385B5DA35DA2 4A5A140300035C6D48C7FC0001130E3800F83CEB7FF8EB0FC0212679A426>I<01F01507 D803FC903903801F80D8071E903907C03FC0D80E1F130F121C123C0038021F131F49EC80 0F00701607A249133FD8F07E168000E0ED000313FEC64849130718000001147E5B03FE5B 0003160E495BA2171E00070101141C01E05B173C1738A217781770020314F05F00030107 13016D486C485A000190391E7C07802800FC3C3E0FC7FC90393FF81FFE90390FE003F032 2679A437>I<903907E007C090391FF81FF89039787C383C9038F03E703A01E01EE0FE38 03C01F018013C0D8070014FC481480000E1570023F1300001E91C7FC121CA2C75AA2147E A214FEA25CA21301A24A1370A2010314F016E0001C5B007E1401010714C000FEEC038001 0F1307010EEB0F0039781CF81E9038387C3C393FF03FF03907C00FC027267CA427>I<13 F0D803FCEB01C0D8071EEB03E0D80E1F1307121C123C0038140F4914C01270A249131FD8 F07E148012E013FEC648133F160012015B5D0003147E5BA215FE00075C5BA214015DA314 035D14070003130FEBF01F3901F87FE038007FF7EB1FC7EB000F5DA2141F003F5C48133F 92C7FC147E147C007E13FC387001F8EB03E06C485A383C1F80D80FFEC8FCEA03F0233679 A428>I E /Fi 7 117 df65 D97 D<13FFB5FCA412077EAF4AB47E020F13F0023F13FC9138FE03FFDAF000 13804AEB7FC00280EB3FE091C713F0EE1FF8A217FC160FA217FEAA17FCA3EE1FF8A217F0 6E133F6EEB7FE06E14C0903AFDF001FF80903AF8FC07FE009039F03FFFF8D9E00F13E0D9 C00390C7FC2F3A7EB935>I<903801FFC0010F13FC017F13FFD9FF8013802603FE0013C0 48485AEA0FF8121F13F0123F6E13804848EB7F00151C92C7FC12FFA9127FA27F123FED01 E06C7E15036C6CEB07C06C6C14806C6C131FC69038C07E006DB45A010F13F00101138023 257DA42A>I<9038FE03F000FFEB0FFEEC3FFF91387C7F809138F8FFC000075B6C6C5A5C A29138807F80ED3F00150C92C7FC91C8FCB3A2B512FEA422257EA427>114 D<90383FF0383903FFFEF8000F13FF381FC00F383F0003007E1301007C130012FC15787E 7E6D130013FCEBFFE06C13FCECFF806C14C06C14F06C14F81203C614FC131F9038007FFE 140700F0130114007E157E7E157C6C14FC6C14F8EB80019038F007F090B512C000F81400 38E01FF81F257DA426>I<130FA55BA45BA25B5BA25A1207001FEBFFE0B6FCA3000390C7 FCB21578A815F86CEB80F014816CEBC3E090383FFFC06D1380903803FE001D357EB425> I E /Fj 65 123 df11 DI14 D<133C137EA213FE1201EA03FC13F0EA07E0EA 0FC0EA1F80EA1E005A5A5A12C00F0F6FB92A>19 D<001C131C007F137F39FF80FF80A26D 13C0A3007F137F001C131C00001300A40001130101801380A20003130301001300485B00 061306000E130E485B485B485B006013601A197DB92A>34 D<146014E0EB01C0EB0380EB 0700130E131E5B5BA25B485AA2485AA212075B120F90C7FCA25A121EA2123EA35AA65AB2 127CA67EA3121EA2121F7EA27F12077F1203A26C7EA26C7E1378A27F7F130E7FEB0380EB 01C0EB00E01460135278BD20>40 D<12C07E12707E7E7E120F6C7E6C7EA26C7E6C7EA213 78A2137C133C133E131EA2131F7FA21480A3EB07C0A6EB03E0B2EB07C0A6EB0F80A31400 A25B131EA2133E133C137C1378A25BA2485A485AA2485A48C7FC120E5A5A5A5A5A13527C BD20>I<121C127FEAFF80A213C0A3127F121C1200A412011380A2120313005A1206120E 5A5A5A12600A19798817>44 DI<121C127FEAFF80A5EA7F0012 1C0909798817>I48 DI<1538A2157815F8A2140114031407A2140F141F141B1433147314 6314C313011483EB030313071306130C131C131813301370136013C01201EA038013005A 120E120C5A123812305A12E0B712F8A3C73803F800AB4A7E0103B512F8A325397EB82A> 52 D<0006140CD80780133C9038F003F890B5FC5D5D158092C7FC14FC38067FE090C9FC ABEB07F8EB3FFE9038780F803907E007E090388003F0496C7E12066E7EC87EA28181A216 80A4123E127F487EA490C71300485C12E000605C12700030495A00385C6C1303001E495A 6C6C485A3907E03F800001B5C7FC38007FFCEB1FE0213A7CB72A>I56 DI<121C127FEAFF80A5EA7F00121CC7FCB2121C127F EAFF80A5EA7F00121C092479A317>I<007FB812F8B912FCA3CCFCAEB912FCA36C17F836 167B9F41>61 D64 D<1538A3157CA315FEA34A7EA34A6C7EA202077FEC063F A2020E7FEC0C1FA2021C7FEC180FA202387FEC3007A202707FEC6003A202C07F1501A2D9 01807F81A249C77F167FA20106810107B6FCA24981010CC7121FA2496E7EA3496E7EA349 6E7EA213E0707E1201486C81D80FFC02071380B56C90B512FEA3373C7DBB3E>II<913A01FF800180020FEBE003027F13F8903A01FF807E07903A03FC000F0F D90FF0EB039F4948EB01DFD93F80EB00FF49C8127F01FE153F12014848151F4848150FA2 48481507A2485A1703123F5B007F1601A35B00FF93C7FCAD127F6DED0180A3123F7F001F 160318006C7E5F6C7E17066C6C150E6C6C5D00001618017F15386D6C5CD91FE05C6D6CEB 03C0D903FCEB0F80902701FF803FC7FC9039007FFFFC020F13F002011380313D7BBA3C> II< B812F8A30001903880001F6C90C71201EE00FC177C173C171CA2170CA4170E1706A2ED01 80A21700A41503A21507151F91B5FCA3EC001F15071503A21501A692C8FCAD4813C0B612 C0A32F397DB836>70 DI< B648B512FEA30001902680000313006C90C76C5AB3A491B6FCA391C71201B3A6486D497E B648B512FEA337397DB83E>II76 DIIII82 DI<003FB812E0A3D9C003EB001F273E0001 FE130348EE01F00078160000701770A300601730A400E01738481718A4C71600B3B09138 07FF80011FB612E0A335397DB83C>I III<39018001800003130339070007 00000E130E485B0018131800381338003013300070137000601360A200E013E0485BA400 CE13CE39FF80FF806D13C0A3007F137FA2393F803F80390E000E001A1974B92A>92 D97 DIIII<147E903803FF8090380FC1E0EB1F8790 383F0FF0137EA213FCA23901F803C091C7FCADB512FCA3D801F8C7FCB3AB487E387FFFF8 A31C3B7FBA19>IIII< EB01C0EB07F0EB0FF8A5EB07F0EB01C090C7FCAAEB01F813FFA313071301B3B3A2123C12 7E00FF13F01303A214E038FE07C0127C383C0F00EA0FFEEA03F8154984B719>III<2703F00FF0EB1FE000FFD93FFCEB7FF8913AF03F01E0 7E903BF1C01F83803F3D0FF3800FC7001F802603F70013CE01FE14DC49D907F8EB0FC0A2 495CA3495CB3A3486C496CEB1FE0B500C1B50083B5FCA340257EA445>I<3903F00FF000 FFEB3FFCECF03F9039F1C01F803A0FF3800FC03803F70013FE496D7EA25BA35BB3A3486C 497EB500C1B51280A329257EA42E>II<3903F01FE000FFEB7FF89038 F1E07E9039F3801F803A07F7000FC0D803FEEB07E049EB03F04914F849130116FC150016 FEA3167FAA16FEA3ED01FCA26DEB03F816F06D13076DEB0FE001F614C09039F7803F0090 38F1E07E9038F0FFF8EC1FC091C8FCAB487EB512C0A328357EA42E>II<3807E01F00 FFEB7FC09038E1E3E09038E387F0380FE707EA03E613EE9038EC03E09038FC0080491300 A45BB3A2487EB512F0A31C257EA421>II<1318A51338A31378A313F8120112031207001FB5FCB6FC A2D801F8C7FCB215C0A93800FC011580EB7C03017E13006D5AEB0FFEEB01F81A347FB220 >IIIIII<003FB512FCA2EB8003D83E0013F8003CEB07F00038EB0FE012300070EB1FC0 EC3F800060137F150014FE495AA2C6485A495AA2495A495A495AA290387F000613FEA248 5A485A0007140E5B4848130C4848131CA24848133C48C7127C48EB03FC90B5FCA21F247E A325>I E /Fk 26 123 df16 D<131F1480133F137FA2EBFF00485A485A5B485A485A138048C7FC123E123C5A12 E0124011126CC431>19 D<140C141C1438147014E0EB01C01303EB0780EB0F00A2131E5B A25B13F85B12015B1203A2485AA3485AA348C7FCA35AA2123EA2127EA4127CA312FCB3A2 127CA3127EA4123EA2123FA27EA36C7EA36C7EA36C7EA212017F12007F13787FA27F7FA2 EB0780EB03C01301EB00E014701438141C140C166476CA26>40 D<12C07E12707E7E7E12 0F6C7E6C7EA26C7E6C7EA21378137C133C133E131E131FA2EB0F80A3EB07C0A3EB03E0A3 14F0A21301A214F8A41300A314FCB3A214F8A31301A414F0A21303A214E0A3EB07C0A3EB 0F80A3EB1F00A2131E133E133C137C13785BA2485A485AA2485A48C7FC120E5A5A5A5A5A 16647BCA26>I<121EEA7F80A2EAFFC0A4EA7F80A2EA1E000A0A78891B>46 D<121EEA7F80A2EAFFC0A4EA7F80A2EA1E00C7FCB3A5121EEA7F80A2EAFFC0A4EA7F80A2 EA1E000A2B78AA1B>58 D<16C04B7EA34B7EA34B7EA34B7EA3ED19FEA3ED30FFA203707F ED607FA203E07FEDC03FA2020180ED801FA2DA03007F160FA20206801607A24A6D7EA34A 6D7EA34A6D7EA20270810260147FA202E08191B7FCA249820280C7121FA249C87F170FA2 0106821707A2496F7EA3496F7EA3496F7EA201788313F8486C83D80FFF03037FB500E002 7FEBFFC0A342477DC649>65 D<010FB512FEA3D9000313806E130080B3B3AB123F487E48 7EA44A5A13801300006C495A00705C6C13076C5C6C495A6CEB1F802603E07FC7FC3800FF FCEB1FE027467BC332>74 D77 D<003FB912F8A3903BF0001FF8001F01806D481303003EC7150048187C0078183CA20070 181CA30060180CA5481806A5C81600B3B3A54B7EED7FFE49B77EA33F447DC346>84 D I97 D<167FED3FFFA315018182B3EC7F80903803FFF090380FC07C90383F000E017E1307496D 5AD803F87F48487F5B000F81485AA2485AA2127FA290C8FC5AAB7E7FA2123FA26C7EA200 0F5D7F6C6C5B00035C6C6C9038077F806C6C010E13C0013F011C13FE90380FC0F8903803 FFE09026007F0013002F467DC436>100 DII105 D108 D<3901FC01FE00FF903807FFC091381E07F091383801F8000701707F0003EBE0 002601FDC07F5C01FF147F91C7FCA25BA35BB3A8486CECFF80B5D8F83F13FEA32F2C7DAB 36>110 DI<3903F803F000FFEB1FFCEC3C 3EEC707F0007EBE0FF3803F9C000015B13FBEC007E153C01FF13005BA45BB3A748B4FCB5 12FEA3202C7DAB26>114 D<90383FE0183901FFFC383907E01F78390F0003F8001E1301 481300007C1478127800F81438A21518A27EA27E6C6C13006C7E13FC383FFFE06C13FC6C 13FF6C14C06C14E0C614F0011F13F81300EC0FFC140300C0EB01FE1400157E7E153EA27E A36C143C6C147C15786C14F86CEB01F039F38003E039F1F00F8039E07FFE0038C00FF01F 2E7DAC26>I<1306A5130EA4131EA3133E137EA213FE12011207001FB512F0B6FCA2C648 C7FCB3A4150CAA017E131C017F1318A26D133890381F8030ECC070903807E0E0903801FF C09038007F001E3E7EBC26>III121 D<003FB612E0A29038C0003F90C713C0 003CEC7F800038ECFF00A20030495A0070495AA24A5A0060495AA24A5A4A5AA2C7485A4A C7FC5B5C495A13075C495A131F4A1360495A495AA249C712C0485AA2485A485A1501485A 48481303A24848EB07804848131F00FF14FF90B6FCA2232B7DAA2B>I E /Fl 27 122 df45 D68 DI73 D76 D<943801FFF0053FEBFF804CB612F0040F 9038001FFEDC3FF0903801FF80DCFF809038003FE0DB03FEC8EA0FF8DB0FF8ED03FE4B48 6F7EDB7FC09238007FC04B48707E4A90CA6C7EDA07FEEF0FFC4A48717E4A48717E4A4871 7F4A48717F4A48727E4949727EA24990CC6C7E4948737E010F874A19074948737E013F88 4A85017F884A8501FF8848894A1A7F48894A1A3FA2488991CE121F4889A34848757EA300 3F1E80A24987A3007F1EC0A44987A200FF1EE0B1007F1EC0A26D63A4003F1E80A36D6300 1F1E00A36C6C515AA36C656E1A3FA26C656E1A7F6C65A26C6D505AA26D6CDB3FC04A5B01 3FDCFFF05E6E020301FC5C011F922607C03E93C7FC6E91270F800F805B010F92261F0003 5D6D6C021E6D6C495A6D6C4A6D6C495A053814606D6D0470495A6D6D01786E495A6E6C01 704C5A6E6CDC18015B6E6CDC1C0390C8FC6E6C4D5A6E6C70485A6E6C4D5A0200D98078ED 3FE092267FC0384B5ADB3FF06F485A92260FF83C4BC9FC922603FE1EEC0FF8922601FF9F EC3FF0923C003FFF8001FF80040FD9C01F1730040390B5EAFBC0DC003F14830501EBF003 94C8FC871F701A01871FF07515E0A27514011E03747E1E0775EC0FC076131F76133FE17F F0137F9939FC03FF8099B6FC751500A3755C6687755C755C755C7514800A3F90C7FCF407 F86C9A78F87C>81 DI<913803FF80021F13F891B512FE903A03FC01FF80903A07E0003F E0D91F80EB0FF8013EC76C7E496E7E01F06E7E48486E7F717E4848153F4982D807A06F7E 13FC487E6D6F7E80A2717EA46C90C8FC6C5A6C5ACAFCA6EE07FF0303B5FC157F913903FF FE07021F138091387FF800903801FFC0010790C7FCEB1FFCEB3FF0EBFFE0485B485B4890 C8FC5B485A485AA2485A1A0E485AA312FF5B170FA4171FA26D153F007F163B177B6DDBF1 FE131C003F16E16C6C14016C6C912603C0FF13386C6CEC0F806C6C6C903A1F007F80706C 6D017CECE1E028007FF803F8EB3FFF011FB500E06D1380010391C7000713009026003FF8 EC01FC474D79CB4F>97 D<14F8EA03FFB5FCA5C6FC133F131FA2130FB3B04CB47E041F13 F8047F13FE923A01FC01FF80923A07E0003FE0031FC7EA0FF0033EEC07FC0378EC01FE4B 6E7EDAF9E06F7EDAFBC06F7EDAFF808292C96C7E737E5C4A707E864A160386851B80A373 13C0A31BE0A31A7FA21BF0AE1BE0A21AFFA31BC0A2611B80A21B0061626E1607626E160F 626E4C5A02F75FDAE7804B5ADAE3C0157FDAC1E04B5ADAC0F04A48C7FC03784A5A4A6CEC 0FF8031F4A5A4A6C6CEB7FC0922703F803FFC8FC0300B512FC010E023F13E090C8D807FE C9FC4C797BF758>II<191FF07FFF051FB5FCA5EF001F180784A284B3B0ED07FE92387FFFC002 03B512F091390FFC01FC91393FE0001FDAFF80EB07814990C7EA03E1D903FCEC01F14948 EC0079D91FF0153D4948151D4A151F49488101FF824890C9FC48835B0007835B120F5B12 1FA2123F5BA2127FA35BA212FFAE127FA27FA3123FA36C7EA36C7EA200075F7F00035F6C 7E606C6D5D6D6C153D013F16396D6C03797F6D6C15F16D6CDA03E17FD903FEDA078113F0 D900FFDA1F01EBFFF0DA7FC0137E91391FF803F80207B512E0020114809127001FF800EC 80004C797AF758>III< F103F8F13FFEDB1FF891B5FC92B5903903FC078002079139E007E01F913D1FF00FF81F80 3FC0913B3FC003FC3E0002FFC7B45A49486E5A49486E5A49486E48EB1F8049486E6CEB06 0097C7FC49486E7E013F82A249486E7EA201FF82A24A80A24884AA6C95C8FCA26E5CA201 7F5EA26D6C4A5AA2011F5E6D6C4A5AA26D6C4A5A6D6C4A5A496C4A5A6E4AC9FC903A0F3F C003FC903A1E1FF00FF80207B512E0D91C0091CAFC013CEB1FF892CCFCA25BA3137CA413 7EA27F8080EB1FF091B612FE6DEDFFF818FF6D17E06D17F8010017FE010383010F84D93F E0C7000114E001FFC9120FD801FC04017F48489338003FF84848171F4848717E48481707 003F727E49170148CBFC737EA200FE85A76C616C616D1701003F616D17036C6C4D5A6C6C 4D5A6C6C4D5A6C6C4D5A6C6C4D5A26007F80DB01FEC7FCD93FE0ED07FCD90FF8ED1FF0D9 03FFEDFFC0010001F8011F90C8FC021FB612F802011580DA000F01F0C9FC4A707DCC4F> I<14F8EA03FFB5FCA5C6FC133F131FA2130FB3B0933803FF80041F13F8047F13FE923A01 FC03FF80923A03E0007FE0DB0F80EB1FF0031EC76C7E5D4B6E7E4B6E7E5D14F9DAFBC06E 7E5D14FF92C9FC865CA35CA45CB3B3A8496C4B7FD97FFF030713F0B7D8800FB612F8A54D 787AF758>I<131EEB7F80497E487F487FA66C5B6C5B6D5A011EC7FC90C8FCB3A7EB01F0 EA07FFB5FCA51201EA007F133FA2131FB3B3B3A3497EEBFFFEB612FCA51E727AF12A>I< EB01F0EA07FFB5FCA51201EA007F133FA2131FB3B3B3B3B3AC497EEBFFFEB612FEA51F78 7AF72A>108 DIII<02F849B47ED803FF 021F13F8B5027F13FE923A01FC01FF80923A07E0003FE0031FC76C7E033EEC0FFCC60278 EC03FE013F496E7E90261FF9E06E7FDAFBC0826DB4486F7E92C96C7E737E5C4A707E864A 160786851B80A2851BC0A2851BE0A5F27FF0AEF2FFE0A54F13C0A34F1380A21B0061626E 160F626E161F626E4C5A4F5A6F5EDAFBC015FFDAF9E04A5BDAF8F04A48C7FC03784A5A6F 4A5A031FEC3FF06F6CEBFFC0922603F80790C8FC0300B512FC043F13E0DC07FEC9FC93CB FCB3A7497EEB7FFFB77EA54C6C7BCA58>I114 DI<1407A85CA65CA35CA35CA25CA25BA25B5B5B5B5B5B48B712FE120FB8FCA3D80001 90C9FCB3B3A2EF01C0B0EF03806D7FA3027FEC0700815F6E6C130E021F141E6F131C6E6C 5B6E6C13F8913901FF01F09139007FFFC0031F5BDB03FCC7FC326B7EE93D>I<02F8EE0F 80D803FFEE3FFFB5030FB5FCA5C6EE000F013F1603011F82A2010F82B3B3A660A460A360 1307606E150E0103161E606E4B7F010116706D6C03F07F6FD903E013F86E6C4948EBFFF8 DA1FE0EB1F00DA0FFE13FE0203B512F8DA007F13E0030790C7EBC0004D4C7ACA58>I<00 7FB500FC0203B512FEA5C66C01F06E14C0010F496E01FCC7FC010349ED7FF06D18C06D60 077EC8FC6E6C157C6E6C5D6E6C5D4E5A6E6C5D6E6C14036E6C4A5A4EC9FC6E6D131E6E7F 6F6C5B033F5C705B6F6C5B92380FFC010307495A70485A6F6C48CAFC6F138E6F139E17FC 705A705A161F83707E707E835E4C7F043C7F4C6C7E16709338F03FF04B486C7E4B486C7E 168003076D7E4B486C7E031E6D7F5D03386D7F03786E7E4B6E7E4A48141F4A4881727E4A 486E7E4AC81203021E82023E6F7F027E6F7F4A167F010184010784D91FFE83017FEFFFFE 0007B54B6D7EB600C00207ECFFC0A5524A80C953>120 DI E end TeXDict begin 0 0 bop 564 651 a Fl(L-rigid)54 b(Databases)d(and)h(the)g (Expressibilit)l(y)871 812 y(of)g(Incomplete)g(Relational)j(Query)1594 972 y(Languages)1424 1287 y Fk(Jos)m(\023)-46 b(e)33 b(Mar)-11 b(\023)-38 b(\020a)32 b(T)-8 b(urull)31 b(T)-8 b(orres)1341 1619 y Fj(Univ)n(ersidad)26 b(Nacional)h(de)h(San)f(Luis) 1229 1719 y(turull@iam)n(ba.edu.ar,)f(turull@unsl.edu.ar)947 2034 y Fk(Advisor:)43 b(A.)33 b(Mendelzon)g(\(Univ)m(ersit)m(y)h(of)e (T)-8 b(oron)m(to\))1773 2333 y Fi(Abstract)648 2507 y Fj(The)32 b(class)f(of)h Fh(Computable)k(Queries)c Fj(\()p Fg(C)5 b(Q)p Fj(\))32 b(w)n(as)f(de\014ned)i(b)n(y)f(Chandra)f (and)h(Harel)523 2607 y(in)27 b(1980,)e(as)h(functions)h(on)f (structures)g(rather)f(than)i(functions)g(on)f(n)n(um)n(b)r(ers)g(\(as) h(recur-)523 2707 y(siv)n(e)j(functions\).)49 b(With)32 b(this)f(form)n(ulation)f(of)h(the)h(notion)f(of)g(a)g(query)f(to)h(a)g (relational)523 2806 y(database)g(\(db\),)j(the)e(\014eld)g(of)g (Finite)g(Mo)r(del)g(Theory)f(b)r(ecame)h(a)f(suitable)h(theoretical) 523 2906 y(framew)n(ork)g(for)i(relational)f(databases.)55 b(In)34 b(this)g(framew)n(ork)f(the)h(notion)g(of)g Fh(lo)l(c)l(al)j (ex-)523 3005 y(pr)l(essibility)27 b Fj(of)e(a)f(giv)n(en)g(logic)g(is) h(the)h(class)e(of)g(queries)g(whic)n(h)h(can)g(b)r(e)g(expressed)f(in) h(that)523 3105 y(logic.)54 b(On)34 b(the)g(other)f(hand,)i(in)f(1991,) f(Abiteb)r(oul)h(and)g(Vian)n(u)f(de\014ned)h(the)g Fh(Generic)523 3205 y(Machine)p Fj(,)27 b(denoted)e(as)g Ff(GM)1445 3175 y Fe(loose)1598 3205 y Fj(,)h(whic)n(h)f(they)g(pro)n(v)n(ed)e(to) i(b)r(e)h(strictly)e(included)i(in)f Fg(C)5 b(Q)p Fj(.)523 3304 y(They)30 b(also)f(pro)n(v)n(ed)f(that)i(this)h(class)e(of)h(mac)n (hines)f(\\b)r(eha)n(v)n(es")f(as)h(complete)h(w.r.t.)44 b(the)523 3404 y(whole)25 b(class)f Fg(C)5 b(Q)24 b Fj(when)h(w)n (orking)e(on)i(classes)f(of)h Fh(or)l(der)l(e)l(d)h Fj(db.)36 b(If)25 b(w)n(e)g(consider)f(the)h(struc-)523 3504 y(tures)h(as)f(db)h (instances,)g(and)f(if)h(w)n(e)g(are)f(using)g(a)h Ff(GM)2255 3473 y Fe(loose)2434 3504 y Fj(mac)n(hine,)g(it)g(means)g(that)g(w)n(e) 523 3603 y(will)34 b(not)f(b)r(e)h(able)f(to)h(compute)f(queries)g(suc) n(h)g(as)g(\\)p Fh(give)j(me)f(the)g(names)g(of)i(the)e(sales-)523 3703 y(men)h(who)h(sel)t(l)g(to)f(an)g(even)g(numb)l(er)f(of)i(clients) p Fj(")d(unless)h(our)e(db)i(is)f(ordered.)56 b(In)35 b(the)523 3802 y(presen)n(t)22 b(Thesis,)h(w)n(e)f(study)h(some)f(prop) r(erties)g(of)g(relational)f(db)i(whic)n(h)g(can)f(increase)f(the)523 3902 y(expressiv)n(e)26 b(p)r(o)n(w)n(er)h(of)h(relational)e(languages) g(or)h(formalisms)g(whic)n(h)h(are)f(incomplete)h(in)523 4002 y(the)k(general)e(case,)i(when)g(w)n(orking)e(on)h(classes)f(of)i (db)g(whic)n(h)f(satisfy)g(that)h(prop)r(erties.)523 4101 y(The)d(formalism)e(whic)n(h)i(w)n(e)f(\014rst)h(consider)e(is)i (the)f Ff(GM)2323 4071 y Fe(loose)2506 4101 y Fj(mac)n(hine.)39 b(And)29 b(the)g(prop-)523 4201 y(erties)c(whic)n(h)h(w)n(e)f(study)h (for)f(classes)f(of)h(db)h(are)f Fh(rigidity)p Fj(,)j Fg(L)e Fh(rigidity)p Fj(,)i Fh(p)l(artial)h(rigidity)p Fj(,)f Fg(L)523 4301 y Fh(p)l(artial)d(rigidity)e Fj(and)d Fh(almost)25 b(rigidity)p Fj(,)f(for)c(di\013eren)n(t)h(fragmen)n(ts)f Fg(L)h Fj(of)g(First)g(Order)e(Logic)523 4400 y(\()p Ff(F)12 b(O)r Fj(\).)38 b(Recall)27 b(that)g(a)g(structure)f(is)h Fh(rigid)i Fj(if)e(its)h(only)e(automorphism)g(is)h(iden)n(tit)n(y)-7 b(.)37 b(The)523 4500 y(fragmen)n(ts)25 b(of)h Ff(F)12 b(O)28 b Fj(whic)n(h)e(w)n(e)f(consider)g(are)g(de\014ned)h(b)n(y)g (stating)f(a)h(b)r(ound)g(in)g(the)g(n)n(um-)523 4599 y(b)r(er)c(of)f(di\013eren)n(t)h(v)-5 b(ariables)21 b(whic)n(h)h(can)f (b)r(e)h(used)g(in)g(a)f(form)n(ula.)34 b(W)-7 b(e)23 b(denote)e(b)n(y)h Ff(F)12 b(O)3209 4569 y Fe(k)3272 4599 y Fj(the)523 4699 y(fragmen)n(t)26 b(of)g Ff(F)12 b(O)29 b Fj(with)e(at)f(most)g Ff(k)j Fj(di\013eren)n(t)e(v)-5 b(ariables,)25 b(p)r(ossibly)h(reused.)36 b(The)26 b(reason)523 4799 y(wh)n(y)32 b(w)n(e)f(use)h Ff(F)12 b(O)1107 4769 y Fe(k)1181 4799 y Fj(as)31 b(the)i(target)e(logic)g(is)h(that)g (Abiteb)r(oul)h(and)f(Vian)n(u)g(pro)n(v)n(ed)e(that)523 4898 y(the)c(expressiv)n(e)f(p)r(o)n(w)n(er)g(of)g(the)i Ff(GM)1684 4868 y Fe(loose)1864 4898 y Fj(mo)r(del)f(is)g(not)g (altered)f(if)i(w)n(e)e(use)h(dynamically)p eop 1 1 bop 523 614 a Fj(generated)25 b(queries)f(in)i Ff(F)12 b(O)1402 584 y Fe(k)1444 614 y Fj(.)36 b(W)-7 b(e)26 b(pro)n(v)n(e)e(that)i(there)f(is)h(a)f(wider)h(set)f(of)h(classes)e (of)i(\014nite)523 714 y(structures)d(for)g(whic)n(h)h Ff(GM)1420 684 y Fe(loose)1598 714 y Fj(is)f(complete)h(than)g(just)g (those)g(in)g(whic)n(h)g(all)f(structures)523 814 y(are)30 b(ordered,)h(and)g(these)g(are)f(at)h(least)g(what)g(w)n(e)g(de\014ne)g (later)g(as)f Fh(str)l(ongly)j Ff(F)12 b(O)3146 783 y Fe(k)3221 814 y Fh(rigid)523 913 y Fj(classes.)45 b(Roughly)-7 b(,)30 b(this)h(means)g(that)f(for)h(ev)n(ery)e(elemen)n(t)i(in)f(ev)n (ery)g(structure)g(in)h(suc)n(h)523 1013 y(a)e(class,)f(there)h(is)g(a) f(form)n(ula)g(in)h Ff(F)12 b(O)1716 983 y Fe(k)1787 1013 y Fj(whic)n(h)29 b(de\014nes)g(that)g(particular)f(elemen)n(t)h (in)g(the)523 1112 y(structure.)56 b(So)34 b(that)g(our)g(\014rst)g (result)g(means)f(that)i(what)f(is)g(relev)-5 b(an)n(t)33 b(as)h(to)g(express-)523 1212 y(ibilit)n(y)i(of)g(queries)e(is)i (rigidit)n(y)f(and)g(not)h(order.)59 b(This)36 b(w)n(as)f(indep)r (enden)n(tly)h(noted)g(b)n(y)523 1312 y(Abiteb)r(oul)27 b(and)g(Vian)n(u,)f(and)g(b)n(y)g(Da)n(w)n(ar.)35 b(Then)27 b(w)n(e)f(consider)f(the)i(existence)f(of)h(classes)523 1411 y(of)f(db)h(whic)n(h)f(are)g(rigid,)g(but)h(whic)n(h)f(are)g(not)g Ff(F)12 b(O)2126 1381 y Fe(k)2194 1411 y Fj(rigid)26 b(for)f(an)n(y)h Ff(k)s Fj(.)36 b(So,)27 b(w)n(e)f(generalize)523 1511 y(the)j(notion)f(of)h(strong)e(rigidit)n(y)h(b)n(y)g(allo)n(wing)f (the)i(b)r(ound)g(on)f(the)h(amoun)n(t)f(of)h(v)-5 b(ariables)523 1611 y(in)30 b(the)h(de\014ning)f Ff(F)12 b(O)32 b Fj(form)n(ulae)d(to) h(b)r(e)h(an)e(arbitrary)f(sub-linear)h(function)i(on)e(the)i(size)523 1710 y(of)h(the)g(db,)i(and)e(w)n(e)f(de\014ne)i(a)e(new)h(class)f(of)h (mac)n(hines)g(whic)n(h)g(lies)g(b)r(et)n(w)n(een)g Ff(GM)3234 1680 y Fe(loose)523 1810 y Fj(and)d Fg(C)5 b(Q)p Fj(,)29 b(and)g(whic)n(h)g(w)n(e)g(call)g Ff(GM)1690 1780 y Fe(f)7 b Fd(\()p Fe(n)p Fd(\))1826 1810 y Fj(.)42 b(This)29 b(mo)r(del)g(w)n(as)g(indep)r(enden)n(tly)h(de\014ned)f(in)523 1910 y(a)g(w)n(ork)f(of)i(Abiteb)r(oul,)h(P)n(apadimitriou)d(and)h (Vian)n(u,)i(in)e(1994,)g(and)g(they)h(pro)n(v)n(ed)e(that)523 2009 y(it)i(is)f(not)g(complete)g(when)h Ff(f)9 b Fj(\()p Ff(n)p Fj(\))29 b(is)g(sub-linear.)41 b(Then)29 b(w)n(e)g(pro)n(v)n(e)f (that,)i(for)f(ev)n(ery)f(sub-)523 2109 y(linear)d(function)h Ff(f)9 b Fj(\()p Ff(n)p Fj(\))26 b(the)g(mac)n(hine)g Ff(GM)1885 2079 y Fe(f)7 b Fd(\()p Fe(n)p Fd(\))2047 2109 y Fj(\\b)r(eha)n(v)n(es")23 b(as)i(complete)h(when)g(w)n(orking) 523 2208 y(on)31 b(strongly)f Ff(F)12 b(O)1097 2178 y Fe(f)7 b Fd(\()p Fe(n)p Fd(\))1265 2208 y Fj(rigid)30 b(classes)g(of)h(db.)48 b(Then)32 b(w)n(e)f(conclude)g(that)g(strong)f (rigidit)n(y)523 2308 y(is)e(alw)n(a)n(ys)e(a)i(nice)h(prop)r(ert)n(y) -7 b(,)27 b(in)h(the)h(sense)f(that)g(for)g(an)n(y)f(giv)n(en)h (strongly)f(rigid)g(class)g(of)523 2408 y(db)32 b(there)f(will)h(alw)n (a)n(ys)d(b)r(e)j(a)f(mac)n(hine)g(\(or)f(a)h(language\))f(whic)n(h)i (is)f(not)g(complete,)i(but)523 2507 y(whic)n(h)25 b(will)h(w)n(ork)e (as)h(if)h(it)g(w)n(ere)e(on)h(an)n(y)g(db)h(of)f(that)h(class.)35 b(W)-7 b(e)26 b(consider)e(t)n(w)n(o)h(examples)523 2607 y(of)g(classes)f(of)i(rigid)f(graphs)f(whic)n(h)h(w)n(e)g(build,)h(and) g(for)e(whic)n(h)i(w)n(e)f(exhibit)h(t)n(w)n(o)e(di\013eren)n(t)523 2707 y(sets)j(of)g(prop)r(erties)g(that)h(de\014ne)f(their)g(elemen)n (ts.)37 b(One)27 b(set)h(is)f(in)g Ff(F)12 b(O)2773 2676 y Fd(2)2839 2707 y Fj(while)27 b(the)h(other)523 2806 y(\(whic)n(h)c(seems)g(to)g(b)r(e)g(naturally)g(induced)g(b)n(y)g(the)g (de\014nition)h(of)f(the)g(graphs\))f(cannot)h(b)r(e)523 2906 y(b)r(ounded)g(b)n(y)f(an)n(y)g(constan)n(t.)35 b(On)23 b(the)h(other)f(hand,)i(w)n(e)e(explore)f(some)h(asp)r(ects)h (of)f(query)523 3005 y(computabilit)n(y)34 b(in)g Ff(F)12 b(O)1293 2975 y Fe(k)1335 3005 y Fj(.)56 b(W)-7 b(e)34 b(build)h(a)f(family)g(of)g(classes)f(of)h(graphs,)g(whic)n(h)g(w)n(e)g (call)523 3105 y Fh(Clique)27 b(Interse)l(ction)f(gr)l(aphs)f Fj(\()p Ff(C)6 b(I)h Fj(\),)26 b(for)d(whic)n(h)g Fh(no)k(b)l(o)l(ole)l (an)g(query)d Fj(can)f(b)r(e)h(computed)g(in)523 3205 y Ff(F)12 b(O)653 3175 y Fe(k)694 3205 y Fj(,)25 b(unless)f(it)g(is)g (trivial.)35 b(Up)25 b(to)e(no)n(w)h(there)f(w)n(ere)g(only)h(t)n(w)n (o)f(kno)n(wn)g(examples)h(of)g(non)523 3304 y(trivial)33 b(classes)g(with)h(this)h(prop)r(ert)n(y:)48 b(the)34 b(class)f(of)h(all)g(structures)f(whic)n(h)g(satisfy)h(the)523 3404 y Ff(k)s Fj(-extension)25 b(axiom)h(and)g(the)h(P)n(aley)e (graphs.)35 b(Ho)n(w)n(ev)n(er,)24 b(the)j Ff(C)6 b(I)34 b Fj(graphs)25 b(ha)n(v)n(e)g(a)h(m)n(uc)n(h)523 3504 y(simpler)34 b(and)g(concrete)f(structure.)56 b(W)-7 b(e)34 b(pro)n(v)n(e)f(this)h(result)g(b)n(y)g(means)f(of)h(a)g(b)r (ounded)523 3603 y(Bac)n(k)21 b(and)h(F)-7 b(orth)22 b(system)g(of)g(partial)g(isomorphisms)e(whic)n(h)j(w)n(e)e(de\014ne)i (in)f(terms)g(of)g(a)g(re-)523 3703 y(lation)g(o)n(v)n(er)e(a)i(sp)r (ecial)g(class)f(of)h(induced)h(sub-h)n(yp)r(ergraphs.)33 b(W)-7 b(e)22 b(use)g(a)g(no)n(v)n(el)f(tec)n(hnique)523 3802 y(b)n(y)31 b(de\014ning)g(these)g(sub-h)n(yp)r(ergraphs)e(as)i (companion)f(structures)g(of)h(the)h(sub-graphs,)523 3902 y(whic)n(h)h(carry)e(information)g(regarding)g(the)i(di\013eren)n (t)g(w)n(a)n(ys)e(in)i(whic)n(h)f(the)h(sub-graphs)523 4002 y(can)e(b)r(e)g(expanded.)47 b(Another)31 b(in)n(teresting)f(prop) r(ert)n(y)g(of)h Ff(C)6 b(I)39 b Fj(graphs)29 b(is)i(that)h(they)f(can) 523 4101 y(b)r(e)d(easily)f(expanded)h(to)f(graphs)g(whic)n(h)g(are)g (rigid.)37 b(Then)28 b(w)n(e)f(face)h(a)f(Mo)r(del)h(Theoretic)523 4201 y(issue,)k(whic)n(h)g(is)f(related)g(to)h(our)f(main)g(sub)5 b(ject)32 b(and)f(whic)n(h)h(is)f(a)g(long)g(standing)g(op)r(en)523 4301 y(problem,)f(with)h(a)f(di\013eren)n(t)g(and)g(no)n(v)n(el)f (approac)n(h:)41 b(the)30 b(de\014nition)h(of)f(classes)f(of)h(rigid) 523 4400 y(structures)21 b(whic)n(h)h(are)e(not)i Ff(F)12 b(O)1542 4370 y Fe(k)1605 4400 y Fj(rigid)21 b(for)g(an)n(y)g Ff(k)s Fj(,)i(and)f(whic)n(h)f(are)g(\\constructible".)34 b(By)523 4500 y(this)22 b(it)h(is)f(mean)n(t,)h(in)f(an)g(informal)f (sense,)i(that)f(one)g(can)f(ha)n(v)n(e)g(an)h(in)n(tuitiv)n(e)g(image) f(of)h(the)523 4599 y(structures)30 b(whic)n(h)g(form)g(the)h(class.)44 b(Though)30 b(it)h(is)f(w)n(ell)g(kno)n(wn)g(that)h(\\man)n(y")e (classes)523 4699 y(of)f(suc)n(h)g(structures)g(are)f(not)i Ff(F)12 b(O)1614 4669 y Fe(k)1684 4699 y Fj(rigid)27 b(for)h(an)n(y)g Ff(k)s Fj(,)g(no)g(constructible)g(class)g(is)g(kno)n (wn)523 4799 y(at)j(presen)n(t.)46 b(There)31 b(are)f(t)n(w)n(o)g (indep)r(enden)n(t)i(constructions)e(\(Gurevic)n(h)g(and)h(Shelah)g(in) 523 4898 y(1995,)f(and)g(Andr)n(\023)-39 b(ek)-5 b(a)29 b(et)i(al)f(in)h(1995\))e(but)i(they)g(use)f(either)h(probabilistic)e (metho)r(ds)i(or)p eop 2 2 bop 523 614 a Fj(existen)n(tial)32 b(pro)r(ofs,)h(rather)e(than)i (constructiv)n(e)f(pro)r(ofs,)h(so)e(that)i(w)n(e)f(cannot)g(ha)n(v)n (e)g(an)523 714 y(in)n(tuitiv)n(e)c(image)e(of)i(the)f(structures.)36 b(Regarding)26 b(our)h(Rigid)g Ff(C)6 b(I)35 b Fj(graphs,)26 b(w)n(e)h(exhibit)h(a)523 814 y(set)23 b(of)h(prop)r(erties)e(with)i (an)f(un)n(b)r(ounded)h(n)n(um)n(b)r(er)f(of)h(v)-5 b(ariables)22 b(and)h(w)n(e)g Fh(c)l(onje)l(ctur)l(e)g Fj(that)523 913 y(the)32 b(class)f(is)g(not)h Ff(F)12 b(O)1238 883 y Fe(k)1311 913 y Fj(rigid)31 b(for)g(an)n(y)g Ff(k)s Fj(.)49 b(But)32 b(w)n(e)f(consider)f(here)i(another)e(approac)n(h.)523 1013 y(W)-7 b(e)31 b(w)n(onder)f(whether)g(b)n(y)h(relaxing)e(a)i (little)g(bit)g(the)g(h)n(yp)r(othesis,)h(w)n(e)e(could)h(\014nd)g(suc) n(h)523 1112 y(a)37 b(class.)66 b(F)-7 b(or)36 b(this)i(sak)n(e)e(w)n (e)h(de\014ne)h(t)n(w)n(o)f(new)g(prop)r(erties:)56 b(a)37 b(structure)g(is)g Fh(p)l(artial)t(ly)523 1212 y(rigid)32 b Fj(\()p Ff(pr)r Fj(\))f(if)g(it)f(has)g(a)g(non)g(empt)n(y)g(subset)g (of)g(de\014nable)g(elemen)n(ts,)h(and)f(a)f(class)h(of)g Ff(pr)523 1312 y Fj(structures)36 b(is)h Fh(almost)h(rigid)g Fj(if)g(the)f(limit)g(of)g(the)g(quotien)n(t)f(b)r(et)n(w)n(een)h(the)g (n)n(um)n(b)r(er)f(of)523 1411 y(de\014nable)e(elemen)n(ts)g(and)f(the) i(size)e(of)h(the)g(structure)f(tends)i(to)e(1,)i(as)f(the)g(n)n(um)n (b)r(er)f(of)523 1511 y(de\014nable)j(elemen)n(ts)h(tends)f(to)g (in\014nit)n(y)-7 b(.)64 b(So,)38 b(w)n(e)e(de\014ne)h(here)f(classes)f (of)h(structures,)523 1611 y(whic)n(h)25 b(are)g Fh(c)l(onstructible)g Fj(\()p Fh(Clique)k(Interse)l(ction)e(T)-6 b(r)l(e)l(e)28 b(structur)l(es)p Fj(\),)c(and)h(w)n(e)g(pro)n(v)n(e)f(that)523 1735 y(they)k(are)e Fh(str)l(ongly)h Ff(F)12 b(O)1286 1705 y Fe(f)7 b Fd(\()p Fe(n)p Fd(\))1496 1735 y Ff(pr)r Fj(,)28 b(with)g Ff(f)9 b Fj(\()p Ff(n)p Fj(\))23 b(=)g Ff(n)2142 1705 y Fd(2)p Fe(=)p Fd(\(2)2270 1669 y Fc(^)2268 1680 y Fb(k)2304 1705 y Fa(\000)p Fd(1\))2419 1735 y Fj(.)37 b(Then)27 b(w)n(e)g(sho)n(w)g(that)g(these)523 1834 y(classes)g(are)g(not)h(strongly)f Ff(F)12 b(O)1527 1804 y Fe(k)1644 1834 y Ff(pr)31 b Fj(for)d(an)n(y)f Ff(k)s Fj(.)38 b(Moreo)n(v)n(er,)26 b(these)i(classes)f(are)g Fh(almost)523 1934 y(rigid)p Fj(.)61 b(W)-7 b(e)35 b(also)f(build)h(a)g (hierarc)n(h)n(y)e(of)i(these)f(classes)g(as)g(to)h(the)h(b)r(ound)f Ff(f)9 b Fj(\()p Ff(n)p Fj(\).)59 b(And)523 2034 y(w)n(e)27 b Fh(c)l(onje)l(ctur)l(e)g Fj(that)h(this)g(hierarc)n(h)n(y)d(is)i (strict.)37 b(This)27 b(means)g(that,)h(for)f(these)g(classes)f(of)523 2133 y(structures,)g(there)g(is)g(no)h Ff(GM)1497 2103 y Fe(loose)1677 2133 y Fj(mac)n(hine)f(whic)n(h)g(can)g(compute)h(the)f (automorphism)523 2233 y(t)n(yp)r(es)31 b(of)f(all)h(the)g(de\014nable) g(elemen)n(ts)f(of)h(ev)n(ery)e(structure)i(in)g(the)g(class)f(while)g (ha)n(ving)523 2332 y(that)h(structure)f(as)g(input.)47 b(Then,)32 b(to)f(pro)n(v)n(e)e(the)i(stated)f(result,)i(w)n(e)e (\014rst)g(giv)n(e)g(a)h(su\016-)523 2432 y(cien)n(t)h(condition)g(for) g(the)g(non)g Ff(F)12 b(O)1672 2402 y Fe(k)1807 2432 y Ff(pr)35 b Fj(for)c(an)n(y)h Ff(k)s Fj(,)h(of)f(a)g(class)f(of)h Ff(pr)j Fj(structures,)d(in)523 2532 y(terms)27 b(of)g(the)g(equiv)-5 b(alence)26 b(of)h(structures)f(under)h Ff(F)12 b(O)2274 2502 y Fe(k)2315 2532 y Fj(.)37 b(W)-7 b(e)27 b(pro)n(v)n(e)f(the)h (equiv)-5 b(alence)26 b(of)523 2631 y(pairs)20 b(of)h(non)g(isomorphic) f Ff(C)6 b(I)h(T)32 b Fj(structures)20 b(under)h Ff(F)12 b(O)2307 2601 y Fe(k)2369 2631 y Fj(b)n(y)21 b(means)g(of)g(a)f(b)r (ounded)i(Bac)n(k)523 2731 y(and)31 b(F)-7 b(orth)31 b(system)g(of)g(partial)f(isomorphisms,)h(and)g(b)n(y)g(using)g(the)h (previously)d(stated)523 2831 y(result.)37 b(W)-7 b(e)28 b(also)f(use)g(here)g(auxiliary)g(structures.)36 b(Finally)-7 b(,)28 b(w)n(e)f(study)h(the)g(prop)r(ert)n(y)e(of)523 2930 y Ff(pr)h Fj(as)e(a)f(means)g(to)h(strictly)g(increase)e(the)i (class)f(of)h(queries)f(whic)n(h)h(can)f(b)r(e)h(computed)g(or)523 3030 y(expressed)h(b)n(y)h(an)g(incomplete)g(mac)n(hine)f(or)h (language)e(on)i(a)g(giv)n(en)f(class)g(of)h(structures.)523 3129 y(F)-7 b(or)33 b(this)h(sak)n(e)e(w)n(e)i(de\014ne)f(a)h(notion)f (of)g Fh(r)l(elative)i Fj(completeness)e(of)h(a)f(formal)g(mac)n(hine) 523 3229 y(whic)n(h)f(in)n(v)n(olv)n(es)e(t)n(w)n(o)h(di\013eren)n(t)h (classes)e(of)i(structures.)49 b(W)-7 b(e)32 b(ac)n(hiev)n(e)f (completeness)g(in)523 3329 y(the)36 b(class)e(of)i(\\small")e(db)i(b)n (y)f(ev)-5 b(aluating)35 b(queries)f(in)i(the)g(class)f(of)g(\\big")f (db.)61 b(Then)523 3428 y(w)n(e)34 b(pro)n(v)n(e)e(that)i(if)g Fg(C)39 b Fj(is)34 b(a)f(class)g(of)h(structures)f(whic)n(h)h(is)g (strongly)e Ff(F)12 b(O)2886 3398 y Fe(g)r Fd(\()p Fe(n)p Fd(\))3086 3428 y Ff(pr)r Fj(,)36 b(with)523 3528 y Ff(g)s Fj(\()p Ff(n)p Fj(\))d(sub-linear,)f(and)h(if)g Fg(C)1422 3498 y Fa(0)1477 3528 y Fj(is)g(the)g(class)e(of)i(the)g(restrictions)e (of)h(the)h(structures)f(in)h Fg(C)523 3628 y Fj(to)c(their)h(resp)r (ectiv)n(e)e(rigid)h(sub-domains,)g(then)h Ff(GM)2262 3597 y Fe(g)r Fd(\()p Fe(n)p Fd(\))2423 3628 y Fj(is)f(complete)h(on)f Fg(C)34 b Fj(w.r.t.)42 b Fg(C)3341 3597 y Fa(0)3364 3628 y Fj(.)523 3727 y(W)-7 b(e)24 b(pro)n(v)n(e)e(also)h(other)g(relativ)n (e)f(completeness)h(results)h(with)g(di\013eren)n(t)g(w)n(a)n(ys)e(of)h (de\014ning)523 3827 y(the)33 b(substructures.)51 b(This)33 b(means)f(that)g(w)n(e)h(can)f(ac)n(hiev)n(e)f(completeness)h(with)h(a) f(class)523 3926 y(of)26 b(sup)r(erstructures)f(built)i(in)f(a)g(w)n(a) n(y)f(that)h(adds)g(as)f(few)i(elemen)n(ts)f(as)f(p)r(ossible)h(to)g (ev)n(ery)523 4026 y(structure)g(in)h(the)g(giv)n(en)e(class.)36 b(And)27 b(in)g(this)f(sense)g(the)h(prop)r(ert)n(y)e(of)i Fh(almost)i(rigidity)f Fj(is)523 4126 y(also)f(imp)r(ortan)n(t:)36 b(w)n(e)27 b(add)h(\\almost)e(no")h(new)h(elemen)n(ts)f(to)h(the)g (structures.)p eop end userdict /end-hook known{end-hook}if .