The complexity of identifying large equivalence classes

• Autorzy: Skyum S. , Frandsen G.S. , Miltersen P.B. , Binderup P.G.
• Języki publikacji: EN

Abstrakty

EN

We prove that at least ...equivalence testes and no more than ... equivalence testes 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 k>n/2 we prove that it is necessary and it suffices to make 2n-k-1 equivalence testes which generalizes a known result.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 1999
• Tom: Vol. 38, Nr 1,2
• Strony: 25--37
• Opis fizyczny: bibliogr. 13 poz.

Twórcy

autor

Skyum S.

autor

Frandsen G.S.

autor

Miltersen P.B.

autor

Binderup P.G.

• BRICS, Basic Research in Computer Science, Centre of the Danish National Research Foun-dation, Department of Computer Science, University of Aarhus