IETF media feature registration WG Graham Klyne Internet draft Content Technologies 6 April 2000 Expires: October 2000 A revised media feature set matching algorithm Status of this memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC 2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress". To view the entire list of current Internet-Drafts, please check the "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). Copyright Notice Copyright (C) The Internet Society 1999. All Rights Reserved. Abstract RFC 2533, "A syntax for describing media feature sets", defines a format to express media feature sets that represent media handling capabilities. It also describes an algorithm for matching these feature sets, which may be used, for example, to determine whether the capabilities of a sender and receiver are compatible. This memo describes a revised form of the feature set matching algorithm, which incorporates lessons learned while implementing the original algorthm. It is anticipated that this revised algorithm description will be included in a future revision of RFC 2533. This memo does not affect any of the normative content of RFC 2533. Klyne Internet draft [Page 1] A revised media feature set matching algorithm 6 April 2000 Table of contents 1. Introduction.............................................2 1.1 Structure of this document ...........................3 1.2 Document terminology and conventions .................3 1.3 Discussion of this document ..........................4 2. Matching feature sets....................................4 2.1 Feature set matching strategy ........................6 2.2 Formulating the goal predicate .......................7 2.3 Replace set expressions ..............................8 2.4 Move logical negations inwards .......................8 2.5 Replace comparisons and logical negations ............8 2.6 Conversion to canonical form .........................9 2.7 Grouping of feature predicates .......................10 2.8 Merge single-feature constraints .....................10 2.9 Presentation of feature comparisons ..................11 3 Worked example............................................11 4. Security considerations..................................16 5. Acknowledgements.........................................16 6. References...............................................17 7. Author's address.........................................18 Appendix A: Amendment history...............................18 Full copyright statement....................................18 1. Introduction RFC 2533, "A syntax for describing media feature sets" [1], defines a format to express media feature sets that represent media handling capabilities. It also describes an algorithm for matching these feature sets, which may be used, for example, to determine whether the capabilities of a sender and receiver are compatible. This memo describes a revised form of the feature set matching algorithm, which incorporates lessons learned while implementing the original algorthm. It is anticipated that this revised algorithm description will be included in a future revision of RFC 2533. The feature set matching algorithm description in RFC 2533 is not normative: the logical properties of feature set expressions are defined independently of any specific algorithm that may be used to process them. This memo does not affect any of the normative content of RFC 2533. Klyne Internet draft [Page 2] A revised media feature set matching algorithm 6 April 2000 Differences between the algorithm described in RFC 2533 and the one in this memo are: o a different set of primitive feature comparison functions are used (LE, GE, EQ, NE used here, LE, GE, NL, NG used in RFC 2533). These yield final results that are more clearly related to the original feature set expressions. o the description of how to transform feature comparison syntax to the four primitive comparison functions is more direct, simpler and should be easier to understand. o the separate feature comparison reduction rules for ordered and unordered value cases are replaced by a single, more obvious, set of rules applicable to all cases. o transformation rules are given for presenting the final result for feature set matching using the feature expression syntax of RFC 2533. An implementation in Java of this feature set matching algorithm has been prepared, and is available for public study and use [15]. 1.1 Structure of this document The main part of this memo addresses the following main areas: Section 2 describes a the revised feature set matching algorithm. Section 3 contains a worked example of feature set matching. 1.2 Document terminology and conventions The following terms are defined in RFC 2533, but are repeated here because they are crucial to parts of the description that follows. Feature Collection is a collection of different media features and associated values. This might be viewed as describing a specific rendering of a specific instance of a document or resource by a specific recipient. Feature Set is a set of zero, one or more feature collections. Klyne Internet draft [Page 3] A revised media feature set matching algorithm 6 April 2000 Feature set predicate A function of an arbitrary feature collection value which returns a Boolean result. A TRUE result is taken to mean that the corresponding feature collection belongs to some set of media feature handling capabilities defined by this predicate. NOTE: Comments like this provide additional nonessential information about the rationale behind this document. Such information is not needed for building a conformant implementation, but may help those who wish to understand the design in greater depth. 1.3 Discussion of this document Discussion of this document should take place on the content negotiation and media feature registration mailing list hosted by the Internet Mail Consortium (IMC): Please send comments regarding this document to: ietf-medfree@imc.org To subscribe to this list, send a message with the body 'subscribe' to "ietf-medfree-request@imc.org". To see what has gone on before you subscribed, please see the mailing list archive at: http://www.imc.org/ietf-medfree/ 2. Matching feature sets This section presents a procedure for combining feature sets to determine the common feature collections to which they refer, if there are any. Making a selection from the possible feature collections (based on q-values or otherwise) is not covered here. Matching a feature set to some given feature collection is esentially very straightforward: the feature set predicate is simply evaluated for the given feature collection, and the result (TRUE or FALSE) indicates whether the feature collection matches the capabilities, and the associated quality value can be used for selecting among alternative feature collections. Klyne Internet draft [Page 4] A revised media feature set matching algorithm 6 April 2000 Matching a feature set to some other feature set is less straightforward. Here, the problem is to determine whether or not there is at least one feature collection that matches both feature sets (e.g. is there an overlap between the feature capabilities of a given file format and the feature capabilities of a given recipient?) This feature set matching is accomplished by logical manipulation of the predicate expressions as described in the following sub- sections. This procedure requires that the predicates be reduced to a canonical form. The canonical form used is "disjunctive normal form". An ABNF [10] syntax for this disjunctive normal form is: filter = orlist orlist = "(" "|" andlist ")" / term andlist = "(" "&" termlist ")" / term termlist = 1*term term = "(" "!" simple ")" / simple where "simple" is defined in RFC 2533, section 4.1 [1]. Thus, the canonicalized form has at most three levels: an outermost "(|...)" disjunction of "(&...)" conjunctions of possibly negated feature value comparisons. NOTE The usual canonical form for predicate expressions is "clausal form". Procedures for converting general predicate expressions are given in [5] (section 10.2), [11] (section 2.13) and [12] (section 5.3.2). "Clausal form" for a predicate is similar to "conjunctive normal form" for a proposition, being a conjunction (logical AND) of disjunctions (logical ORs). The related form used here, better suited to feature set matching, is "disjunctive normal form", which is a logical disjunction (OR) of conjunctions (ANDs). In this form, the aim of feature set matching is to show that at least one of the disjunctions can be satisfied by some feature collection. Is this consideration of canonical forms really required? After all, the feature predicates are just Boolean expressions, aren't they? Well, no: a feature predicate is a Boolean expression containing primitive feature value tests (comparisons), represented by 'item' in the feature predicate syntax. If these tests could all be assumed to be independently TRUE or FALSE, then each could be regarded as an atomic proposition, and the whole Klyne Internet draft [Page 5] A revised media feature set matching algorithm 6 April 2000 predicate could be dealt with according to the (relatively simple) rules of Propositional Calculus. But, in general, the same feature tag may appear in more than one predicate 'item', so the tests cannot be regarded as independent. Indeed, interdependence is needed in any meaningful application of feature set matching, and it is important to capture these dependencies (e.g. does the set of resolutions that a sender can supply overlap the set of resolutions that a recipient can handle?). Thus, we have to deal with elements of the Predicate Calculus, with some additional rules for algebraic manipulation. A description of both the Propositional and Predicate calculi can be found in [12]. We aim to show that these additional rules are more unfamiliar than complicated. The construction and use of feature predicates avoids some of the complexity of dealing with fully-generalized Predicate Calculus. 2.1 Feature set matching strategy The overall strategy for matching feature sets, expanded below, is: 1. Formulate the feature set matching hypothesis. 2. Replace "set" expressions with equivalent comparisons. 3. Move logical negations "inwards", so that they are all applied directly to feature comparisons. 4. Eliminate logical negations, and express all feature comparisons in terms of just four comparison functions. 5. Reduce the hypothesis to a canonical disjunctive normal form (a disjunction of conjunctions). 6. For each of the conjunctions, attempt to show that it can be satisfied by some feature collection. 6.1 Partition the feature value tests into independent feature groups, such that each group contains tests involving just one feature tag. Thus, no predicate in a feature group contains a feature tag that also appears in some other group. Klyne Internet draft [Page 6] A revised media feature set matching algorithm 6 April 2000 6.2 For each feature group, merge the various constraints to a minimum form. This process either yields a reduced expression for the allowable range of feature values, or an expression containing the value FALSE, which is an indication that no combination of feature values can satisfy the constraints (in which case the corresponding conjunction can never be satisfied). 7. If the remaining disjunction contains at least one satisfiable conjunction, then the constraints are shown to be satisfiable and therefore the original two feature sets can be matched together. The final expression obtained by this procedure, if it is non- empty, can be used as a statement of the resulting feature set for possible further matching operations. That is, it can be used as a starting point for combining with additional feature set constraint predicate to determine a feature set that is constrained by the capabilities of several entities in a message transfer path. NOTE: as presented, the feature matching process evaluates (and stores) all conjunctions of the disjunctive normal form before combining feature tag comparisons and eliminating unsatisfiable conjunctions. For low-memory systems an alternative approach is possible, in which each normal form conjunction is enumerated and evaluated in turn, with only those that are satisfiable being retained for further use. 2.2 Formulating the goal predicate A formal statement of the problem we need to solve can be given as: given two feature set predicates, '(P x)' and '(Q x)', where 'x' is some feature collection, we wish to establish the truth or otherwise of the proposition: EXISTS(x) : (P x) AND (Q x) i.e. does there exist a feature collection 'x' that satisfies both predicates, 'P' and 'Q'? Then, if feature sets to be matched are described by predicates 'P' and 'Q', the problem is to determine if there is any feature set satisfying the goal predicate: (& P Q) i.e. to determine whether the set thus described is non-empty. Klyne Internet draft [Page 7] A revised media feature set matching algorithm 6 April 2000 2.3 Replace set expressions Replace all "set" instances in the goal predicate with equivalent "simple" forms: T = [ E1, E2, ... En ] --> (| (T=[E1]) (T=[E2]) ... (T=[En]) ) (T=[R1..R2]) --> (& (T>=R1) (T<=R2) ) (T=[E]) --> (T=E) 2.4 Move logical negations inwards The goal of this step is to move all logical negations so that they are applied directly to feature comparisons. During the subsequent step, these logical negations are replaced by alternative comparison operators. This is achieved by repeated application of the following transformation rules: (! (& A1 A2 ... Am ) ) --> (| (! A1 ) (! A2 ) ... (! Am ) ) (! (| A1 A2 ... Am ) ) --> (& (! A1 ) (! A2 ) ... (! Am ) ) (! (! A ) ) --> A The first two rules are extended forms of De Morgan's law, and the third is elimination of double negatives. 2.5 Replace comparisons and logical negations The predicates are derived from the syntax described in RFC 2533, and contain primitive value testing functions '=', '<=', '>='. The primitive tests have a number of well known properties that are exploited to reach a useful conclusion; e.g. (A = B) & (B = C) => (A = C) (A <= B) & (B <= C) => (A <= C) These rules form a core body of logic statements against which the goal predicate can be evaluated. The first step in formulating these rules is to simplify the framework of primitive predicates. Klyne Internet draft [Page 8] A revised media feature set matching algorithm 6 April 2000 The original three comparisons (<=, >=, =) and their negations yield six possible forms of primitive predicate. These are reduced to combinations of just four functions, without negations, by the following transformation rules: (tag = value) --> (EQ tag value) (tag <= value) --> (LE tag value) (tag >= value) --> (GE tag value) (! (tag = value) ) --> (NE tag value) (! (tag <= value) ) --> (& (GE tag value) (NE tag value) ) (! (tag >= value) ) --> (& (LE tag value) (NE tag value) ) Thus, we have rules to transform all comparisons and logical negations into combinations of just 4 relational functions (LE, GE, EQ, NE). 2.6 Conversion to canonical form NOTE: Logical negations have been eliminated in the previous step. Expand bracketed disjunctions, and flatten bracketed conjunctions and disjunctions, by repeated application of the following transformations: (& (| A1 A2 ... Am ) B1 B2 ... Bn ) --> (| (& A1 B1 B2 ... Bn ) (& A2 B1 B2 ... Bn ) : (& Am B1 B2 ... Bn ) ) (& (& A1 A2 ... Am ) B1 B2 ... Bn ) --> (& A1 A2 ... Am B1 B2 ... Bn ) (| (| A1 A2 ... Am ) B1 B2 ... Bn ) --> (| A1 A2 ... Am B1 B2 ... Bn ) The result is in "disjunctive normal form", a disjunction of conjunctions: (| (& S11 S12 ... ) (& S21 S22 ... ) : (& Sm1 Sm2 ... Smn ) ) where the "Sij" elements are simple feature comparison forms constructed during the step at the previous section. Each term within the top-level "(|...)" construct represents a possible feature set that satisfies the goal. Note that the order of entries within the top-level '(|...)', and within each '(&...)', is immaterial. Klyne Internet draft [Page 9] A revised media feature set matching algorithm 6 April 2000 From here on, each conjunction '(&...)' is processed separately. Only one of these needs to be satisfiable for the original goal to be satisfiable. NOTE: A textbook conversion to clausal form [5,11] uses slightly different rules to yield a "conjunctive normal form". 2.7 Grouping of feature predicates Recall that, from here onwards, each conjunction is treated separately. Each simple feature comparison contains a "left-hand" feature tag and a "right-hand" feature value with which it is compared. To arrange these into independent groups, simple predicates are grouped according to their left hand feature tag. 2.8 Merge single-feature constraints Within each group of each conjunction, apply the predicate simplification rules given below to eliminate redundant single- feature constraints. All single-feature predicates are reduced to an equality or range constraint on that feature, possibly combined with a number of non-equality statements. If the constraints on any feature are found to be contradictory (i.e. resolved to (FALSE) according to the applied rules), the containing conjunction is not satisfiable and may be discarded. Otherwise, the resulting expression is a reduced form of the corresponding original conjunction. (LE f a) (LE f b) --> (LE f a), a<=b (LE f b), a>b (LE f a) (GE f b) --> (FALSE), a (FALSE), a=b (LE f a) (NE f b) --> (LE f a), a (GE f b), a=b (GE f a) (EQ f b) --> (EQ f b) a<=b (FALSE), a>b (GE f a) (NE f b) --> (GE f a) a>b Klyne Internet draft [Page 10] A revised media feature set matching algorithm 6 April 2000 (EQ f a) (EQ f b) --> (EQ f a), a=b (FALSE), a!=b (EQ f a) (NE f b) --> (EQ f a), a!=b (FALSE), a=b (NE f a) (NE f b) --> (NE f a), a=b NOTE: In the above table, occurrences (within a single conjunction) of the expressions on the left hand side of "-->" are replced by the right hand side expression, if and only if the condition after the "," is true. Thus: (A) (B) --> (R1), C1 (R2), C2 means: "replace "(A) (B)" with "(R1)" if "C1" is true, or with "(R2)" if "C2" is true, otherwise leave alone. 2.9 Presentation of feature comparisons If the original feature sets can be matched, the foregoing sections result in a number of reduced conjunctions that, when joined by a disjunction, represent the feature set that satisfies all of the original feature constraints. The feature set expression thus obtained can be displayed in the feature expression syntax of RFC 2533 [1] using the following representations for feature comparison functions: (EQ tag value) --> (tag = value) (LE tag value) --> (tag <= value) (GE tag value) --> (tag >= value) (NE tag value) --> (! (tag = value) ) 3 Worked example In the example that follows, for improved readability, expressions are presented throughout using the syntax of RFC 2533. Otherwise, the transformation steps followed correspond to those described in the previous section. This example considers sending a document to a high-end black-and- white fax system with the following receiver capabilities: (& (dpi=[200,300]) (color=binary) (image-coding=[MH,MR]) ) Turning to the document itself, assume it is available to the sender in three possible formats, A4 high resolution, B4 low resolution and A4 high resolution colour, described by: Klyne Internet draft [Page 11] A revised media feature set matching algorithm 6 April 2000 (& (dpi=300) (color=binary) (image-coding=MR) ) (& (dpi=200) (color=binary) (image-coding=[MH,MMR]) ) (& (dpi=300) (dpi-xyratio=1) (color=[grey,full]) (image-coding=JPEG) ) These three image formats can be combined into a composite capability statement by a logical-OR operation (to describe format-1 OR format-2 OR format-3): (| (& (dpi=300) (color=binary) (image-coding=MR) ) (& (dpi=200) (color=binary) (image-coding=[MH,MMR]) ) (& (dpi=300) (color=[grey,full]) (image-coding=JPEG) ) ) The composite document description can be matched with the receiver capability description by combining the capability descriptions with a logical AND operation: (& (& (dpi=[200,300]) (color=binary) (image-coding=[MH,MR]) ) (| (& (dpi=300) (color=binary) (image-coding=MR) ) (& (dpi=200) (color=binary) (image-coding=[MH,MMR]) ) (& (dpi=300) (color=[grey,full]) (image-coding=JPEG) ) ) ) --> Expand value-set notation: (& (& (| (dpi=200) (dpi=300) ) (color=binary) (| (image-coding=MH) (image-coding=MR) ) ) (| (& (dpi=300) (color=binary) Klyne Internet draft [Page 12] A revised media feature set matching algorithm 6 April 2000 (image-coding=MR) ) (& (dpi=200) (color=binary) (| (image-coding=MH) (image-coding=MMR) ) ) (& (dpi=300) (color=grey) (image-coding=JPEG) ) (& (dpi=300) (color=full) (image-coding=JPEG) ) ) ) -->Flatten nested '(&...)': (& (| (dpi=200) (dpi=300) ) (color=binary) (| (image-coding=MH) (image-coding=MR) ) (| (& (dpi=300) (color=binary) (image-coding=MR) ) (& (dpi=200) (color=binary) (| (image-coding=MH) (image-coding=MMR) ) ) (& (dpi=300) (color=grey) (image-coding=JPEG) ) (& (dpi=300) (color=full) (image-coding=JPEG) ) ) ) --> (distribute '(&...)' over inner '(|...)'): (& (| (dpi=200) (dpi=300) ) (color=binary) (| (image-coding=MH) (image-coding=MR) ) (| (& (dpi=300) (color=binary) (image-coding=MR) ) (& (dpi=200) (color=binary) (image-coding=MH) ) (& (dpi=200) (color=binary) (image-coding=MMR) ) (& (dpi=300) (color=grey) (image-coding=JPEG) ) (& (dpi=300) (color=full) (image-coding=JPEG) ) ) ) --> continue to distribute '(&...)' over '(|...)', and flattening nested '(&...)' and '(|...)' ...: (| (& (dpi=200) (color=binary) (image-coding=MH) (| (& (dpi=300) (color=binary) (image-coding=MR) ) (& (dpi=200) (color=binary) (image-coding=MH) ) (& (dpi=200) (color=binary) (image-coding=MMR) ) (& (dpi=300) (color=grey) (image-coding=JPEG) ) (& (dpi=300) (color=full) (image-coding=JPEG) ) ) ) (& (dpi=200) (color=binary) (image-coding=MR) Klyne Internet draft [Page 13] A revised media feature set matching algorithm 6 April 2000 (| (& (dpi=300) (color=binary) (image-coding=MR) ) (& (dpi=200) (color=binary) (image-coding=MH) ) (& (dpi=200) (color=binary) (image-coding=MMR) ) (& (dpi=300) (color=grey) (image-coding=JPEG) ) (& (dpi=300) (color=full) (image-coding=JPEG) ) ) ) (& (dpi=300) (color=binary) (image-coding=MH) (| (& (dpi=300) (color=binary) (image-coding=MR) ) (& (dpi=200) (color=binary) (image-coding=MH) ) (& (dpi=200) (color=binary) (image-coding=MMR) ) (& (dpi=300) (color=grey) (image-coding=JPEG) ) (& (dpi=300) (color=full) (image-coding=JPEG) ) ) ) (& (dpi=300) (color=binary) (image-coding=MR) (| (& (dpi=300) (color=binary) (image-coding=MR) ) (& (dpi=200) (color=binary) (image-coding=MH) ) (& (dpi=200) (color=binary) (image-coding=MMR) ) (& (dpi=300) (color=grey) (image-coding=JPEG) ) (& (dpi=300) (color=full) (image-coding=JPEG) ) ) ) Klyne Internet draft [Page 14] A revised media feature set matching algorithm 6 April 2000 --> ... until normal form is achieved: (| (& (dpi=200) (color=binary) (image-coding=MH) (dpi=300) (color=binary) (image-coding=MR) ) (& (dpi=200) (color=binary) (image-coding=MR) (dpi=300) (color=binary) (image-coding=MR) ) (& (dpi=300) (color=binary) (image-coding=MH) (dpi=300) (color=binary) (image-coding=MR) ) (& (dpi=300) (color=binary) (image-coding=MR) (dpi=300) (color=binary) (image-coding=MR) ) (& (dpi=200) (color=binary) (image-coding=MH) (dpi=200) (color=binary) (image-coding=MH) ) (& (dpi=200) (color=binary) (image-coding=MR) (dpi=200) (color=binary) (image-coding=MH) ) (& (dpi=300) (color=binary) (image-coding=MH) (dpi=200) (color=binary) (image-coding=MH) ) (& (dpi=300) (color=binary) (image-coding=MR) (dpi=200) (color=binary) (image-coding=MH) ) (& (dpi=200) (color=binary) (image-coding=MH) (dpi=200) (color=binary) (image-coding=MMR) ) (& (dpi=200) (color=binary) (image-coding=MR) (dpi=200) (color=binary) (image-coding=MMR) ) (& (dpi=300) (color=binary) (image-coding=MH) (dpi=200) (color=binary) (image-coding=MMR) ) (& (dpi=300) (color=binary) (image-coding=MR) (dpi=200) (color=binary) (image-coding=MMR) ) (& (dpi=200) (color=binary) (image-coding=MH) (dpi=300) (color=grey) (image-coding=JPEG) ) (& (dpi=200) (color=binary) (image-coding=MR) (dpi=300) (color=grey) (image-coding=JPEG) ) (& (dpi=300) (color=binary) (image-coding=MH) (dpi=300) (color=grey) (image-coding=JPEG) ) (& (dpi=300) (color=binary) (image-coding=MR) (dpi=300) (color=grey) (image-coding=JPEG) ) (& (dpi=200) (color=binary) (image-coding=MH) (dpi=300) (color=full) (image-coding=JPEG) ) (& (dpi=200) (color=binary) (image-coding=MR) (dpi=300) (color=full) (image-coding=JPEG) ) (& (dpi=300) (color=binary) (image-coding=MH) (dpi=300) (color=full) (image-coding=JPEG) ) (& (dpi=300) (color=binary) (image-coding=MR) (dpi=300) (color=full) (image-coding=JPEG) ) ) --> Group terms in each conjunction by feature tag: (| (& (dpi=200) (dpi=300) (color=binary) (color=binary) (image-coding=MH) (image-coding=MR) ) (& (dpi=200) (dpi=300) (color=binary) (color=binary) (image-coding=MR) (image-coding=MR) ) : Klyne Internet draft [Page 15] A revised media feature set matching algorithm 6 April 2000 (etc.) : (& (dpi=300) (dpi=300) (color=binary) (color=full) (image-coding=MR) (image-coding=JPEG) ) ) --> Combine feature tag comparisons and eliminate unsatisfiable conjunctions: (| (& (dpi=300) (color=binary) (image-coding=MR) ) (& (dpi=200) (color=binary) (image-coding=MH) ) ) Thus, we see that this combination of sender and receiver options can transfer a bi-level image, either at 300dpi using MR coding, or at 200dpi using MH coding. Points to note about the feature matching process: o The colour document option is eliminated because the receiver cannot handle either colour (indicated by '(color=[grey,full])') or (image-coding=JPEG). o The high resolution version of the document with '(dpi=300)' must be sent using '(image-coding=MR)' because this is the only available coding of the image data that the receiver can use for high resolution documents. (The available 300dpi document codings here are MMR and MH, and the receiver capabilities are MH and MR.) 4. Security considerations Security considerations are discussed in RFC 2533 [1] and related documents. This memo does not introduce any additional security considerations. 5. Acknowledgements Work to develop the feature set matching algorithm, and to provide a public implementation, has been supported by 5th Generation Messaging Ltd. Thanks also to Paul Hoffman of Internet Mail Consortium for making the source code [15] available for general access at the IMC web site. Klyne Internet draft [Page 16] A revised media feature set matching algorithm 6 April 2000 6. References [1] RFC 2533, "A syntax for describing media feature sets" Graham Klyne, 5GM/Content Technologies March 1999. [2] RFC 2506, "Media Feature Tag Registration Procedure" Koen Holtman, TUE Andrew Mutz, Hewlett-Packard Ted Hardie, NASA March 1999. [5] "Programming in Prolog" (2nd edition) W. F. Clocksin and C. S. Mellish, Springer Verlag ISBN 3-540-15011-0 / 0-387-15011-0 1984. [10] RFC 2234, "Augmented BNF for Syntax Specifications: ABNF" D. Crocker (editor), Internet Mail Consortium P. Overell, Demon Internet Ltd. November 1997. [11] "Logic, Algebra and Databases" Peter Gray Ellis Horwood Series: Computers and their Applications ISBN 0-85312-709-3/0-85312-803-3 (Ellis Horwood Ltd) ISBN 0-470-20103-7/0-470-20259-9 (Halstead Press) 1984. [12] "Logic and its Applications" Edmund Burk and Eric Foxley Prentice Hall, Series in computer science ISBN 0-13-030263-5 1996. [15] Java source code of feature set matching algorithm Linked from Klyne Internet draft [Page 17] A revised media feature set matching algorithm 6 April 2000 7. Author's address Graham Klyne Content Technologies Ltd. 1220 Parkview, Arlington Business Park Theale Reading, RG7 4SA United Kingdom. Telephone: +44 118 930 1300 Facsimile: +44 118 930 1301 E-mail: GK@ACM.ORG Appendix A: Amendment history 00a 11-Jun-1999 This memo created to contain a description of a revised version of the feature set matching algorithm from RFC 2533 [1]. 00b 15-Jun-1999 Some small adjustments to the feature matching algorithm to align it more closely with the source code posted. Bring worked example up to date with current fax feature schema (on which it has been based). 01a 26-Jul-1999 Add note describing the notation used in the feature comparison reduction tables. 02a 06-Apr-2000 Re-issued to keep draft available in I-D repository. Updated contact details. Full copyright statement Copyright (C) The Internet Society 1999. All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. Klyne Internet draft [Page 18] A revised media feature set matching algorithm 6 April 2000 The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Klyne Internet draft [Page 19]