VERSION SPACE represents all the alternative PLAUSIBLE
        DESCRIPTIONS of the heuristic.  A plausible description is one that
        is applicable to all known positive examples and no known negative
        example.

        Algorithm: CANDIDATE ELIMINATION

            Given: - A representation language
                   - A set of positive and negative examples expressed in
                     that language

            Compute: A concept description that is consistent with all the
            positive examples and none of the negative examples.

            Method: - Initialize G to contain one element: the null
                      description (all features are variables).
                    - Initialize S to contain one element: the first positive
                      example.
                    - Accept a new training example.
                        - If it is a positive example:
                            - Remove from G any descriptions that do not
                              cover the example.
                            - Update the S set to contain the most specific
                              set of descriptions in the version space that
                              cover the example and the current elements of
                              the S set (i.e., generalize the elements of S
                              as little as possible so that they cover the
                              new training example).
                        - If it is a negative example:
                            - Remove from S any descriptions that cover the
                              example.
                            - Update the G set to contain the most general
                              set of descriptions in the version space that
                              do not cover the example (i.e., specialize the
                              elements of G as little as possible so that the
                              negative example is no longer covered by any of
                              the elements of G).
                    - If S and G are both singleton sets, then:
                            - if they are identical, output their value and
                              halt.
                            - if they are different, the training cases were
                              inconsistent.  Output this result and halt.
                            - else continue accepting new training examples.

Example (from Rich & Knight): Learning the concept of "Japanese economy car"

        Features: Origin, Manufacturer, Color, Decade, Type

        POSITIVE EXAMPLE: (Japan, Honda, Blue, 1980, Economy)

            Initialize G to singleton set that includes everything
            Initialize S to singleton set that includes first positive example

            G = {(?, ?, ?, ?, ?)}
            S = {(Japan, Honda, Blue, 1980, Economy)}

        NEGATIVE EXAMPLE: (Japan, Toyota, Green, 1970, Sports)

            Specialize G to exclude negative example

            G = {(?, Honda, ?, ?, ?),
                 (?, ?, Blue, ?, ?)
                 (?, ?, ?, 1980, ?)
                 (?, ?, ?, ?, Economy)}
            S = {(Japan, Honda, Blue, 1980, Economy)}

        POSITIVE EXAMPLE: (Japan, Toyota, Blue, 1990, Economy)

            Prune G to exclude descriptions inconsistent with positive example
            Generalize S to include positive example

            G = {(?, ?, Blue, ?, ?)
                 (?, ?, ?, ?, Economy)}
            S = {(Japan, ?, Blue, ?, Economy)}

        NEGATIVE EXAMPLE: (USA, Chrysler, Red, 1980, Economy)

            Specialize G to exclude negative example
            (but staying within version space, i.e., staying consistent with S)

            G = {(Japan, ?, Blue, ?, ?)
                 (Japan, ?, ?, ?, Economy)}
            S = {(Japan, ?, Blue, ?, Economy)}

        POSITIVE EXAMPLE: (Japan, Honda, White, 1980, Economy)

            Prune G to exclude descriptions inconsistent with positive example
            Generalize S to include positive example

            G = {(Japan, ?, ?, ?, Economy)}
            S = {(Japan, ?, ?, ?, Economy)}

            S = G, both singleton => done!