An incremental depth-first algorithm for computing the S- and G-set of
Mitchell's Candidate Elimination and Mellish's Description Identifica
tion algorithm is presented. As in Mellish's approach, lowerbounds (ex
amples) as well as upperbounds can be handled. Instead of storing the
complete S- and G-sets, only one element s is an element of S and g is
an element of G is stored, together with backtrack information. The w
orst-case space complexity of our algorithm is linear in the number of
lower- and upperbounds. For the Candidate Elimination algorithm this
can be exponential. We introduce a test for membership of S and G with
a number of coverage tests linear in the number of examples. Conseque
ntly the worst-case time complexity to compute S and G for each exampl
e is only a linear factor worse than the Candidate Elimination algorit
hm's.