idnits 2.17.1 draft-ietf-conneg-feature-algebra-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 42 longer pages, the longest (page 2) being 60 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** The abstract seems to contain references ([2], [3], [1]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (8 July 1998) is 9424 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: '0' is mentioned on line 1125, but not defined -- Looks like a reference, but probably isn't: 'A' on line 1592 -- Looks like a reference, but probably isn't: 'B' on line 1596 -- Looks like a reference, but probably isn't: 'C' on line 1612 -- Looks like a reference, but probably isn't: 'D' on line 1652 -- Looks like a reference, but probably isn't: 'E' on line 1656 -- Looks like a reference, but probably isn't: 'F' on line 1651 -- Looks like a reference, but probably isn't: 'G' on line 1655 -- Looks like a reference, but probably isn't: 'GK' on line 1770 == Unused Reference: '12' is defined on line 2049, but no explicit reference was found in the text == Unused Reference: '15' is defined on line 2067, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. '1' -- Possible downref: Non-RFC (?) normative reference: ref. '2' -- Possible downref: Non-RFC (?) normative reference: ref. '3' -- Possible downref: Non-RFC (?) normative reference: ref. '4' -- Possible downref: Non-RFC (?) normative reference: ref. '5' -- Possible downref: Non-RFC (?) normative reference: ref. '6' ** Obsolete normative reference: RFC 2251 (ref. '7') (Obsoleted by RFC 4510, RFC 4511, RFC 4512, RFC 4513) ** Obsolete normative reference: RFC 2254 (ref. '8') (Obsoleted by RFC 4510, RFC 4515) ** Obsolete normative reference: RFC 2068 (ref. '9') (Obsoleted by RFC 2616) ** Obsolete normative reference: RFC 2234 (ref. '10') (Obsoleted by RFC 4234) -- Possible downref: Non-RFC (?) normative reference: ref. '11' -- Possible downref: Non-RFC (?) normative reference: ref. '12' -- Possible downref: Non-RFC (?) normative reference: ref. '13' -- Possible downref: Non-RFC (?) normative reference: ref. '14' -- Possible downref: Non-RFC (?) normative reference: ref. '15' -- Possible downref: Non-RFC (?) normative reference: ref. '16' -- Possible downref: Non-RFC (?) normative reference: ref. '17' Summary: 13 errors (**), 0 flaws (~~), 6 warnings (==), 23 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 IETF media feature registration WG Graham Klyne 3 Internet draft Content Technologies/5GM 4 8 July 1998 5 Expires: January 1999 7 An algebra for describing media feature sets 8 10 Status of this memo 12 This document is an Internet-Draft. Internet-Drafts are working 13 documents of the Internet Engineering Task Force (IETF), its areas, 14 and its working groups. Note that other groups may also distribute 15 working documents as Internet-Drafts. 17 Internet-Drafts are draft documents valid for a maximum of six 18 months and may be updated, replaced, or obsoleted by other 19 documents at any time. It is inappropriate to use Internet-Drafts 20 as reference material or to cite them other than as ``work in 21 progress''. 23 To view the entire list of current Internet-Drafts, please check 24 the "1id-abstracts.txt" listing contained in the Internet-Drafts 25 Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net 26 (Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au 27 (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US 28 West Coast). 30 Copyright (C) 1998, The Internet Society 32 Abstract 34 A number of Internet application protocols have a need to provide 35 content negotiation for the resources with which they interact [1]. 36 A framework for such negotiation is described in [2]. Part of this 37 framework is a way to describe the range of media features which 38 can be handled by the sender, recipient or document transmission 39 format of a message. A format for a vocabulary of individual media 40 features and procedures for registering media features are 41 presented in [3]. 43 This document describes an algebra and syntax that can be used to 44 define feature sets which are formed from combinations and 45 relations involving individual media features. Such feature sets 46 are used to describe the media feature handling capabilities of 47 message senders, recipients and file formats. 49 An algebra for describing media feature sets 51 This document also outlines an algorithm for feature set matching. 52 (In its present form, it needs considerable refinement, but does 53 indicates the availability of a deterministic solution.) 55 Table of contents 57 1. Introduction.............................................3 58 1.1 Structure of this document ...........................4 59 1.2 Discussion of this document ..........................4 60 1.3 Amendment history ....................................4 61 1.4 Unfinished business ..................................5 62 2. Terminology and definitions..............................5 63 3. Media feature values.....................................6 64 3.1 Complexity of feature algebra ........................6 65 3.2 Sufficiency of simple types ..........................7 66 3.2.1 Unstructured data types..........................7 67 3.2.2 Cartesian product................................8 68 3.2.3 Discriminated union..............................8 69 3.2.4 Array............................................8 70 3.2.5 Powerset.........................................9 71 3.2.6 Sequence.........................................9 72 4. Feature set predicates...................................9 73 4.1 An algebra for data file format selection ............10 74 4.1.1 Describing feature sets..........................11 75 4.1.1.1 Feature value ranges 11 76 4.1.1.2 Feature value combinations 12 77 4.1.1.3 Using meta-features to group features 13 78 4.1.2 Content, sender and recipient capabilities.......14 79 4.2 Conclusion and proposal ..............................14 80 5. Indicating preferences...................................15 81 5.1 Combining preferences ................................15 82 5.2 Representing preferences .............................15 83 6. Feature set representation...............................17 84 6.1 Textual representation of predicates .................18 85 6.2 Arithmetic expressions ...............................19 86 6.3 Named and auxiliary predicates .......................20 87 6.3.1 Defining a named predicate.......................20 88 6.3.2 Invoking named predicates........................21 89 6.3.3 Auxiliary predicates in a filter.................21 90 6.4 Feature set definition examples ......................21 91 6.4.1 Single predicate.................................21 92 6.4.2 Predicate with auxiliary predicate...............22 93 6.5 ASN.1 representation .................................22 94 7. Content negotiation protocol processing..................23 95 7.1 Matching feature sets ................................23 96 7.1.1 Feature set matching strategy....................25 97 7.1.2 Formulating the problem..........................26 98 7.1.3 Simplifying primitive predicates.................26 99 7.1.3.1 Primitive predicate properties 27 101 An algebra for describing media feature sets 103 7.1.4 Conversion to canonical form.....................29 104 7.1.5 Grouping of feature predicates...................31 105 7.1.6 Remove simultaneous equality constraints.........32 106 7.1.7 Merge single-feature constraints.................34 107 7.1.8 Test simultaneous feature constraints............34 108 7.1.8.1 Convex sets 34 109 7.1.8.2 Testing for satisfiability 36 110 7.2 Effect of named predicates ...........................37 111 7.3 Overlapping features .................................37 112 7.4 Unknown feature value data types .....................38 113 7.5 Worked example .......................................38 114 7.6 Algorithm source code ................................38 115 8. Security considerations..................................39 116 9. Copyright................................................40 117 10. Acknowledgements........................................40 118 11. References..............................................41 119 12. Author's address........................................43 121 1. Introduction 123 A number of Internet application protocols have a need to provide 124 content negotiation for the resources with which they interact [1]. 125 A framework for such negotiation is described in [2]. A part of 126 this framework is a way to describe the range of media features 127 which can be handled by the sender, recipient or document 128 transmission format of a message. 130 Descriptions of media feature capabilities need to be based upon 131 some underlying vocabulary of individual media features. A format 132 for such a vocabulary and procedures for registering media features 133 are presented in [3]. 135 This document defines an algebra which can be used to describe 136 feature sets which are formed from combinations and relations 137 involving individual media features. Such feature sets are used to 138 describe the media handling capabilities of message senders, 139 recipients and file formats. 141 This document also outlines a syntax for describing feature sets, 142 and an algorithm for feature set matching. 144 The feature set algebra is built around the principle of using 145 feature set predicates as "mathematical relations" which define 146 constraints on feature handling capabilities. The idea is that the 147 same form of feature set expression can be used to describe sender, 148 receiver and file format capabilities. This has been loosely 149 modelled on the way that the Prolog programming language uses Horn 150 Clauses to describe a set of result values. 152 An algebra for describing media feature sets 154 In developing the algebra, examples are given using notation drawn 155 from the Prolog programming language. Later, a syntax for 156 expressing feature predicates is suggested, based on LDAP search 157 filters. Finally, an algorithm for feature set matching is 158 described. 160 1.1 Structure of this document 162 The main part of this draft addresses the following main areas: 164 Section 2 introduces and references some terms which are used with 165 special meaning. 167 Section 3 discusses constraints on the data types allowed for 168 individual media feature values. 170 Section 4 introduces and describes the algebra used to construct 171 feature set descriptions with expressions containing media 172 features. The first part of this section contains a development of 173 the ideas, and the second part contains the conclusions and 174 proposed algebra. 176 Section 5 introduces and describes extensions to the algebra for 177 indicating preferences between different feature sets. 179 Section 6 contains a description of recommended representations for 180 describing feature sets based on the previously-described algebra. 182 1.2 Discussion of this document 184 Discussion of this document should take place on the content 185 negotiation and media feature registration mailing list hosted by 186 the Internet Mail Consortium (IMC): 188 Please send comments regarding this document to: 190 ietf-medfree@imc.org 192 To subscribe to this list, send a message with the body 'subscribe' 193 to "ietf-medfree-request@imc.org". 195 To see what has gone on before you subscribed, please see the 196 mailing list archive at: 198 http://www.imc.org/ietf-medfree/ 200 1.3 Amendment history 202 00a 11-Mar-1998 203 Document initially created. 205 An algebra for describing media feature sets 207 01a 05-May-1998 208 Mainly-editorial revision of sections describing the 209 feature types and algebra. Added section on indicating 210 preferences. Added section describing feature predicate 211 syntax. Added to security considerations (based on fax 212 negotiation scenarios draft). 214 01b 25-Jun-1998 215 New Internet draft boilerplate in 'status' preface. 216 Review and rationalization of sections on feature 217 combinations. Added numeric expressions, named 218 predicates and auxiliary predicates as options in the 219 syntax. Added examples of text string predicate 220 representation. 222 02a 08-Jul-1998 223 Added chapter on protocol processing considerations, and 224 in particular outlined an algorithm for feature set 225 matching. Added restrictions to the form of arithmetic 226 expression to allow deterministic feature set matching. 228 1.4 Unfinished business 230 . Array values: are they needed? (section 3.2.4) 232 . Matching feature sets (section 7.1). As described, the algorithm 233 is rather clunky and ad-hoc, and would bear considerable 234 refinement. There is also much work to tidy it up, as noted in 235 comments throughout that section. 237 . Discuss determination of qvalues in the feature set matching 238 algorithm. 240 . Use of unknown data types for feature values (section 7.3) 242 . Add source code for feature matching implementation. 244 . Should ASN.1 representation be pursued? If so, should it be 245 aligned with LDAP filter representation? (section 6.5) 247 2. Terminology and definitions 249 Feature Collection 250 is a collection of different media features and 251 associated values. This might be viewed as describing a 252 specific rendering of a specific instance of a document 253 or resource by a specific recipient. 255 An algebra for describing media feature sets 257 Feature Set 258 is a set of zero, one or more feature collections. 260 Feature set predicate 261 A function of an arbitrary feature collection value which 262 returns a Boolean result. A TRUE result is taken to mean 263 that the corresponding feature collection belongs to some 264 set of media feature handling capabilities defined by 265 this predicate. 267 Other terms used in this draft are defined in [2]. 269 3. Media feature values 271 This document assumes that individual media feature values are 272 simple atomic values: 274 . Boolean values 276 . Enumerated values 278 . Text string values (treated as atomic entities, like enumerated 279 value tokens). 281 . Numeric values 283 More complex media feature values might be accommodated, but they 284 would (a) be undesirable because they would complicate the algebra, 285 and (b) are not necessary. 287 These statements are justified in the following sub-sections. 289 NOTE 291 The following sub-sections are not part of the algebraic 292 framework description, and may be skipped by readers not 293 concerned with design rationale. 295 3.1 Complexity of feature algebra 297 Statement (a) above is justified as follows: predicates constructed 298 as expressions containing media feature values must ultimately 299 resolve to a logical combination of feature value tests. 301 A full range of simple tests for all of the data types listed above 302 can be performed based on just two fundamental operations: equality 303 and less-than. All other meaningful tests can be constructed as 304 predicates incorporating these two basic tests. 306 An algebra for describing media feature sets 308 For example: 309 ( a != b ) iff !( a == b ) 310 ( a <= b ) iff !( b < a ) 311 ( a > b ) iff ( b < a ) 312 ( a >= b ) iff !( a < b ) 314 If additional (composite) data types are introduced, then 315 additional operators must be introduced to test their component 316 parts: the addition of just one further comparison operator 317 increases the number of such operators by 50%. 319 3.2 Sufficiency of simple types 321 To justify statement (b), let us first review the range of 322 composite data types that might reasonably be considered. 324 In 1972, a paper "Notes on data structuring" by C. A. R. Hoare was 325 published in the book "Structured Programming" [4]. This was an 326 early formalization of data types used in programming languages, 327 and its content has formed a sufficient basis for describing the 328 data types in almost every programming language which has been 329 developed. This gives good grounds to believe that the type 330 framework is also sufficient for media features. 332 The data types covered by Hoare's paper are: 334 . Unstructured data types: (integer, real, enumeration, ordered 335 enumeration, sub-ranges). 337 . Cartesian product (e.g. C 'struct'). 339 . Discriminated union (e.g. C 'union'). 341 . Array. 343 . Powerset (e.g. Pascal 'SET OF'). 345 . Sequence (e.g. C string, Pascal 'FILE OF'). 347 To demonstrate sufficiency of simple types for media features we 348 must show that the feature-set defining properties of these 349 composite types can be captured using predicates on the simple 350 types described previously. 352 3.2.1 Unstructured data types 354 The unstructured data types noted correspond closely to, and can be 355 represented by the proposed simple value types for media features. 357 An algebra for describing media feature sets 359 3.2.2 Cartesian product 361 A Cartesian product value (e.g. resolution=[x,y]) is easily 362 captured as a collection of two or more separately named media 363 features (e.g. x-resolution=x, y-resolution=y). 365 3.2.3 Discriminated union 367 A discriminated union value is an either/or type of choice. For 368 example, a given workstation might be able to display 16K colours 369 at 1024x768 resolution, OR 256 colours at 1280x1024 resolution. 371 These possibilities are captured by a logical-OR of predicates: 372 ( ( x-resolution <= 1024 ) && 373 ( y-resolution <= 768 ) && 374 ( colours <= 16384 ) ) || 375 ( ( x-resolution <= 1280 ) && 376 ( y-resolution <= 1024 ) && 377 ( colours <= 256 ) ) 379 3.2.4 Array 381 An array represents a mapping from one data type to another. For 382 example, the availability of pens in a pen plotter might be 383 represented by an array which maps a pen number to a colour. 385 If the array index which forms the basis for defining a feature set 386 is assumed to be a constant, then each member can be designated by 387 a feature name which incorporates the index value. For example: 388 Pen-1=black, pen-2=red, etc. 390 Another example where an array might describe a media feature is a 391 colour palette: an array is used to associate a colour value (in 392 terms of RGB or some other colour model) with a colour index value. 393 In this case is possible to envisage a requirement for a particular 394 colour to be loaded in the palette without any knowledge of the 395 index which maps to it. 397 In this case, the colour might be treated as a named Boolean 398 attribute: if TRUE then that colour is deemed to be available in 399 the palette 401 Feature selection based on a variable array index is more 402 difficult, but it is believed that this is not required for media 403 selection. 405 [[I cannot think of any example of feature selection which involves 406 a variable index into an array. If such a feature is presented, an 407 array type could be added to the set of allowable media feature 408 types, and an array selection operator added to the algebra.]] 410 An algebra for describing media feature sets 412 3.2.5 Powerset 414 A powerset is a collection of zero, one or more values from some 415 base set of values. A colour palette may be viewed as a powerset 416 of colour values, or the fonts available in a printer as a powerset 417 of all available fonts. 419 A powerset is very easily represented by a separate Boolean-valued 420 feature for each member of the base set. The value TRUE indicates 421 that the corresponding value is a member of the powerset value. 423 3.2.6 Sequence 425 A sequence is a list of values from some base set of values, which 426 are accessed sequentially. 428 A sequence can be modelled by an array if one assumes integer index 429 values starting at (say) 1 and incrementing by 1 for each 430 successive element of the sequence. 432 Thus, the considerations described above relating to array values 433 can be considered as also applying (in part) to sequence values. 434 That is, if arrays are deemed to be adequately handled, then 435 sequence values too can be handled. 437 4. Feature set predicates 439 A model for data file selection is proposed, based on relational 440 set definition and subset selection, using elements of the Prolog 441 programming language [5] as a descriptive notation for this 442 purpose. 444 NOTE 446 The use of Prolog as a syntax for feature description is 447 NOT being proposed; rather, the Prolog-like notation is 448 used to develop the semantics of an algebra. These 449 semantics could be mapped to any convenient syntax. 451 For the purposes of developing this algebra, examples are drawn 452 from the media features described in "Media Features for Display, 453 Print, and Fax" [6], which in summary are: 455 pix-x=n (Image size, in pixels) 456 pix-y=m 458 res-x=n (Image resolution, pixels per inch) 459 res-y=m 461 An algebra for describing media feature sets 463 UA-media= screen|stationary|transparency|envelope| 464 continuous-long 465 papersize= na-letter|iso-A4|iso-B4|iso-A3|na-legal 467 color=n (Colour depth in bits) 468 grey=n (Grey scale depth in bits) 470 4.1 An algebra for data file format selection 472 The basic idea proposed here is that a feature capability of the 473 original content, sender, data file format or recipient is 474 represented as a predicate applied to a collection of feature 475 values. Under universal quantification (i.e. selecting all 476 possible values that satisfy it), a predicate indicates a range of 477 possible combinations of feature values). 479 This idea is inherent in Prolog clause notation, which is used in 480 the example below to describe a predicate 481 'acceptable_file_format(File)', which yields a set of possible file 482 transfer formats, using other predicates which indicate the file 483 formats available to the sender and feature capabilities of the 484 file format, original content: 486 acceptable_file_format(File) :- 487 sender_available_file_format(File), 488 match_format(File). 490 (Read this statement as: 'File' is an acceptable file format IF it 491 is a format available to the sender AND it matches the requirements 492 defined by 'match_format'.) 494 match_format(File) :- 495 pix_x(File,Px), content_pix_x(Px), recipient_pix_x(Px), 496 pix_y(File,Py), content_pix_x(Py), recipient_pix_y(Py), 497 res_x(File,Rx), content_res_x(Rx), recipient_res_x(Rx), 498 res_y(File,Ry), content_res_y(Ry), recipient_res_y(Ry), 499 colour(File,C), content_colour(C), recipient_colour(C), 500 grey(File,G), content_grey(G), recipient_grey(G), 501 ua_media(File,M), 502 content_ua_media(M), 503 recipient_ua_media(M), 504 papersize(File,P), 505 content_papersize(P), 506 recipient_papersize(P). 508 (Read this as: 'File' satisfies the constraints of 'match_format' 509 IF there is some 'pix_x' feature value 'Px' that is supported by 510 the file format AND is suitable for representing the message 511 content to be sent AND can be displayed by the message recipient, 512 AND there is some 'pix_y' feature ...) 514 An algebra for describing media feature sets 516 Essentially, 'acceptable_file_format' selects a set of file 517 transfer formats from those available (as defined by 518 'sender_available_file_format'), choosing any whose feature 519 capabilities have a non-empty intersection with the feature 520 capabilities of the original content and the recipient. 522 4.1.1 Describing feature sets 524 The above framework suggests file format capabilities are described 525 as enumerated feature sets. As an abstract theory, this works fine 526 but for practical use it has a couple of problems: 528 (a) description of features with a large number of possibilities 530 (b) describing features which are supported in specific 531 combinations 533 A typical case of (a) would be where a feature (e.g. size of image 534 in pixels) can take any value from a range. To present and test 535 each value separately is not a practical proposition, even if it 536 were possible. (A guide here as to what constitutes a practical 537 approach is to make a judgement about the feasibility of writing 538 the corresponding Prolog program.) 540 A typical case of (b) would be where different values for certain 541 features can occur only in combinations (e.g. allowable 542 combinations of resolution and colour depth on a given video 543 display). If the features are treated independently as suggested 544 by the framework above, all possible combinations would be allowed, 545 rather than the specifically allowable combinations. 547 4.1.1.1 Feature value ranges 549 The first issue can be addressed by considering the type of value 550 which can represent the allowed features of a data file format. 551 The features of a specific data file are represented as values from 552 an enumeration (e.g. ua_media, papersize), or a numeric values 553 (integer or rational). The description of allowable file format 554 feature needs to represent all the allowable values. 556 The Prolog clauses used above to describe file format features 557 already allow for multiple enumerated values. Each acts as a 558 mathematical relation to select a subset of the set of file values 559 allowed by the preceding predicates. 561 Section 3 of this document describes proposed media feature value 562 types. 564 An algebra for describing media feature sets 566 For numeric feature values, a sequence of two numbers to represent 567 a closed interval is suggested, where either value may be replaced 568 by an empty list to indicate no limiting value. Thus: 570 [m,n] => { x : m <= x <= n } 571 [m,[]] => { x : m <= x } 572 [[],n] => { x : x <= n } 574 The following Prolog could be used to describe such range matching: 576 feature_match(X,[[],[]]). 577 feature_match(X,[L,[]]) :- L <= X. 578 feature_match(X,[[],H]) :- X <= H. 579 feature_match(X,[L,H]) :- L <= X, X <= H. 580 feature_match(X,X). 582 (This example stretches standard Prolog, which does not support 583 non-integer numbers. The final clause allows 'feature_match' to 584 deal with equality matching for the normal enumerated and text 585 string value case.) 587 Similar constructs might be used with enumeration-valued and 588 string-values features for which an ordering relationship is 589 defined. 591 4.1.1.2 Feature value combinations 593 The approach to representing allowed combinations of feature values 594 presented here is to use additional predicates to describe 595 relationship constraints between them. 597 For example, consider a display capable of handling any x- and y- 598 resolution between 72dpi and 600dpi. This might be represented by 599 the constraint clauses: 601 feature_match(Rx,[72,600]), 602 feature_match(Ry,[72,600]) 604 If x- and y- resolutions are to be further constrained to square or 605 semi-square aspect-ratios, the following additional predicate 606 clause might be added to the feature set description: 608 ( feature_match(Rx,Ry) ; 609 feature_match(Rx,2*Ry) ; 610 feature_match(2*Rx,Ry) ) 612 An algebra for describing media feature sets 614 (Read this clause as: (Rx = Ry) OR (Rx = 2*Ry) OR (2*Rx = Ry).) 616 Another example might be a display which supports 640x480, 800x600 617 and 1024x768 image pixel sizes: 619 ( ( feature_match(Px,640), feature_match(Py,480) ) ; 620 ( feature_match(Px,600), feature_match(Py,800) ) ; 621 ( feature_match(Px,1024), feature_match(Py,768) ) ) 623 This is based on the predicates 'pix_x(File,Px)', 'pix_y(File,Py)', 624 'res_x(File,Rx)' and 'res_y(File,Ry)' from the initial framework 625 above.) 627 4.1.1.3 Using meta-features to group features 629 The expression of feature combinations can sometimes be simplified 630 by introducing "meta-features", or auxiliary predicates, to 631 describe relationship constraints between feature values. 633 Developing the previous examples, given: 635 pix_x(File,Px), 636 pix_y(File,Py), 637 res_x(File,Rx), 638 res_y(File,Ry), 640 We can define meta-features 'pix' and 'res': 642 pix(File,[Px,Py]) :- pix_x(File,Px), pix_y(File,Py). 643 res(File,[Rx,Ry]) :- res_x(File,Rx), res_y(File,Ry). 645 Then the additional constraints: 647 pix(File,[640, 480]). 648 pix(File,[800, 600]). 649 pix(File,[1024,768]). 651 serve to define three allowable pixel image sizes, and: 653 res(File,[Rx,Ry]) :- 654 feature_match(Rx,[72,600]), 655 feature_match(Ry,[72,600]), 656 ( feature_match(Rx,Ry) ; 657 feature_match(Rx,2*Ry) ; 658 feature_match(2*Rx,Ry) ). 660 serves to represent the allowable resolutions described in the 661 previous section. 663 An algebra for describing media feature sets 665 4.1.2 Content, sender and recipient capabilities 667 It has been shown that feature set predicates can be used to 668 describe the capabilities of a particular content file format, and 669 also to represent constraints of feature value combinations. 671 This use of feature predicates is equally applicable to describing 672 the feature handling capabilities of senders, recipients and other 673 elements in a message transmission. 675 4.2 Conclusion and proposal 677 The previous sections show that file format capabilities can be 678 described by feature set predicates: arbitrary logical expressions 679 using AND, OR, NOT logical combining operators, and media feature 680 value matching. Data file features, original content features, 681 sender features and recipient features (and user features) can all 682 be represented in this way. 684 A key insight, which points to this conclusion, is that a 685 collection of feature values can be viewed as describing a specific 686 representation of the content of a specific document (for example, 687 when rendered by a given recipient). The capabilities that we wish 688 to describe, be they sender, file format, recipient or other 689 capabilities, are sets of such feature collections, with the 690 potential to be displayed using any of the feature value 691 collections in the set. 693 This raises a terminology problem, because the term "feature set" 694 can be used to mean a collection of specific feature values and a 695 range of possible feature values. Thus the more restricted 696 definitions of "feature collection" and "feature set" which appear 697 in the terminology section of this document. 699 Original content, data files and recipients (and users) all embody 700 the potential capability to deal with a "feature set". One of the 701 aims of content negotiation is to select an available data file 702 format (availability being circumscribed by the original content 703 and sender capabilities) whose feature set intersection with the 704 recipient feature set is non-empty. (The further issue of 705 preference being deferred for later consideration.) 707 The concept of a mathematical relation as a subset defined by a 708 predicate can be used to define feature sets, using universal 709 quantification (i.e. using the predicate to select from some 710 notional universe of all possible feature collections). 712 An algebra for describing media feature sets 714 Thus, a common framework of predicates can be used to represent the 715 feature capabilities of original content, data file formats, 716 recipients and any other participating entity which may impose 717 constraints on the usable feature sets. 719 Within this framework, it is sufficient to represent individual 720 feature values as Booleans, enumerated values, text strings or 721 numeric ranges. The thesis in section 3 of his document, combined 722 with a study of "Media Features for Display, Print, and Fax" [6], 723 indicate that more complex media feature values can be handled by 724 predicates. 726 5. Indicating preferences 728 5.1 Combining preferences 730 The general problem of describing and combining preferences among 731 feature sets is very much more complex than simply describing 732 allowable feature sets. For example, given two feature sets: 733 {A1,B1} 734 {A2,B2} 736 where: 737 A1 is preferred over A2 738 B2 is preferred over B1 740 Which of the feature sets is preferred? In the absence of 741 additional information or assumptions, there is no generally 742 satisfactory answer to this. 744 The proposed resolution of this issue is simply to assert that 745 preference information cannot be combined. Applied to the above 746 example, any preference information about A1 in relation to A2, or 747 B1 in relation to B2 is not presumed to convey information about 748 preference of {A1,B1} in relation to {A2,B2}. 750 In practical terms, this restricts the application of preference 751 information to top-level predicate clauses. A top-level clause 752 completely defines an allowable feature set; clauses combined by 753 logical-AND operators cannot be top-level clauses. 755 5.2 Representing preferences 757 A convenient way to represent preferences is by numeric "quality 758 values", as used in HTTP "Accept" headers, etc. (see RFC 2068 [9], 759 section 3.9). 761 An algebra for describing media feature sets 763 It has been suggested that numeric quality values, as used in some 764 HTTP negotiations, are misleading and are really just a way of 765 ranking options. Attempts to perform arithmetic on quality values 766 do seem to degenerate into meaningless juggling of numbers. 768 Numeric quality values in the range 0 to 1 (as defined by RFC 2068 769 [9], section 3.9) are used to rank feature sets according to 770 preference. Higher values are preferred over lower values, and 771 equal values are presumed to be equally preferred. Beyond this, 772 the actual number used has no significance, and should not be used 773 as a basis for any arithmetic operation. 775 In the absence of any explicitly applied quality value, a value of 776 "1" is assumed, suggesting an "ideal" option that is equally or 777 more preferred than any other. 779 This approach can be represented by extending the Prolog-based 780 framework of an earlier example as follows: 782 match_format(File,Qvalue) :- 783 match_format(File), 784 Qvalue=1. 786 match_format(File) :- 787 pix(File,[1024,768], 788 res(File,[Rx,Ry]). 790 match_format(File,Qvalue) :- 791 pix(File,[800, 600]), 792 res(File,[Rx,Ry]), 793 Qvalue=0.9. 795 match_format(File,Qvalue) :- 796 pix(File,[640, 480]). 797 res(File,[Rx,Ry]), 798 Qvalue=0.8. 800 res(File,[Rx,Ry]) :- 801 feature_match(Rx,[72,600]), 802 feature_match(Ry,[72,600]), 803 ( feature_match(Rx,Ry) ; 804 feature_match(Rx,2*Ry) ; 805 feature_match(2*Rx,Ry) ). 807 This example applies image preference ranking based solely on the 808 size of the image, provided that the resolution constraints are 809 satisfied. 811 An algebra for describing media feature sets 813 6. Feature set representation 815 The foregoing sections have described a framework and semantics for 816 defining feature sets with predicates applied to feature 817 collections. This section proposes some concrete representations 818 for these feature set predicates. 820 Rather than invent an all-new notation, this proposal adapts a 821 notation already defined for directory access [7,8]. Observe that 822 a feature collection is similar to a directory entry, in that it 823 consists of a collection of named values. Further, the semantics 824 of the mechanism for selecting feature collections from a feature 825 set is in most respects identical to selection of directory entries 826 from a directory. 828 Differences between directory selection (per [7]) and feature set 829 selection described previously are: 831 . Directory selection provides substring-, approximate- and 832 extensible- matching for attribute values. Directory selection 833 may also be based on the presence of an attribute without regard 834 to its value. 836 . Directory selection provides for matching rules which are 837 dependent upon the declared data type of an attribute value. 839 . Feature selection provides for the association of a quality value 840 with a feature predicate as a way of ranking the selected value 841 collections. 843 . Feature selection contains provisions for defining relationships 844 between feature values. 846 The idea of substring matching does not seem to be relevant to 847 feature set selection, and is excluded from these proposals. 849 The idea of extensible matching and matching rules dependent upon 850 data types are facets of a problem not addressed by this memo, but 851 which do not necessarily affect the feature selection syntax. An 852 aspect which might have a bearing on the syntax would be a 853 requirement to specify a matching rule explicitly as part of a 854 selection expression. 856 Testing for the presence of a feature may be useful in some 857 circumstances, but does not sit comfortably within the semantic 858 framework. Feature sets are described by implied universal 859 quantification over predicates, and the absence of reference to a 860 given feature means the set is not constrained by that feature. 861 Against this, it is difficult to define what might be meant by 863 An algebra for describing media feature sets 865 "presence" of a feature, so this option is not included in these 866 proposals. 868 An effect similar to testing for the presence of a feature can be 869 achieved by defining a Boolean-valued feature. 871 6.1 Textual representation of predicates 873 The text representation of a feature set is based on RFC 2254 "The 874 String Representation of LDAP Search Filters" [8], excluding those 875 elements not relevant to feature set selection (discussed above), 876 and adding elements specific to feature set selection (e.g. options 877 to associate quality values with predicates). 879 The format of a feature predicate is defined by the production for 880 "filter" in the following, using the syntax notation of [10]: 882 filter = "(" filtercomp *( ";" parameter ) )" 883 parameter = "q" "=" qvalue 884 / ext-param "=" ext-value 885 qvalue = ( "0" [ "." 0*3DIGIT ] ) 886 / ( "1" [ "." 0*3("0") ] ) 887 ext-param = ALPHA *( ALPHA / DIGIT / "-" ) 888 ext-value = 889 filtercomp = and / or / not / item 890 and = "&" filterlist 891 or = "|" filterlist 892 not = "!" filter 893 filterlist = 1*filter 894 item = simple / set 895 set = attr "=" "[" setentry *( "," setentry ) "]" 896 setentry = value "/" range 897 range = value ".." value 898 simple = attr filtertype value 899 filtertype = equal / greater / less 900 equal = "=" 901 approx = "~=" 902 greater = ">=" 903 less = "<=" 904 attr = ftag 905 value = fvalue 906 ftag = 907 fvalue = 909 (Subject to constraints imposed by the protocol that carries a 910 feature predicate, whitespace characters may appear between any 911 pair of syntax elements or literals that appear on the right hand 912 side of these productions.) 914 An algebra for describing media feature sets 916 As described, the syntax permits parameters (including quality 917 values) to be attached to any "filter" value in the predicate (not 918 just top-level values). Only top-level quality values are 919 recognized. If no explicit quality value is given, a value of 920 '1.0' is applied. 922 NOTE 924 The flexible approach to quality values and other 925 parameter values in this syntax has been adopted for two 926 reasons: (a) to make it easy to combine separately 927 constructed feature predicates, and (b) to provide an 928 extensible tagging mechanism (for example, to incorporate 929 a conceivable requirement to explicitly specify a 930 matching rule). 932 6.2 Arithmetic expressions 934 It can be observed that some feature value constraints (e.g. the 935 aspect ratio constraints in section 4.1.1.2) depend upon being able 936 to express equivalence an arithmetic expression of some feature 937 value (or values) and some other value. 939 To capture this idea, our predicate representation needs to 940 represent arithmetic expressions in addition to just logical 941 combinations of feature comparisons. 943 The syntax for this extends that given previously for "attr": 945 value =/ expr 946 expr = [ "+" / "-" ] term *( ( "+" / "-" ) term ) 947 term = factor *( ( "*" / "/" ) factor ) 948 factor = ftag / number / "(" expr ")" 949 number = 1*DIGIT [ "." 1*DIGIT ] 951 The form of an 'expr' is further constrained by the requirement 952 that it is linear function of a single feature tag value. 954 NOTE 956 The linearity constraint is imposed to allow an easy 957 algorithm for matching feature sets with simultaneous 958 constraints involving multiple feature tags. The single 959 variable constraint is to avoid the need to solve 960 simultaneous equations in more than two variables. The 961 allowable forms could be extended at some cost in 962 algorithmic complexity. At the time of writing, there 963 are no likely feature matching scenarios known to the 964 author that would require more complex forms. 966 An algebra for describing media feature sets 968 An "expr" appears only on the right hand side of a 969 filter. The left hand side is always a feature tag. The 970 main reason for this is to follow the general style of 971 the LDAP filter string upon which the predicate syntax is 972 based, but it also appears that it may simplify some 973 aspects of feature set matching. 975 6.3 Named and auxiliary predicates 977 Named and auxiliary predicates can serve two purposes: 979 (a) making complex predicates easier to write and understand, and 981 (b) providing a possible basis for naming and registering feature 982 sets. 984 6.3.1 Defining a named predicate 986 A named predicate definition has the following form: 988 named-pred = "(" fname *pname ")" ":-" filter 989 fname = 990 pname = 992 'fname' is the name of the predicate. 994 'pname' is the name of a formal parameter which may appear in the 995 predicate body, and which is replaced by some supplied value when 996 the predicate is invoked. 998 'filter' is the predicate body. It may contain references to the 999 formal parameters, and may also contain references to feature tags 1000 and other values defined in the environment in which the predicate 1001 is invoked. References to formal parameters may appear anywhere 1002 where a reference to a feature tag ('ftag') is permitted by the 1003 syntax for 'filter'. 1005 The only specific mechanism defined by this memo for introducing a 1006 named predicate into a feature set definition is the "auxiliary 1007 predicate" described later. Specific negotiating protocols or 1008 other memos may define other mechanisms. 1010 NOTE 1012 There has been some discussion of creating a registry for 1013 feature sets as well as individual feature values. Such 1014 a registry might be used to introduce named predicates 1015 corresponding to these feature sets into the environment 1016 of a capability assertion. Detailed discussion of this 1017 idea is beyond the scope of this memo. 1019 An algebra for describing media feature sets 1021 6.3.2 Invoking named predicates 1023 Assuming a named predicate has been introduced into the environment 1024 of some other predicate, it can be invoked by a filter "item" of 1025 the form: 1027 item =/ fname *param 1028 param = expr 1030 The number of parameters must match the definition of the named 1031 predicate that is invoked. 1033 6.3.3 Auxiliary predicates in a filter 1035 A auxiliary predicate is attached to a filter definition by the 1036 following extension to the "filter" syntax: 1038 filter =/ "(" filtercomp *( ";" parameter ) ")" 1039 "where" 1*( named-pred ) "end" 1041 The named predicates introduced by "named-pred" are visible from 1042 the body of the "filtercomp" of the filter to which they are 1043 attached, but are not visible from each other. They all have 1044 access to the same environment as "filter", plus their own formal 1045 parameters. (Normal scoping rules apply: a formal parameter with 1046 the same name as a value in the environment of "filter" effectively 1047 hides the environment value from the body of the predicate to which 1048 it applies.) 1050 NOTE 1052 Recursive predicates are not permitted. The scoping 1053 rules should ensure this. 1055 6.4 Feature set definition examples 1057 This section re-casts the Prolog example given in section 5.2 using 1058 the textual form syntax described in sections 6.1-6.3. 1060 6.4.1 Single predicate 1062 (| (& (Pix_x=1024) 1063 (Pix_y=768) 1064 (Res_x=[72..600]) 1065 (Res_y=[72..600]) 1066 (| (Res_x=Res_y) 1067 (Res_x=Res_y*2) 1068 (Res_y=Res_x*2) ) ) 1070 An algebra for describing media feature sets 1072 (& (Pix_x=800) 1073 (Pix_y=600) 1074 (Res_x=[72..600]) 1075 (Res_y=[72..600]) 1076 (| (Res_x=Res_y) 1077 (Res_x=Res_y*2) 1078 (Res_y=Res_x*2) ) );q=0.9 1079 (& (Pix_x=640) 1080 (Pix_y=480) 1081 (Res_x=[72..600]) 1082 (Res_y=[72..600]) 1083 (| (Res_x=Res_y) 1084 (Res_x=Res_y*2 1085 (Res_y=Res_x*2) ) );q=0.8 ) 1087 6.4.2 Predicate with auxiliary predicate 1089 (| (& (Pix_x=1024) (Pix_y=768) (Res Res_x Res_y) ) 1090 (& (Pix_x=800) (Pix_y=600) (Res Res_x Res_y) );q=0.9 1091 (& (Pix_x=640) (Pix_y=480) (Res Res_x Res_y) );q=0.8 ) 1092 where 1093 (Res Res_x Res_y) :- 1094 (& (Res_x=[72..600]) 1095 (Res_y=[72..600]) 1096 (| (Res_x=Res_y) 1097 (Res_x=Res_y*2) 1098 (Res_y=Res_x*2) ) ) 1099 end 1101 Note that the formal parameters of "Res", "Res_x" and "Res_y", 1102 prevent the body of the named predicate from referencing similarly- 1103 named feature values. 1105 6.5 ASN.1 representation 1107 Should it be required, the LDAP search filter model provides the 1108 basis for an ASN.1 representation of a feature predicate. 1110 The following ASN.1 is adapted from RFC 2251 "Lightweight Directory 1111 Access Protocol (v3)" [7] (also contained in RFC 2254 "The String 1112 Representation of LDAP Search Filters" [8]) to mirror the 1113 adaptation of the string representation presented above 1115 [[The following ASN.1 fragment does not include provision for 1116 quality value (and possibly other parameter values). Also, if 1117 using an ASN.1-derived representation it would seem appropriate to 1118 use an ISO object identifier for the feature tag, and an ASN.1 type 1119 for the feature value. Such changes would remove any semblance of 1120 compatibility with LDAP, but that may not matter.]] 1122 An algebra for describing media feature sets 1124 Filter ::= CHOICE { 1125 and [0] SET OF Filter, 1126 or [1] SET OF Filter, 1127 not [2] Filter, 1128 equalityMatch [3] AttributeValueAssertion, 1129 greaterOrEqual [5] AttributeValueAssertion, 1130 lessOrEqual [6] AttributeValueAssertion 1131 } 1133 AttributeValueAssertion ::= SEQUENCE { 1134 featureTag OCTET STRING, 1135 featureValue OCTET STRING 1136 } 1138 7. Content negotiation protocol processing 1140 This section addresses some issues that may arise when using 1141 feature set predicates as part of some content negotiation or file 1142 selection protocol. 1144 7.1 Matching feature sets 1146 Matching a feature set to some given feature collection is 1147 esentially very straightforward: the feature set predicate is 1148 simply evaluated for the given feature collection, and the result 1149 indicates whether the feature collection matches the capabilities, 1150 and the associated quality value can be used for selecting among 1151 alternative feature collections. 1153 Matching a feature set to some other feature set is less 1154 straightforward. Here, the problem is to determine whether or not 1155 there is at least one feature collection that matches both feature 1156 sets (e.g. is there an overlap between the feature capabilities of 1157 a given file format and the feature capabilities of a given 1158 recipient?) 1160 This feature set matching is accomplished by a combination of 1161 logical expression manipulation and partial evaluation of the 1162 predicate constraints. 1164 For this procedure to work reliably, the predicates must be reduced 1165 to a canonical form. One such form is "clausal form", and 1166 procedures for converting general expressions in predicate calculus 1167 are given in [5] (section 10.2), [11] (section 2.13), [13] (chapter 1168 4) and [14] (section 5.3.2). 1170 "Clausal form" for a predicate is similar to "conjunctive normal 1171 form" for a proposition, which consists of a conjunction (logical 1172 ANDs) of disjunctions (logical ORs). A related form that is better 1174 An algebra for describing media feature sets 1176 suited to feature set matching is "disjunctive normal form", which 1177 consists of a logical disjunction of conjunctions. In this form, 1178 it is sufficient to show that at least one of the disjunctions can 1179 be satisfied by some feature collection. 1181 A syntax for disjunctive normal form is: 1183 filter = orlist 1184 orlist = "(" "|" andlist ")" / term 1185 andlist = "(" "&" termlist ")" / term 1186 termlist = 1*term 1187 term = "(" "!" simple ")" / simple 1189 where "simple" is as described previously in section 6.1. Thus, 1190 the canonicalized form has at most three levels: an outermost 1191 "(|...)" disjunction of "(&...)" conjunctions of possibly negated 1192 feature value tests. 1194 NOTE (a theoretical diversion): 1196 Is this consideration of "clausal form" really required? 1197 After all, the feature predicates are just Boolean 1198 expressions, aren't they? 1200 Well, no. A feature predicate is a Boolean expression 1201 containing primitive feature value tests (comparisons), 1202 represented by 'item' in the feature predicate syntax. 1203 If these tests could all be assumed to be independently 1204 'true' or 'false', then each could be regarded as an 1205 atomic proposition, and the whole predicate could be 1206 dealt with according to the (relatively simple) rules of 1207 the Propositional Calculus. 1209 But, in general, the same feature tag may appear in more 1210 than one predicate 'item', so the tests cannot be 1211 regarded as independent. Indeed, interdependence is 1212 needed in any meaningful application of feature set 1213 matching, and it is important to capture these 1214 dependencies (e.g. does the set of resolutions that a 1215 sender can supply overlap the set of resolutions that a 1216 recipient can handle?). Thus, we have to deal with 1217 elements of the Predicate Calculus, with its additional 1218 rules for algebraic manipulation. 1220 This section aims to show that these additional rules are 1221 more unfamiliar than complicated. In practice, it seems 1222 that the way feature predicates are constructed and used 1223 actually avoids some of the complexity of dealing with 1224 fully-generalized Predicate Calculus. 1226 An algebra for describing media feature sets 1228 7.1.1 Feature set matching strategy 1230 The overall strategy for matching feature sets, expanded in the 1231 following sections, is: 1233 1. Formulate the hypothesis. 1235 2. Reduce the feature predicates to just <= and >=. 1237 3. Reduce the hypothesis to a canonical form (disjunctive normal 1238 form). 1240 4. For each of the disjunctions, attempt to show that it can be 1241 satisfied by some feature collection. Any that cannot be 1242 satisfied are discarded. 1244 4.1 Separate the feature value tests into the smallest possible 1245 independent groups, such that each group contains all tests 1246 involving one or more feature values. That is: no group 1247 contains a predicate involving any feature tag that also 1248 appears in a predicate in some other group. 1250 4.2 Within each group, process simultaneous equality 1251 constraints, to eliminate them from the overall set of 1252 constraints. 1254 The result of this step is that simultaneous inequality 1255 constraints are not dependent upon equality constraints. 1257 4.3 For each group, merge the various constraints involving just 1258 a single feature tag to a minimum form. 1260 4.4 For each group, ensure that all the constraints on the 1261 different feature values can be satisfied simultaneously. 1262 This involves enumerating and evaluating combinations of 1263 predicates within the group, hence the previous step to 1264 separate predicates into small groups. 1266 5. If the remaining disjunction is non-empty, then the constraints 1267 are shown to be satisfiable. Further, it can be used as a 1268 statement of the resulting feature set for possible further 1269 matching operations. 1271 An algebra for describing media feature sets 1273 7.1.2 Formulating the problem 1275 A formal statement of the problem we need to solve can be given as: 1276 given two feature set predicates, '(P x)' and '(Q x)', where 'x' is 1277 some feature collection, we wish to establish the truth or 1278 otherwise of the proposition: 1280 EXISTS(x) : (P x) AND (Q x) 1282 i.e. does there exist a feature collection that satisfies both 1283 predicates, 'P' and 'Q'? 1285 The predicates are derived from the predicate syntax described 1286 previously, and contain a number of primitive predicate functions 1287 such as '=', '<=', '>=' as well as logical connectives. The 1288 primitive predicate functions have a number of well known 1289 properties that we shall need to exploit in order reach a useful 1290 conclusion; e.g. 1292 (A = B) == (B = A) 1293 (A <= B) == (B >= A) 1294 (A = B) & (B = C) => (A = C) 1295 (A <= B) & (B <= C) => (A <= C) 1297 and so on (where '==' is used to mean "is equivalent to", and '=>' 1298 to mean "implies"). 1300 These rules form a core body of logic statements against which the 1301 goal predicate can be evaluated. The form in which these 1302 statements are expressed is important to realizing an effective 1303 predicate matching algorithm (i.e. one that doesn't loop or fail to 1304 find a valid result). The first step in forumulating these rules 1305 is to simplify the framework of primitive predicates. 1307 7.1.3 Simplifying primitive predicates 1309 The primitive predicates from which feature set definitions are 1310 constructed are '=', '<=' and '>='. Observe that, given any pair 1311 of feature values, the relationship between them must be exactly 1312 one of the following: 1314 (LT a b): 'a' is less than 'b'. 1315 (EQ a b): 'a' is equal to 'b'. 1316 (GT a b): 'a' is greater than 'b'. 1317 (NR a b): 'a' is not equal and not related to 'b'. 1319 (The final case arises when two values are compared for which no 1320 ordering relationship is defined, and the values are not equal; 1321 e.g. two unequal string values.) 1323 An algebra for describing media feature sets 1325 These four cases can be captured by a pair of primitive predicates: 1327 (LE a b): 'a' is less than or equal to 'b'. 1328 (GE a b): 'a' is greater than or equal to 'b'. 1330 The four cases described above are prepresented by the following 1331 combinations of primitive predicate values: 1333 (LE a b) (GE a b) | relationship 1334 ---------------------------------- 1335 TRUE FALSE | (LT a b) 1336 TRUE TRUE | (EQ a b) 1337 FALSE TRUE | (GT a b) 1338 FALSE FALSE | (NR a b) 1340 Thus, the original 3 imitive predicates can be translated to 1341 combinations of just LE and GE, reducing the number of additional 1342 relationships that must be subsequently captured: 1344 (<= a b) --> (LE a b) 1345 (>= a b) --> (GE a b) 1346 (= a b) --> (& (LE a b) (GE a b) ) 1348 7.1.3.1 Primitive predicate properties 1350 This section captures and codifies a set of rules that express the 1351 additional properties of the primitive predicates. The form of 1352 rules presented is intended to be used for performing feature set 1353 matching computations. 1355 Each rule is presented as: 1356 . one or two constraint predicates, 1357 . a single replacement constraint predicate or the value TRUE or 1358 FALSE, 1359 . optionally, a condition to be satisfied for the replacement to be 1360 valid. The relations '==' and '!=' are used here to denote 1361 equality and inequality in an unordered data type. 1362 A 'FALSE' or '(!TRUE)' result corresponds to failure (non- 1363 satisfiability) of any conjunction that contains it. A 'TRUE' or 1364 '(!FALSE)' result can be deleted from any conjunction that contains 1365 it. 1367 An algebra for describing media feature sets 1369 (<= f f) --> TRUE 1370 (<= f a) (<= f b) --> (<= f a), a<=b, a==b 1371 (<= f b), a>b 1372 FALSE, a!=b (*1) 1373 (<= f a) (>= f b) --> FALSE, a FALSE, a<=b, a==b (*3) 1375 (<= f a), a!=b 1376 (<= f a) (!(>= f b)) --> (<= f a), a= f b)), a>=b 1378 FALSE a==b 1380 (>= f f) --> TRUE 1381 (>= f a) (>= f b) --> (>= f a), a>=b, a==b 1382 (>= f b), a= f a) (!(>= f b)) --> FALSE, b<=a, a==b (*3) 1385 (>= f a), a != b 1386 (>= f a) (!(<= f b)) --> (>= f a), a>b, a!=b (*4) 1387 (!(<= f b)), a<=b, 1388 FALSE, a==b 1390 (!(<= f a)) (!(<= f b)) --> (! (<= f a) ), a>=b, a==b 1391 (! (>= f b) ), a= f b)) --> FALSE, a>=b, a==b 1394 (!(>= f a)) (!(>= f b)) --> (! (>= f a) ), a<=b, a==b 1395 (! (<= f b) ), a>b 1397 NOTES 1399 (*1) these cases correspond to there being no ordering 1400 relationship on the value of 'f', hence can only be 1401 satisfied if '(f=a) & (f=b) & (a<>b)', which is always 1402 FALSE. 1404 (*2) these cases correspond to inconsistent range 1405 constraints applied, with the lower bound greater than 1406 the upper bound. This can also correspond to 1407 inconsistent equality constraints (where equality is 1408 represented by a conjunction of '<=' and '>='). 1410 (*3) (!(<=...)) is equivalent to '>' or 'nr'. This is a 1411 variation of (*2) except that the interval is open at its 1412 lower bound. 1414 (*4) these cases include there being no ordering 1415 relationship on the value of 'f', hence can only be 1416 satisfied if '(f=a) & (f<>b)'. The latter term is always 1417 FALSE when 'a<>b', so the it reduces to just '(f=a)'. 1419 An algebra for describing media feature sets 1421 Open boundaries ('<' and '>') are represented by a 1422 negation of '>=' and '<=' respectively. The rules here 1423 assume conjunction, so these are treated separately. 1425 [[[TODO: revise the above table to present rules for ordered and 1426 unordered features separately. Also, use '<', '>' instead of 1427 logical negations. This will make it much easier to very 1428 correctness by inspection.]]] 1430 [[[TODO: Work through this whole chapter to use consistent 1431 notation for describing the predicates being transformed.]]] 1433 [[[TODO: model the above system to confirm that it is complete and 1434 does indeed work properly in all cases.]]] 1436 7.1.4 Conversion to canonical form 1438 The steps below (except step 0) are adapted from standard textbooks 1439 on logic and logic programing [5,11]. All steps mentioned for a 1440 textbook conversion to clausal form are indicated here for 1441 completeness, but some --indicated in parentheses-- are not 1442 applicable in this situation. Step 0 is not a textbook step, but 1443 is applied to get the predicate into a standard Boolean expression 1444 form. 1446 0. Replace all "set" instances with "simple" forms: 1447 T = [ E1, E2, ... En ] => (| (T=[E1]) (T=[E2]) ... (T=[En]) ) 1448 (T=[R1..R2]) => (& (T>=R1) (T<=R2) ) 1449 (T=[E]) => (T=E) 1451 1. (Remove implications and equivalences. Our predicate form is 1452 constructed without these, so there is nothing to do here.) 1454 2. Move negation inwards, by application of De Morgan's Rule: 1455 (! (& A1 A2 ... An ) ) => (| (! A1 ) (! A2 ) ... (! An ) ) 1456 (! (| A1 A2 ... An ) ) => (& (! A1 ) (! A2 ) ... (! An ) ) 1457 (! (! A ) ) => A 1458 Repeat application of this to the inner expressions A1,A2,...An 1459 until all negations apply directly to "simple" forms. 1461 3. (Remove existential quantifiers. This involves replacing 1462 existentially qualified variables with "Skolem constants" and/or 1463 "Skolem functions" in a procedure called "Skolemizing". Feature 1464 predicates do not use these so there is nothing to do here.) 1466 An algebra for describing media feature sets 1468 NOTE 1470 Recall that the original goal was formulated using an 1471 existential quantifier: 1473 EXISTS(x) : (P x) AND (Q x) 1475 Applying Skolemization here means that every ocurrence of 1476 the variable 'x' is replaced by some unknown "Skolem 1477 constant", which is distinct from all other variables and 1478 constants in the predicate. 1480 In this case, 'x' represents some (unknown) feature 1481 collection, which in turn is a set of feature tag and 1482 feature value associations. The feature predicate syntax 1483 and examples have feature values referenced by their 1484 feature tags; each feature tag can be regarded as 1485 representing a component value of a feature collection. 1486 If we treat every feature tag reference as being 1487 implicitly qualified by the feature collection to which 1488 the predicate is applied, the predicate as presented is 1489 already Skolemized (noting that, by construction, feature 1490 tags satisfy the uniqueness requirements for Skolem 1491 constants; and, in the absence of universal 1492 quantification, Skolem functions are not required). 1494 4. (Pull out universal quantifiers. Again, feature predicates do 1495 not use these so there is nothing to do here.) 1497 5. Expand bracketed disjunctions, and flatten bracketed conjunctions 1498 and disjunctions: 1499 (& (| A1 A2 ... Am ) B1 B2 ... Bn ) 1500 => (| (& A1 B1 B2 ... Bn ) 1501 (& A2 B1 B2 ... Bn ) 1502 : 1503 (& Am B1 B2 ... Bn ) ) 1504 (& (& A1 A2 ... Am ) B1 B2 ... Bn ) 1505 => (& A1 A2 ... Am B1 B2 ... Bn ) 1506 (| (| A1 A2 ... Am ) B1 B2 ... Bn ) 1507 => (| A1 A2 ... Am B1 B2 ... Bn ) 1509 The result is a "disjunctive normal form", a disjunction of 1510 conjunctions: 1512 (| (& S11 S12 ... ) 1513 (& S21 S22 ... ) 1514 : 1515 (& Sm1 Sm2 ... Smn ) ) 1517 An algebra for describing media feature sets 1519 where the "Sij" elements are either "simple" forms, or negations of 1520 "simple" forms. Each term within the top-level "(&...)" construct 1521 represents a single possible feature set that satisfies the goal. 1522 Note that the order of entries within the top-level '(|...)', and 1523 within each '(&...)', is immaterial. 1525 From here on, each conjunction '(&...)' is processed separately. 1526 Only one of these needs to be satisfiable for the original goal to 1527 be satisfiable. 1529 (A textbook conversion to clausal form uses slightly different 1530 rules to yield a "conjunctive normal form".) 1532 7.1.5 Grouping of feature predicates 1534 NOTE: remember that from here on, each disjunction is 1535 treated separately. 1537 Each simple feature predicate contains a "left-hand" feature tag 1538 and may also contain another feature tag on the "right-hand" side. 1539 Thus, each simple predicate reduces to one of the forms: 1541 (<= f a) 1542 (<= f a+b*f1) 1543 (>= f a) 1544 (>= f a+b*f1) 1546 where "f" and "f1" are feature tags, and "a" and "b" are literal 1547 (i.e. known) constant values. 1549 To arrange these into independent groups: 1551 1. Group all simple predicates according to their left hand feature 1552 tag ('f'). 1554 2. Locate all predicates with feature tags ('f1') on their "right- 1555 hand" side, and combine the feature tag group in which they 1556 appear with the group that has that value as a "left-hand" tag. 1558 (e.g. given a predicate of the form '(<= pix_x 2*pix_y)', combine 1559 the groups containing predicates of the form '(?= pix_x ...)' and 1560 '(?= pix_y ...)', noting that they may already be combined.) 1562 One pass through all of the predicates should ensure that any 1563 interdependent predicates have been grouped together. (The act of 1564 joining predicate groups can never separate any feature tags, and 1565 at the end of one pass, every feature tag occurrence has been 1566 joined in a group with any other tags that appear in the same 1567 predicate.) 1569 An algebra for describing media feature sets 1571 7.1.6 Remove simultaneous equality constraints 1573 The purpose of this step is to remove all dependence of 1574 simultaneous inequality constraints on any equality constraint. 1575 This means that the only simultaneous constraints remaining are 1576 inequality constrains (i.e. '<=' or '>='). 1578 An equality constraint occurs when '(<= f e)' and '(>= f e)' are 1579 asserted in the same conjunction with the same values for 'f' and 1580 'e', where 'e' may be any value or expression in the limited linear 1581 form allowed (i.e. 'a+b*f1'). 1583 In the remainder of this section, the expression '(= x y)' is used 1584 as a shorthand for both '(<= x y)' and '(>= x y)' appearing in the 1585 group with the same values for 'x' and 'y' and with neither being 1586 logically negated. 1588 For each equality constraint in the group ('(= f1 e)', consisting 1589 of '(<= f1 e)' and '(>= f1 e)' as noted above), scan all other 1590 constraints in the same group and apply the following rules: 1592 [A] (= f a ), 'a' is a literal constant, 1593 --> replace all right-hand occurrences of 'f' in the group with 1594 'a'. 1596 [B] (= f1 a1+b1*f2), (= f1 a2+b2*f2) 1597 --> solve for 'f1', 'f2' using the formulae: 1598 f1 = (a1 b2 - a2 b1)/(b2 - b1) 1599 f2 = (a1 - a2)/(b2 - b1) 1600 replace the predicates with equivalents that represent the 1601 solutions, and replace all right-hand occurrences of 'f1', 1602 'f2' in the group with these solutions. 1603 If the solution is degenerate (i.e. 'b2=b1') then: 1604 (a) if 'a1=a2', discard one of the constraints and continue 1605 processing with the other. 1606 (b) if 'a1<>a2', fail the current conjunction as there are 1607 no values of 'f1' and 'f2' that can satisfy both of 1608 these predicates. 1610 An algebra for describing media feature sets 1612 [C] (= f1 a1+b1*f2), (= f2 a2+b2*f1) 1613 --> solve for 'f1', 'f2' using the formulae: 1614 f1 = (a1 + a2 b1)/(1 - b1 b2) 1615 f2 = (a2 + a1 b2)/(1 - b1 b2) 1616 replace the predicates with equivalents that represent the 1617 solutions, and replace all right-hand occurrences of 'f1', 1618 'f2' in the group with these solutions. 1619 If the solution is degenerate (i.e. 'b1 b2=1') then: 1620 (a) if 'a1+a2 b1=0' (or 'a2+a1 b2=0'), discard one of the 1621 constraints and continue processing with the other. 1622 (b) if 'a1+a2 b1<>0', fail the current conjunction as there 1623 are no values of 'f1' and 'f2' that can satisfy both of 1624 these predicates. 1626 [D] (= f1 a1+b1*f2), (<= f1 a2+b2*f2) 1627 --> substitute for 'f1' in the second predicate, and reorganize 1628 to get the result into the required form: 1629 a1 + b1 f2 <= a2 + b2 f2 1630 hence 1631 (b1 - b2) f2 <= a2 - a1 1632 Now we need to consider 4 cases: 1633 (1) b1>b2, use: (<= f2 (a2-a1)/(b1-b2)) 1634 (2) b1= f2 (a2-a1)/(b1-b2)) 1635 (3) b1=b2, a2>=a1, use: TRUE 1636 (4) b1=b2, a2 substitute for 'f1' in the second predicate, and reorganize 1640 to get the result into the required form: 1641 f2 <= a2 + b2 (a1 + b1 f2) 1642 hence 1643 f2 <= a2 + b2 a1 + b2 b1 f2 1644 (1 - b1 b2) f2 <= a2 + a1 b2 1645 Now we need to consider 4 cases: 1646 (1) b1 b2 < 1, use: (<= f2 (a2 - a1*b2)/(1 - b1*b2) ) 1647 (2) b1 b2 > 1, use: (>= f2 (a2 - a1*b2)/(1 - b1*b2) ) 1648 (3) b1 b2 = 1, (a2 + a1 b2) >= 0, use: TRUE 1649 (4) b1 b2 = 1, (a2 + a1 b2) < 0, use: FALSE 1651 [F] (= f1 a1+b1*f2), (>= f1 a2+b2*f2) 1652 --> is the same as rule [D] (above) except that '<=' and '>=' 1653 predicates are exchanged. 1655 [G] (= f1 a1+b1*f2), (>= f2 a2+b2*f1) 1656 --> is the same as rule [E] (above) except that '<=' and '>=' 1657 predicates are exchanged. 1659 When processing of an equality predicate is complete, remove it 1660 from active consideration in the group (but keep it as part of 1661 the final solution). 1663 An algebra for describing media feature sets 1665 On completion of this stage, all simultaneous equality predicates 1666 have been replaced by single feature value predicates, or by 1667 equality with an expression containing a feature whose value range 1668 is determined by one or more inequality predicates. 1670 [[[TODO: discussion of near-degenerate cases. Numerical stability 1671 issues, etc. How to handle?]]] 1673 [[[TODO: if the theory is correct, this stage should be unecessary, 1674 though it may yield performance gains if there is a large number of 1675 interdependent features (unlikely). Model the algorithm without 1676 this step to increase confidence that it works OK.]]] 1678 7.1.7 Merge single-feature constraints 1680 Within each group, apply the predicate simplification rules from 1681 section 7.1.3 to eliminate redundant single-feature constraints. 1682 All single-feature predicates are reduced to an equality, 1683 inequality or range constraint on that feature. 1685 If the constraints on any feature are found to be contradictory, 1686 the current disjunction is removed from the feature set 1687 description. 1689 The resulting description is a minimal form of the particular 1690 disjunction of the feature set definition. 1692 [[[TODO: move rule descriptions to here when they are revised.]]] 1694 7.1.8 Test simultaneous feature constraints 1696 The final stage is to examine any simultaneous inequality 1697 constrains on the feature values to determine whether or not they 1698 can be satisfied. 1700 During this stage, the feature set description predicates are not 1701 further modified. Previous processing has been directed toward 1702 reducing the feature set descriptions to some minimal format; the 1703 final stage is to examine the reduced rules to determine whether or 1704 not they can be satisfied. 1706 7.1.8.1 Convex sets 1708 The algorithm for testing satisfiability of the simultaneous 1709 inequalities is based on the theory of conves sets. These are 1710 described in [16,17], or other good reference works on Linear 1711 Algebra and/or Linear Programming. 1713 An algebra for describing media feature sets 1715 The idea is very simple: a convex set is a set where any linear 1716 combination of any two members with coefficients that sum to 1 is 1717 also a member of the set. A simple example is a line between two 1718 points: if P1 and P2 are points on that line, then (using normal 1719 vector addition and multiplication by a scalar) '(a1 P1 + a2 P2)' 1720 is also a point on that line, where 'a1+a2=1'. This idea 1721 generalizes easily to higher dimensions. 1723 CS1: A "convex set" is a set of vectors 'S' if 't V + (1-t) U' 1724 belongs to S whenever U and V belong to S and 0 <= t <= 1. 1726 CS2: The solution of any set of linear inequalities is a convex 1727 set. [16, chapter 7] 1729 Other definitions and properties of convex sets are: 1731 CS3: A "convex combination" of points 'V1,V2,...,Vn' is the point 1732 'V = SUM(i=1,n; ti Vi)', where 'SUM(i=1,n; ti) = 1'. 1734 CS4: A point 'U' in a convex set 'C' is called an "extreme point" 1735 or "vertex" if it cannot be expressed as a convex 1736 combination of two other distinct points in 'C'. 1738 CS5: The "convex hull" 'C(S)' of a set of points 'S' is the set 1739 of all convex combinations of points from 'S'. The set 'S' 1740 is said to "span" 'C(S)'. 1742 CS6: A "convex polygonal region" or "convex polyhedron" is a 1743 convex hull spanned by a finite number of points 1744 'V1,V2,...,Vn' is the set of all convex combinations of 1745 'V1,...,Vn'. 1747 CS7: A bounded solution to a set of linear inequalities is a 1748 convex polyhedron. [16, chapter 7] 1750 CS8: A "simplex" is an n-dimensional convex polyhedron with 1751 exactly n+1 vertices. The boundary of a simplex contains 1752 simplices of lower dimension, which are called "simplicial 1753 faces". 1754 [17, ch 2, sect 3] 1756 [[[TODO: above are textbook definitions. Below are a number of 1757 definitions and hypotheses concerning convex sets that seem fairly 1758 obvious to me, but for which I don't have proofs or citations. 1759 These are currently tagged [GK]. Proofs or citations are 1760 needed.]]] 1762 CS9: A convex set is spanned by its vertices. [GK] 1764 An algebra for describing media feature sets 1766 CS10: The vertices of the complex polyhedron that is the solution 1767 of a set of linear ineqalities are a subset of the solutions 1768 of the inequalities treated as equations. Specifically the 1769 linear equation solutions that lie within the solution 1770 convex set are its vertices. [GK] 1772 [[[cf Simplex method slack variables]]] 1774 [[[Unbounded solution sets]]] 1776 [[[Vertices for unbounded sets]]] 1778 [[[Develop open/closed boundaries]]] 1780 [[[Boundary points -- adjoining points]]] 1782 [[[Open and closed boundaries]]] 1784 [[[Open and closed vertices]]] 1786 [[[Relating open/closed vertices to inequalities]]] 1788 7.1.8.2 Testing for satisfiability 1790 Assume that our dependency group contains N features. Then the 1791 convex set that comprises the solution space contains N-vectors. 1792 The vertices of this convex set will be obtained each as the 1793 solution of N simultaneous linear equations. As the original 1794 problem was constrained to allow a maximum of two features in any 1795 single primitive feature predicate, it will be possible to solve 1796 the simultaneous equations by direct substitution. 1798 To test a set of inequalities for satisfiability: 1800 1. From the inequalities in the dependency group, select each 1801 combination that references all N interdependent features. (It 1802 is assumed that the total number of inequalities in a group will 1803 be quite small, so the total number of combinations should not 1804 get out of hand.) 1806 2. For each selected combination, treat the inequalities as 1807 equations and solve for the feature values. If the solution is 1808 degenerate, discard that combination. 1810 An algebra for describing media feature sets 1812 3. For each solution generated at step 2, test it against all of the 1813 constraints in the set. If it satisfies or adjoins each 1814 constraint, add that solution to the set of vertices. If the 1815 solution fully satisfies every constraint, note that it is a 1816 'closed' vertex. Otherwise, if it only adjoins (rather than 1817 fully satisfies) at least one of the constraints, note that it is 1818 an 'open' vertex. Discovery of any closed vertex indicates at 1819 least one solution that satisfies the current dependency group. 1821 4. If all the vertices discovered are 'open' vertices, then 1822 construct a new point that is a convex combination of the 1823 vertices discovered, with all coefficients in the range 0= 100' and another 1853 feature set specifies 'Res_x_dpi <= 100'. A simple conjunction of 1854 these yields the theorem: 1856 (& ( Res_x_dpcm >= 100 ) 1857 ( Res_x_dpi <= 100 ) ) 1859 which appears to be quite satisfiable, despite what we know about 1860 the relationship between them. 1862 But we can add an extra clause that captures our knowledge of this 1863 relationship: 1865 (& ( Res_x_dpcm >= 100 ) 1866 ( Res_x_dpi <= 100 ) 1867 ( Res_x_dpi = Res_x_dpcm*2.54 ) ) 1869 The procedures described above for handling simultaneous feature 1870 constraints would cause this predicate to fail because there are no 1871 values for 'Res_x_dpcm' and 'Res_x_dpi' that simultaneously satisfy 1872 all the constraints. 1874 7.4 Unknown feature value data types 1876 [[Discuss issues of specific features which may have feature- 1877 specific comparison rules, as opposed to generic Booleans, 1878 enumerations, strings and numbers which use comparison rules 1879 independent of the feature concerned.]] 1881 [[[TODO]]] 1883 7.5 Worked example 1885 [[[TODO]]] 1887 7.6 Algorithm source code 1889 [[[TODO]]] 1891 An algebra for describing media feature sets 1893 8. Security considerations 1895 Some security considerations for content negotiation are raised in 1896 [1,2,3]. 1898 The following are primary security concerns for capability 1899 identification mechanisms: 1901 . Unintentional disclosure of private information through the 1902 announcement of capabilities or user preferences. 1904 . Disruption to system operation caused by accidental or malicious 1905 provision of incorrect capability information. 1907 . Use of a capability identification mechanism might be used to 1908 probe a network (e.g. by identifying specific hosts used, and 1909 exploiting their known weaknesses). 1911 The most contentious security concerns are raised by mechanisms 1912 which automatically send capability identification data in response 1913 to a query from some unknown system. Use of directory services 1914 (based on LDAP [7], etc.) seem to be less problematic because 1915 proper authentication mechanisms are available. 1917 Mechanisms which provide capability information when sending a 1918 message are less contentious, presumably because some intention can 1919 be inferred that person whose details are disclosed wishes to 1920 communicate with the recipient of those details. This does not, 1921 however, solve problems of spoofed supply of incorrect capability 1922 information. 1924 The use of format converting gateways may prove problematic because 1925 such systems would tend to defeat any message integrity and 1926 authenticity checking mechanisms that are employed. 1928 An algebra for describing media feature sets 1930 9. Copyright 1932 Copyright (C) The Internet Society 1998. All Rights Reserved. 1934 This document and translations of it may be copied and furnished to 1935 others, and derivative works that comment on or otherwise explain 1936 it or assist in its implementation may be prepared, copied, 1937 published and distributed, in whole or in part, without restriction 1938 of any kind, provided that the above copyright notice and this 1939 paragraph are included on all such copies and derivative works. 1940 However, this document itself may not be modified in any way, such 1941 as by removing the copyright notice or references to the Internet 1942 Society or other Internet organizations, except as needed for the 1943 purpose of developing Internet standards in which case the 1944 procedures for copyrights defined in the Internet Standards process 1945 must be followed, or as required to translate it into languages 1946 other than English. 1948 The limited permissions granted above are perpetual and will not be 1949 revoked by the Internet Society or its successors or assigns. 1951 This document and the information contained herein is provided on 1952 an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET 1953 ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR 1954 IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 1955 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1956 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1958 10. Acknowledgements 1960 My thanks to Larry Masinter for demonstrating to me the breadth of 1961 the media feature issue, and encouraging me to air my early ideas. 1963 Early discussions of ideas on the IETF-HTTP and IETF-FAX discussion 1964 lists led to useful inputs also from Koen Holtman, Ted Hardie and 1965 Dan Wing. 1967 The debate later moved to the IETF conneg WG mailing list, where Al 1968 Gilman was particularly helpful in helping me to refine the feature 1969 set algebra. Several ideas for dealing with preferences were 1970 suggested by Larry Masinter. 1972 I would also like to thank Content Technologies Ltd and 5th 1973 Generation Messaging Ltd for supporting this work. 1975 An algebra for describing media feature sets 1977 11. References 1979 [1] "Scenarios for the Delivery of Negotiated Content" 1980 T. Hardie, NASA Network Information Center 1981 Internet draft: 1982 Work in progress, November 1997. 1984 [2] "Requirements for protocol-independent content negotiation" 1985 G. Klyne, Integralis Ltd. 1986 Internet draft: 1987 Work in progress, March 1998. 1989 [3] "Content feature tag registration procedures" 1990 Koen Holtman, TUE 1991 Andrew Mutz, Hewlett-Packard 1992 Ted Hardie, NASA 1993 Internet draft: 1994 Work in progress, November 1997. 1996 [4] "Notes on data structuring" 1997 C. A. R. Hoare, 1998 in "Structured Programming" 1999 Academic Press, APIC Studies in Data Processing No. 8 2000 ISBN 0-12-200550-3 / 0-12-200556-2 2001 1972. 2003 [5] "Programming in Prolog" (2nd edition) 2004 W. F. Clocksin and C. S. Mellish, 2005 Springer Verlag 2006 ISBN 3-540-15011-0 / 0-387-15011-0 2007 1984. 2009 [6] "Media Features for Display, Print, and Fax" 2010 Larry Masinter, Xerox PARC 2011 Koen Holtman, TUE 2012 Andrew Mutz, Hewlett-Packard 2013 Dan Wing, Cisco Systems 2014 Internet draft: 2015 Work in progress, January 1998. 2017 [7] RFC 2251, "Lightweight Directory Access Protocol (v3)" 2018 M. Wahl, Critical Angle Inc. 2019 T. Howes, Netscape Communications Corp. 2020 S. Kille, Isode Limited 2021 December 1997. 2023 [8] RFC 2254, "The String Representation of LDAP Search Filters" 2024 T. Howes, Netscape Communications Corp. 2025 December 1997. 2027 An algebra for describing media feature sets 2029 [9] RFC 2068, "Hyptertext Transfer Protocol -- HTTP/1.1" 2030 R. Fielding, UC Irvine 2031 J. Gettys, 2032 J. Mogul, DEC 2033 H. Frytyk, 2034 T. Berners-Lee, MIT/LCS 2035 January 1997. 2037 [10] RFC 2234, "Augmented BNF for Syntax Specifications: ABNF" 2038 D. Crocker (editor), Internet Mail Consortium 2039 P. Overell, Demon Internet Ltd. 2040 November 1997. 2042 [11] "Logic, Algebra and Databases" 2043 Peter Gray 2044 Ellis Horwood Series: Computers and their Applications 2045 ISBN 0-85312-709-3/0-85312-803-3 (Ellis Horwood Ltd) 2046 ISBN 0-470-20103-7/0-470-20259-9 (Halstead Press) 2047 1984. 2049 [12] "Introduction to Expert Systems" 2050 Peter Jackson 2051 Addison Wesley, International computer science series 2052 ISBN 0-201-14223-6 2053 1986. 2055 [13] "Elementary Logics: A procedural Perspective 2056 Dov Gabbay 2057 Prentice Hall, Series in computer science 2058 ISBN 0-13-726365-1 2059 1998. 2061 [14] "Logic and its Applications" 2062 Edmund Burk and Eric Foxley 2063 Prentice Hall, Series in computer science 2064 ISBN 0-13-030263-5 2065 1996. 2067 [15] "Metalogic: 2068 An Introduction to the Metatheory of Standard First Order Logic" 2069 Geoffrey Hunter 2070 University of California Press 2071 ISBN 0-520-02356-0 2072 1971. 2074 [16] "Elementary Linear Algebra" 2075 Paul C Shields 2076 Worth Publishers Inc. 2077 ISBN 0-87901-121-1 2078 1968, 1973, 1980. 2080 An algebra for describing media feature sets 2082 [17] "Linear Programming" 2083 Saul I Gass, 2084 McGraw-Hill Inc. 2085 Library of Congress Catalog Card no 68-55267 (no ISBN) 2086 1958, 1964, 1969. 2088 12. Author's address 2090 Graham Klyne 2091 Content Technologies Ltd. 5th Generation Messaging Ltd. 2092 Forum 1 5 Watlington Street 2093 Station Road Nettlebed 2094 Theale Henley-on-Thames 2095 Reading, RG7 4RA RG9 5AB 2096 United Kingdom United Kingdom. 2098 Telephone: +44 118 930 1300 +44 1491 641 641 2100 Facsimile: +44 118 930 1301 +44 1491 641 611 2102 E-mail: GK@ACM.ORG