%!PS-Adobe-2.0 %%Creator: dvips(k) 5.85 Copyright 1999 Radical Eye Software %%Title: paper.dvi %%Pages: 11 %%PageOrder: Ascend %%BoundingBox: 0 0 596 842 %%DocumentFonts: Helvetica-Bold Helvetica Times-Bold Times-Roman %%+ Times-Italic CMSY10 Courier Symbol CMMI10 %%DocumentPaperSizes: a4 %%EndComments %DVIPSWebPage: (www.radicaleye.com) %DVIPSCommandLine: dvips -o paper.ps paper.dvi %DVIPSParameters: dpi=600, compressed %DVIPSSource: TeX output 2000.06.21:1418 %%BeginProcSet: texc.pro %! /TeXDict 300 dict def TeXDict begin/N{def}def/B{bind def}N/S{exch}N/X{S N}B/A{dup}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{A A 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/IEn 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 IEn N end A{/foo setfont}2 array copy cvx N load 0 nn put/ctr 0 N[}B/sf 0 N/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 A definefont setfont}B/Cw{Cd A length 5 sub get}B/Ch{Cd A length 4 sub get }B/Cx{128 Cd A length 3 sub get sub}B/Cy{Cd A length 2 sub get 127 sub} B/Cdx{Cd A length 1 sub get}B/Ci{Cd A 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/CharBuilder{save 3 1 roll S A/base get 2 index get S/BitMaps get S get/Cd X pop/ctr 0 N Cdx 0 Cx Cy Ch sub Cx Cw add Cy setcachedevice Cw Ch true[1 0 0 -1 -.1 Cx sub Cy .1 sub]/id Ci N/rw Cw 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 A 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 A gp add/gp X adv}B/nd{ /cp 0 N rw exit}B/lsh{rw cp 2 copy get A 0 eq{pop 1}{A 255 eq{pop 254}{ A A add 255 and S 1 and or}ifelse}ifelse put 1 adv}B/rsh{rw cp 2 copy get A 0 eq{pop 128}{A 255 eq{pop 127}{A 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}]A{bind pop} forall N/D{/cc X A type/stringtype ne{]}if nn/base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{A A length 1 sub A 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 A 1 get A mul exch 0 get A 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/IEn 256 array N 2 string 0 1 255{IEn S A 360 add 36 4 index cvrs cvn put}for pop 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/Rx 0 N/Ry 0 N/V{}B/RV/v{ /Ry X/Rx X V}B statusdict begin/product where{pop false[(Display)(NeXT) (LaserWriter 16/600)]{A length product length le{A length product exch 0 exch getinterval eq{pop true exit}if}{pop}ifelse}forall}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale Rx Ry false RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR Rx Ry scale 1 1 false RMat{BDot} imagemask grestore}}ifelse B/QV{gsave newpath transform round exch round exch itransform moveto Rx 0 rlineto 0 Ry neg rlineto Rx neg 0 rlineto fill grestore}B/a{moveto}B/delta 0 N/tail{A/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: 8r.enc % @@psencodingfile@{ % author = "S. Rahtz, P. MacKay, Alan Jeffrey, B. Horn, K. Berry", % version = "0.6", % date = "1 July 1998", % filename = "8r.enc", % email = "tex-fonts@@tug.org", % docstring = "Encoding for TrueType or Type 1 fonts % to be used with TeX." % @} % % Idea is to have all the characters normally included in Type 1 fonts % available for typesetting. This is effectively the characters in Adobe % Standard Encoding + ISO Latin 1 + extra characters from Lucida. % % Character code assignments were made as follows: % % (1) the Windows ANSI characters are almost all in their Windows ANSI % positions, because some Windows users cannot easily reencode the % fonts, and it makes no difference on other systems. The only Windows % ANSI characters not available are those that make no sense for % typesetting -- rubout (127 decimal), nobreakspace (160), softhyphen % (173). quotesingle and grave are moved just because it's such an % irritation not having them in TeX positions. % % (2) Remaining characters are assigned arbitrarily to the lower part % of the range, avoiding 0, 10 and 13 in case we meet dumb software. % % (3) Y&Y Lucida Bright includes some extra text characters; in the % hopes that other PostScript fonts, perhaps created for public % consumption, will include them, they are included starting at 0x12. % % (4) Remaining positions left undefined are for use in (hopefully) % upward-compatible revisions, if someday more characters are generally % available. % % (5) hyphen appears twice for compatibility with both % ASCII and Windows. % /TeXBase1Encoding [ % 0x00 (encoded characters from Adobe Standard not in Windows 3.1) /.notdef /dotaccent /fi /fl /fraction /hungarumlaut /Lslash /lslash /ogonek /ring /.notdef /breve /minus /.notdef % These are the only two remaining unencoded characters, so may as % well include them. /Zcaron /zcaron % 0x10 /caron /dotlessi % (unusual TeX characters available in, e.g., Lucida Bright) /dotlessj /ff /ffi /ffl /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef % very contentious; it's so painful not having quoteleft and quoteright % at 96 and 145 that we move the things normally found there to here. /grave /quotesingle % 0x20 (ASCII begins) /space /exclam /quotedbl /numbersign /dollar /percent /ampersand /quoteright /parenleft /parenright /asterisk /plus /comma /hyphen /period /slash % 0x30 /zero /one /two /three /four /five /six /seven /eight /nine /colon /semicolon /less /equal /greater /question % 0x40 /at /A /B /C /D /E /F /G /H /I /J /K /L /M /N /O % 0x50 /P /Q /R /S /T /U /V /W /X /Y /Z /bracketleft /backslash /bracketright /asciicircum /underscore % 0x60 /quoteleft /a /b /c /d /e /f /g /h /i /j /k /l /m /n /o % 0x70 /p /q /r /s /t /u /v /w /x /y /z /braceleft /bar /braceright /asciitilde /.notdef % rubout; ASCII ends % 0x80 /.notdef /.notdef /quotesinglbase /florin /quotedblbase /ellipsis /dagger /daggerdbl /circumflex /perthousand /Scaron /guilsinglleft /OE /.notdef /.notdef /.notdef % 0x90 /.notdef /.notdef /.notdef /quotedblleft /quotedblright /bullet /endash /emdash /tilde /trademark /scaron /guilsinglright /oe /.notdef /.notdef /Ydieresis % 0xA0 /.notdef % nobreakspace /exclamdown /cent /sterling /currency /yen /brokenbar /section /dieresis /copyright /ordfeminine /guillemotleft /logicalnot /hyphen % Y&Y (also at 45); Windows' softhyphen /registered /macron % 0xD0 /degree /plusminus /twosuperior /threesuperior /acute /mu /paragraph /periodcentered /cedilla /onesuperior /ordmasculine /guillemotright /onequarter /onehalf /threequarters /questiondown % 0xC0 /Agrave /Aacute /Acircumflex /Atilde /Adieresis /Aring /AE /Ccedilla /Egrave /Eacute /Ecircumflex /Edieresis /Igrave /Iacute /Icircumflex /Idieresis % 0xD0 /Eth /Ntilde /Ograve /Oacute /Ocircumflex /Otilde /Odieresis /multiply /Oslash /Ugrave /Uacute /Ucircumflex /Udieresis /Yacute /Thorn /germandbls % 0xE0 /agrave /aacute /acircumflex /atilde /adieresis /aring /ae /ccedilla /egrave /eacute /ecircumflex /edieresis /igrave /iacute /icircumflex /idieresis % 0xF0 /eth /ntilde /ograve /oacute /ocircumflex /otilde /odieresis /divide /oslash /ugrave /uacute /ucircumflex /udieresis /yacute /thorn /ydieresis ] def %%EndProcSet %%BeginProcSet: texps.pro %! TeXDict begin/rf{findfont dup length 1 add dict begin{1 index/FID ne 2 index/UniqueID ne and{def}{pop pop}ifelse}forall[1 index 0 6 -1 roll exec 0 exch 5 -1 roll VResolution Resolution div mul neg 0 0]/Metrics exch def dict begin Encoding{exch dup type/integertype ne{pop pop 1 sub dup 0 le{pop}{[}ifelse}{FontMatrix 0 get div Metrics 0 get div def} ifelse}forall Metrics/Metrics currentdict end def[2 index currentdict end definefont 3 -1 roll makefont/setfont cvx]cvx def}def/ObliqueSlant{ dup sin S cos div neg}B/SlantFont{4 index mul add}def/ExtendFont{3 -1 roll mul exch}def/ReEncodeFont{CharStrings rcheck{/Encoding false def dup[exch{dup CharStrings exch known not{pop/.notdef/Encoding true def} if}forall Encoding{]exch pop}{cleartomark}ifelse}if/Encoding exch def} def end %%EndProcSet %%BeginFont: CMMI10 %!PS-AdobeFont-1.1: CMMI10 1.100 %%CreationDate: 1996 Jul 23 07:53:57 % Copyright (C) 1997 American Mathematical Society. All Rights Reserved. 11 dict begin /FontInfo 7 dict dup begin /version (1.100) readonly def /Notice (Copyright (C) 1997 American Mathematical Society. All Rights Reserved) readonly def /FullName (CMMI10) readonly def /FamilyName (Computer Modern) readonly def /Weight (Medium) readonly def /ItalicAngle -14.04 def /isFixedPitch false def end readonly def /FontName /CMMI10 def /PaintType 0 def /FontType 1 def /FontMatrix [0.001 0 0 0.001 0 0] readonly def /Encoding 256 array 0 1 255 {1 index exch /.notdef put} for dup 58 /period put readonly def /FontBBox{-32 -250 1048 750}readonly def /UniqueXX 5087385 def currentdict end currentfile eexec 80347982ab3942d930e069a70d0d48311d725e830d1c76fba12e12486e989c98 74c2b527f0925722787027f44470d484262c360cdfdddf3657533a57bb16f730 48bfbbfcb73a650484015441fdc837add94ac8fbd2022e3ec8f115d4b4bb7b7f 15388f22cc6198efe768bd9fceb3446ee4a8dc27d6cd152485384ef5f59381ff da43f2d20c8fb08aa27ab2015b774db10dacfdcd33e60f178c461553146ab427 bdd7da12534ba078ad3d780414930da4f8d58abefd45db119b10eb409dd89792 3c6e705479464a4b310b58348c4b42393988fef4925cf984423aaf65fea9f0e6 4629953bcf50b919d968d99bd185f83112b2759cc411764e9bde677f57c5ee5a c555448d5f81a16259ded1e11bf4119d53e8ab07a802df900d3a2d5ccc1c6876 d29c5e9effb7af3ef83400b0910c07873a8c56fa7b1eb1ba426043b00cc95dbe dc6e136cbbbcb3f67509964f9f281ebf81fe5b018122eaf66c4a838487e82e18 6e006093042848a903efb3469ab6b4049767aadb95c30408dfd58d8a10f4cb22 168decd9f3ee100f07b49aa44c92139b669cc312ba20192454eb2375be6284b0 26659d964b96ae82d4942e758027fcf23c25ed01115af27ce7f20efe2a822bb6 84004f20243a49c9e93301fc21b80815c033c3e2ba58ef53da2157d524b395f2 b37abca13bc6a2f42e824ab7e47106176b0d6db267fbb795ac7425582df2e3dc 55863468a9200742bd7b552c48f8cf58bc21343bd3b95abfa140f33f37c6f3f7 8b0d8a5154eb7c1f62ec598267f13e841a3e64172663935ac8b665d86540d316 ddece329c008049c5e74b27d59022c5515059bc3b89370b1bc6a169c888bb325 e0b74282d6f053a50da4024ed1e433271a32ab8c17d41c632b41cf9f3ecd5fe1 24daf7aea7ce8a63047b245822930d517df7baaafa69d2d17f7d93cebd45416d f3459365434123a76ccf883a4973bab19807e1f0c4bab03a45f7ed69ff2660ff 3963e4def11001eec4238c368a39d874fd30b3c14f4186ec7700fbce22abe468 eb32baf7b0164f8f21a9b5e706b91411faaa44467cb2180ab03de375c1ab93e9 76e11ab92fdd4a7280a6d1a8dc65c4c89d04c8ed6988045a2a3de9a4c7b1efd3 75b79ee3d49569213fcb818f6f1cf250f5e595c4b2d090c769e9fc42bfcd2e99 512d0cfa089c727bf03d886a3f35f6b38197e9407725810a0448593ee7e8d68c c7f44c03ebbd363e6059b5728e35e35a1c31a1b8883a3bdea7e2b7fa7a9f5f86 9b5ebc71fe69ea4fd3162ee4de21acce7e177c6c9d2b2aa6712008319f3069a3 33348cae6a5958ae5ad50a423c4bc17facf60c109e33245b7c4c9f043e6e8d5b f71f578d6cd1fe0d204500495c52ba0652ee8efd17f753764a4c675386e7a169 0323b6889746191d684e59828d032049d16e1689 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 cleartomark %%EndFont %%BeginFont: CMSY10 %!PS-AdobeFont-1.1: CMSY10 1.0 %%CreationDate: 1991 Aug 15 07:20:57 % Copyright (C) 1997 American Mathematical Society. All Rights Reserved. 11 dict begin /FontInfo 7 dict dup begin /version (1.0) readonly def /Notice (Copyright (C) 1997 American Mathematical Society. All Rights Reserved) readonly def /FullName (CMSY10) readonly def /FamilyName (Computer Modern) readonly def /Weight (Medium) readonly def /ItalicAngle -14.035 def /isFixedPitch false def end readonly def /FontName /CMSY10 def /PaintType 0 def /FontType 1 def /FontMatrix [0.001 0 0 0.001 0 0] readonly def /Encoding 256 array 0 1 255 {1 index exch /.notdef put} for dup 15 /bullet put readonly def /FontBBox{-29 -960 1116 775}readonly def /UniqueXX 5000820 def currentdict end currentfile eexec 9b9c1569015f2c1d2bf560f4c0d52257bac8ced9b09a275ab231194ecf829352 05826f4e975dcecec72b2cf3a18899ccde1fd935d09d813b096cc6b83cdf4f23 b9a60db41f9976ac333263c908dcefcdbd4c8402ed00a36e7487634d089fd45a f4a38a56a4412c3b0baffaeb717bf0de9ffb7a8460bf475a6718b0c73c571145 d026957276530530a2fbefc6c8f67052788e6703bb5ee49533870bca1f113ad8 3750d597b842d8d96c423ba1273ddd32f3a54a912a443fcd44f7c3a6fe3956b0 aa1e784aaec6fce08dae0c76da9d0a3eba57b98a6233d9e9f0c3f00fcc6b2c6a 9ba23af389e6dfff4efec3de05d6276c6be417703ce508377f25960ef4ed83b4 9b01b873f3a639ce00f356229b6477a081933fef3bb80e2b9dffa7f75567b1fa 4d739b772f8d674e567534c6c5bbf1cf615372be20b18472f7aa58be8c216dbd df81cc0a86b6d8318ca68fe22c8af13b54d7576fe4ca5a7af9005ea5cc4edb79 c0ab668e4fec4b7f5a9eb5f0e4c088cd818ecc4feb4b40ec8bd2981bf2336074 b64c4301c39221774c4482ad2518015bc80e2e96dabb4bdf5fbde00562af1aa6 90336bfc814e8312dd70402bf02d57a3ffe05e732cdfddafc00d318f83a79439 5eb8460eed2f5f1e7a2726c02f81b69917baaf163033a49dc10f61f35c72d3c9 33039c21bc71a9b4b25bc7573429924340b16d1cdfe6a6b93450c50f15b6229f be901e24b3d21bf434b7f60802dfa0bb3462a12bff97ca01cf591cba483a1699 da979b8e79d363c1849565820b5d62eb82d4e481b26944bdb6f0f02642252a86 35e29f2f3f5faa4444aa607bfd3bf4ac98653fed 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 cleartomark %%EndFont TeXDict begin 39158280 55380996 1000 600 600 (paper.dvi) @start /Fa 197[18 58[{}1 66.4176 /CMMI10 rf /Fc 170[48 2[41 8[22 73[{TeXBase1Encoding ReEncodeFont}3 66.4176 /Times-Italic rf /Fd 133[45 45 45 45 1[45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 6[45 1[45 45 1[45 45 45 45 1[45 45 45 45 45 2[45 1[45 1[45 45 45 45 45 2[45 1[45 1[45 6[45 45 45 1[45 45 45 45[{ TeXBase1Encoding ReEncodeFont}53 74.7198 /Courier rf /Fe 103[40 29[40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 1[40 40 40 40 40 40 40 40 40 3[40 1[40 40 40 40 40 40 40 40 40 40 1[40 40 40 40 40 40 1[40 40 40 1[40 40 40 40 40 1[40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 1[40 40 40 40 40 40 1[40 40 40 33[{ TeXBase1Encoding ReEncodeFont}80 66.4176 /Courier rf /Fg 240[37 15[{}1 74.7198 /CMSY10 rf /Fh 133[29 33 33 50 33 37 21 29 29 37 37 37 37 54 21 33 21 21 37 37 21 33 37 33 37 37 8[46 1[46 54 42 37 46 1[46 54 50 62 42 2[25 54 2[46 54 50 1[46 6[25 6[37 37 37 37 1[19 25 19 2[25 25 37[37 2[{TeXBase1Encoding ReEncodeFont}54 74.7198 /Times-Italic rf /Fi 7[37 96[75 2[33 33 24[33 37 37 54 37 37 21 29 25 37 37 37 37 58 21 37 21 21 37 37 25 33 37 33 37 33 3[25 1[25 46 1[54 71 54 54 46 42 50 54 42 54 54 66 46 54 29 25 54 54 42 46 54 50 50 54 5[21 21 37 37 37 37 37 37 37 37 37 37 21 19 25 19 2[25 25 1[58 28[25 5[42 42 2[{TeXBase1Encoding ReEncodeFont}79 74.7198 /Times-Roman rf /Fj 82[33 51[50 50 72 50 55 33 39 44 55 55 50 55 83 28 55 1[28 55 50 33 44 55 44 55 50 8[72 2[72 66 55 72 1[61 78 72 94 66 78 1[39 78 78 61 66 72 72 66 72 6[33 50 50 50 50 50 50 50 50 50 50 1[25 43[55 2[{TeXBase1Encoding ReEncodeFont}58 99.6264 /Times-Bold rf /Fk 105[46 28[42 2[42 46 23 42 28 2[46 46 4[18 46 1[23 46 1[42 46 46 11[60 51 55 60 5[46 2[23 5[60 55 55 20[23 5[55 38[{TeXBase1Encoding ReEncodeFont}27 83.022 /Helvetica rf /Fl 7[61 125[50 2[72 1[55 28 50 33 2[55 55 83 22 50 1[22 55 2[55 55 50 55 55 13[66 4[72 83 1[66 1[28 7[66 101 17[28 46[{TeXBase1Encoding ReEncodeFont}27 99.6264 /Helvetica rf /Fm 138[91 2[58 2[91 91 133 4[91 91 50 83 1[83 1[83 8[100 4[100 5[124 91 7[108 2[108 6[50 58[{TeXBase1Encoding ReEncodeFont}18 149.44 /Helvetica-Bold rf end %%EndProlog %%BeginSetup %%Feature: *Resolution 600dpi TeXDict begin %%BeginPaperSize: a4 a4 %%EndPaperSize %%EndSetup %%Page: 1 1 1 0 bop 706 107 a Fm(DSD:)40 b(A)i(Sc)o(hema)f(Langua)o(g)q(e)i(f)m(or) f(XML)441 445 y Fl(Nils)28 b(Klar)q(lund)318 532 y Fk(A)-10 b(T&T)24 b(Labs\226Research)157 653 y Fl(klar)q(lund@research.att.com) 1633 445 y(Anders)30 b(M\370)-5 b(ller)1421 532 y Fk(BRICS)n(,)24 b(Univ)n(ersity)f(of)g(Aarhus)1527 664 y Fl(amoeller@br)q(ics)o(.dk) 2618 445 y(Michael)29 b(I.)e(Schw)o(ar)t(tzbach)2640 532 y Fk(BRICS)n(,)d(Univ)n(ersity)e(of)i(Aarhus)2860 664 y Fl(mis@br)q(ics)o(.dk)-152 1202 y Fj(ABSTRA)-5 b(CT)-152 1293 y Fi(XML)26 b(\(eXtensible)g(Markup)h(Language\))g(is)f (a)g(linear)g(syntax)g(for)g(trees,)-152 1380 y(which)k(has)g(gathered) f(a)h(remarkable)g(amount)g(of)f(interest)g(in)g(industry)-5 b(.)-152 1467 y(The)25 b(acceptance)h(of)f(XML)f(opens)i(ne)n(w)f(v)o (enues)h(for)e(the)h(application)h(of)-152 1554 y(formal)i(methods)h (such)g(as)f(speci\002cation)g(of)g(abstract)g(syntax)h(tree)f(sets) -152 1642 y(and)20 b(tree)f(transformations.)-152 1816 y(A)i(notation)h(for)f(de\002ning)h(a)f(set)g(of)g(XML)g(trees)g(is)f (called)i(a)f Fh(sc)o(hema)g(lan-)-152 1903 y(gua)o(g)o(e)p Fi(.)48 b(Such)27 b(trees)f(correspond)i(to)f(a)f(speci\002c)h(user)f (domain,)j(such)f(as)-152 1990 y(XHTML,)18 b(the)h(class)g(of)g(XML)g (documents)h(that)f(mak)o(e)h(sense)f(as)g(HTML.)-152 2165 y(A)i(useful)g(schema)h(notation)g(must:)54 b(identify)22 b(most)f(of)g(the)g(syntactic)g(re-)-152 2252 y(quirements)29 b(that)g(the)f(documents)i(in)e(the)g(user)h(domain)g(follo)n(w;)k (allo)n(w)-152 2339 y(ef)n(\002cient)23 b(parsing;)j(be)d(readable)h (to)f(the)g(user;)i(allo)n(w)e(limited)g(tree)g(trans-)-152 2426 y(formations)i(corresponding)h(to)e(the)g(insertion)g(of)g(def)o (aults;)j(be)d(modular)-152 2513 y(and)c(e)o(xtensible)f(to)g(support)h (e)n(v)o(olving)g(classes)f(of)g(XML)g(documents.)-152 2688 y(In)25 b(the)g(present)g(paper)m(,)h(we)f(introduce)h(the)e(DSD)g (\(Document)i(Structure)-152 2775 y(Description\))e(notation)g(as)f (our)h(bid)f(on)h(ho)n(w)g(to)f(meet)g(the)h(requirements)-152 2862 y(abo)o(v)o(e.)-152 3036 y(The)32 b(e)o(xpressi)n(v)o(eness)h(of)e (DSDs)g(goes)h(f)o(ar)f(be)o(yond)i(the)f(DTD)e(concept)-152 3124 y(that)d(is)g(already)g(b)o(uild)g(into)g(XML)g(and)g(SGML.)f(In)h (particular)m(,)i(we)d(ad-)-152 3211 y(v)o(ocate)18 b(the)f(use)h(of)f (nonterminals)h(in)f(a)h(top-do)n(wn)g(manner)m(,)g(coupled)h(with)-152 3298 y(boolean)25 b(logic)e(and)h(re)o(gular)f(e)o(xpressions)i(to)e (describe)g(ho)n(w)h(constraints)-152 3385 y(on)f(tree)f(nodes)h (depend)h(on)f(their)f(conte)o(xt.)33 b(W)-6 b(e)22 b(also)g(support)h (a)f(general,)-152 3472 y(declarati)n(v)o(e)d(mechanism)f(for)g (inserting)g(def)o(ault)g(elements)g(and)g(attrib)o(utes)-152 3559 y(that)j(is)f(reminiscent)h(of)f(Cascading)i(Style)e(Sheets)g (\(CSS\),)f(a)h(w)o(ay)h(of)g(ma-)-152 3647 y(nipulating)31 b(formatting)f(instructions)h(in)e(HTML)h(that)f(is)h(b)o(uilt)f(into)h (all)-152 3734 y(modern)17 b(bro)n(wsers.)23 b(Finally)-5 b(,)16 b(we)f(include)i(a)f(simple)g(technique)h(for)e(e)n(v)o(olv-) -152 3821 y(ing)k(DSD)g(documents)h(through)g(selecti)n(v)o(e)f (rede\002nitions.)-152 3995 y(The)31 b(DSD)e(language)j(is)e (completely)h(self-describable,)j(meaning)e(that)-152 4082 y(the)19 b(syntax)g(of)f(le)o(gal)g(DSD)f(documents)j(together)f (with)f(all)g(static)f(require-)-152 4170 y(ments)24 b(are)f(captured)h(in)f(a)g(special)h(DSD)e(document,)k(the)d(meta-DSD) g(of)-152 4257 y(less)c(than)g(500)h(lines.)-152 4431 y(W)-6 b(e)17 b(relate)g(DSDs)f(to)h(other)g(recent)h(XML)e(schema)i (languages)h(and)f(to)f(lan-)-152 4518 y(guages)j(for)f(abstract)g (syntax)h(description.)2040 1202 y(The)c(DSD)g(language)i(is)e(fully)g (implemented)i(and)f(is)f(a)o(v)n(ailable)g(in)h(an)f(open)2040 1289 y(source)k(distrib)o(ution.)2040 1522 y Fj(1.)99 b(INTR)m(ODUCTION)2040 1613 y Fi(XML)24 b(\(eXtensible)h(Markup)h (Language\)[5])g(is)e(a)h(syntax)g(deri)n(v)o(ed)g(from)2040 1700 y(SGML)18 b(for)h(markup)h(of)f(te)o(xt.)j(XML)d(is)f (particularly)h(interesting)g(to)g(com-)2040 1788 y(puter)g(scientists) g(because)i(the)e(markup)h(notation)g(is)e(really)h(nothing)i(b)o(ut)d (a)2040 1875 y(w)o(ay)k(of)g(specifying)h(labeled)f(trees.)32 b(The)21 b(tree)h(vie)n(w)g(and)g(the)g(con)m(v)o(enient)2040 1962 y(SGML)h(syntax)i(of)f(HTML)g(ha)o(v)o(e)g(been)g(important)h(to)f (the)g(de)n(v)o(elopment)2040 2049 y(of)j(the)h(W)-6 b(orld)27 b(W)m(ide)f(W)-6 b(eb)m(.)48 b(Recently)-5 b(,)30 b(the)d(general)h(XML)f(syntax)h(has)2040 2136 y(gathered)e(a)f(remarkable)h(amount)h(of)e(interest)g(in)g(industry)h (as)f(a)h(w)o(ay)f(of)2040 2224 y(e)o(xchanging)c(data)f(such)g(as)f (documents,)i(databases,)f(or)f(computed)i(infor)o(-)2040 2311 y(mation.)2040 2485 y(W)-6 b(e)19 b(ar)o(gue)h(in)g(this)f (document)i(that)f(the)f(acceptance)i(of)f(XML)f(opens)i(ne)n(w)2040 2572 y(w)o(ays)e(of)f(introducing)h(formal)f(computer)h(science)g (techniques)g(into)f(prac-)2040 2659 y(tice.)26 b(Speci\002cally)-5 b(,)20 b(we)g(study:)52 b(the)20 b(formal)g(speci\002cation)g(of)h(XML) e(lan-)2040 2747 y(guages,)24 b(that)e(is)g(sets)g(of)g(abstract)g (syntax)i(trees,)e(and)h(tree-based)g(def)o(ault)2040 2834 y(insertion)g(mechanisms,)h(that)e(is,)h(tree)f(transformations.) 67 b(Both)23 b(aspects)2040 2921 y(are)30 b(part)f(of)h(the)g(DSD)e (\(Document)j(Structure)e(Description\))h(notation,)2040 3008 y(which)c(we)f(introduce)i(informally)e(in)h(this)f(article.)42 b(Before)25 b(we)h(e)o(xplain)2040 3095 y(DSDs,)e(let)f(us)h(mention)h (some)f(fundamental)h(XML)f(ef)n(forts)f(that)h(are)g(al-)2040 3182 y(ready)c(standardized)g(\(in)e(the)h(sense)g(of)g(being)h(a)e (W3C)h(recommendation\))2040 3270 y(or)g(under)h(de)n(v)o(elopment:) 2152 3521 y Fg(\017)38 b Fh(CSS)25 b(\(Cascading)g(Style)g(Sheet\))f Fi(allo)n(ws)h(XML)f(documents)i(to)e(be)2227 3608 y(rendered)i (visually)g(\(CSS2[1])f(is)g(the)g(latest)g(of)n(\002cial)g(recommen-) 2227 3695 y(dation\);)2152 3876 y Fg(\017)38 b Fh(tr)o(ansformation)27 b(langua)o(g)o(e)h Fi(de\002nes)e(rather)g(general)g(transforma-)2227 3963 y(tions)14 b(between)i(XML)e(languages)i(\(XSL)-7 b(T[6],)14 b(which)g(is)g(also)h(called)2227 4050 y(a)25 b(style)h(sheet)g(language,)i(became)f(an)e(of)n(\002cial)g (recommendation)2227 4137 y(recently\);)2152 4318 y Fg(\017)38 b Fh(linking)18 b Fi(de\002nes)g(generalized)g(links)g(between)g(XML)f (resources)i(\(X)2227 4406 y(Link[11])29 b(and)g(XPointer[10])g(are)f (almost)h(completed,)j(whereas)2227 4493 y(XP)o(ath[7],)c(a)f(simple)f (e)o(xpression)i(language)h(underlying)f(se)n(v)o(eral)2227 4580 y(of)20 b(the)h(XML)f(ef)n(forts,)g(has)h(just)f(been)h(turned)g (into)g(an)g(of)n(\002cial)f(rec-)2227 4667 y(ommendation\);)2152 4848 y Fg(\017)38 b Fh(sc)o(hema)28 b(langua)o(g)o(e)i Fi(is)c(a)i(current)f(ef)n(fort)h(similar)e(to)h(ours)h(for)f(de-)2227 4935 y(scribing)f(the)f(formal)g(syntax)h(of)f(XML)g(applications)h (\(XML)f(has)2227 5022 y(already)20 b(inherited)f(the)g(DTD)g(concept)h (from)f(SGML,)f(b)o(ut)h(this)g(no-)2227 5109 y(tation)g(is)f (considered)j(inadequate)f(by)f(man)o(y\);)h(and)2152 5290 y Fg(\017)38 b Fh(query)30 b(langua)o(g)o(e)p Fi(,)j(which)c(will) f(generalize)i(database)g(queries)f(to)2227 5378 y(semi-structured)19 b(data)h(represented)g(by)f(XML)g(documents.)p eop %%Page: 2 2 2 1 bop -152 -69 a Fi(In)15 b(the)f(area)h(of)f(schema)i(languages,)g (se)n(v)o(eral)f(proposals,)h(such)f(as)g(DDML[2],)-152 19 y(DCD[3],)23 b(SO)m(X[9],)g(Schematron[14],)h(and)f(RELAX[19])f(ha)o (v)o(e)h(already)-152 106 y(emer)o(ged.)39 b(Recently)-5 b(,)25 b(W3C)f(has)g(issued)g(an)h(of)n(\002cial)e(draft)h(proposal)h (for)-152 193 y(XML)19 b(Schema,)g(which)g(has)h(been)f(met)g(with)g (intense)g(debate.)-152 367 y(Our)f(DSD)g(proposal)h(is)f(more)g (ambitious)h(than)f(other)h(proposals)g(with)f(the)-152 454 y(e)o(xception)31 b(of)f(Schematron,)j(which)d(is)g(based)h(on)f(a) g(pattern)g(matching)-152 542 y(paradigm)e(instead)f(of)f(a)h(parsing)g (vie)n(w)-5 b(,)28 b(and)f(RELAX,)e(which)i(is)f(more)-152 629 y(e)o(xpressible)21 b(in)f(some)g(re)o(gards.)26 b(A)19 b(DSD)g(de\002nes)h(a)g(grammar)g(for)g(a)g(class)-152 716 y(of)f(XML)g(documents,)h(documentation)h(for)e(that)g(class,)f (and)i(additionally)-152 803 y(a)25 b(CSS-lik)o(e)f(notation)h(for)g (specifying)g(def)o(ault)h(parts)e(of)h(documents.)42 b(A)-152 890 y(DSD)18 b(is)h(itself)f(an)h(XML)g(document.)-152 1065 y(W)-6 b(e)27 b(recall)g(that)g(an)h(XML)f(document)i(consists)e (of)h(elements)f(that)g(ha)o(v)o(e)-152 1152 y(attrib)o(utes)c(and)h (content;)h(the)f(latter)e(is)h(a)g(sequence)i(of)e(te)o(xt)g (interspersed)-152 1239 y(with)c(subelements.)24 b(F)o(or)18 b(an)i(e)o(xample,)f(tak)o(e)g(the)g(HTML)g(markup)-118 1326 y Fe(
)-39 1413 y(Hello)g (there)-118 1500 y()-152 1588 y Fi(This)23 b(is)g(an)h(element)f(representing)i(a)e(node)h(labeled)g (\223body\224.)37 b(The)24 b(node)-152 1675 y(has)h(an)f(attrib)o(ute)f (named)i(\223class\224)g(and)g(tw)o(o)f(children)g(corresponding)j(to) -152 1762 y(its)20 b(content)i(\(the)e(stuf)n(f)h(between)g(the)g (start)f(tag)h Fd(