ITERATIVE VERSIONSPACES

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.