W3C home > Mailing lists > Public > www-archive@w3.org > April 2003

draft-klyne-conneg-feature-match-02.txt

From: Luu Tran <Luu.Tran@Sun.COM>
Date: Thu, 17 Apr 2003 11:35:28 -0700
To: www-archive@w3.org
Message-id: <3E9EF3F0.1060900@sun.com>

IETF media feature registration WG                        Graham Klyne
Internet draft                                    Content Technologies
                                                           6 April 2000
                                                  Expires: October 2000


             A revised media feature set matching algorithm
               <draft-klyne-conneg-feature-match-02.txt>

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
<draft-klyne-conneg-feature-match-02.txt>




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
<draft-klyne-conneg-feature-match-02.txt>


   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
<draft-klyne-conneg-feature-match-02.txt>


   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
<draft-klyne-conneg-feature-match-02.txt>


   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
<draft-klyne-conneg-feature-match-02.txt>


        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
<draft-klyne-conneg-feature-match-02.txt>


      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
<draft-klyne-conneg-feature-match-02.txt>


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
<draft-klyne-conneg-feature-match-02.txt>


   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
<draft-klyne-conneg-feature-match-02.txt>


   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<b
                                   (EQ f a)    a=b
      (LE f a)  (EQ f b)      -->  (FALSE),    a<b
                                   (EQ f b),   a>=b
      (LE f a)  (NE f b)      -->  (LE f a),   a<b

      (GE f a)  (GE f b)      -->  (GE f b),   a<b
                                   (GE f a),   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
<draft-klyne-conneg-feature-match-02.txt>


      (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
<draft-klyne-conneg-feature-match-02.txt>


      (& (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
<draft-klyne-conneg-feature-match-02.txt>


               (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
<draft-klyne-conneg-feature-match-02.txt>


            (| (& (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
<draft-klyne-conneg-feature-match-02.txt>


   -->  ... 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
<draft-klyne-conneg-feature-match-02.txt>


            (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
<draft-klyne-conneg-feature-match-02.txt>


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 <http://www.imc.org/ietf-medfree/>

















Klyne                       Internet draft                   [Page 17]

A revised media feature set matching algorithm            6 April 2000
<draft-klyne-conneg-feature-match-02.txt>


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
<draft-klyne-conneg-feature-match-02.txt>


   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]
Received on Thursday, 17 April 2003 16:13:25 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Wednesday, 7 November 2012 14:17:29 GMT