Abstract:
We prove that at least 
equivalence tests and no more than 
equivalence tests are needed in the worst case to identify the
equivalence classes with at least k members in set of n elements. The
upper bound is an improvement by a factor 2 compared to known results. For
k=3 we give tighter bounds. Finally, for 
we prove that it
is necessary and it suffices to make 2n-k-1 equivalence tests which
generalizes a known result for 
Available as PostScript, PDF, DVI.