J. Karhumaki et al., EFFICIENT CONSTRUCTIONS OF TEST SETS FOR REGULAR AND CONTEXT-FREE LANGUAGES, Theoretical computer science, 116(2), 1993, pp. 305-316
We present a simple construction of linear size test sets for regular
languages and of single exponential test sets for context-free languag
es. In the case of regular sets the size of our test set is exactly th
e number of transitions of the automaton. This improves the best-known
upper bounds: exponential for regular and doubly exponential for cont
ext-free languages. We give also an O(n log n) time algorithm for the
morphism equivalence and an O(n3 log n) time algorithm to test the gsm
equivalence on a regular language. An O(n2 log n) time algorithm is g
iven to test the equivalence of two deterministic gsm's as well as tha
t of two deterministic finite transducers.