The first item of the seed, S , covers all and only the states of the target: the left projection of these pairs is thus linear in n and every right projection is at most n • m + p. Thus the size of S is at most n Concerning the second part, S , its cardinality is at most n • |Σ| (in the rare case where Q = Q).
each element of the left projection of S is of length (k + 1) and each element of its right projection is at most of length (k + 1) the size of the characteristic sample is in , which is clearly polynomial in the size of the target transducer.