a1 Turku Centre for Computer Science & Charles University, Prague, Czech Republic
a2 Department of Information Processing Science, University of Oulu, P.O. Box 3000, 90014 Oulun Yliopisto, Finland
We prove that for each positive integer n, the finite commutative language En = c(a 1 a 2...an ) possesses a test set of size at most 5n. Moreover, it is shown that each test set for E n has at least n-1 elements. The result is then generalized to commutative languages L containing a word w such that (i) alph(w) = alph}(L); and (ii) each symbol a ∈ alph}(L) occurs at least twice in w if it occurs at least twice in some word of L: each such L possesses a test set of size 11n, where n = Card(alph(L)). The considerations rest on the analysis of some basic types of word equations.
(Received April 2001)
(Accepted December 2001)
(Online publication August 15 2002)
Mathematics Subject Classification: