Linear size test sets for certain commutative languages
Turku Centre for Computer Science & Charles University, Prague, Czech
2 Department of Information Processing Science, University of Oulu, P.O. Box 3000, 90014 Oulun Yliopisto, Finland
Accepted: December 2001
We prove that for each positive integer n, the finite commutative language En = c(a1a2...an) possesses a test set of size at most 5n. Moreover, it is shown that each test set for En 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.
Mathematics Subject Classification: 68R15
© EDP Sciences, 2001