We prove that each context-free language possesses a test set of size
O(m(6)), where m is the number of productions in a grammar-producing t
he language. A context-free grammar generating the test set can be fou
nd in polynomial time by a sequential algorithm. It improves the doubl
y exponential upper bound from [2] and single exponential one from J.
Karhumaki, W. Rytter, and S. Jarominek (Theoret. Comput. Sci. 116 (199
3), 305-316). On the other hand, we show that the lower bound for the
problem is Omega(m(3)) and that the lower bound for the size of a test
set for a language defined over n-letter alphabet is Omega(n(3)). (C)
1995 Academic Press, Inc.