Linear size test sets for certain commutative languages
Štěpán Holub, Juha Kortelainen · RAIRO - Theoretical Informatics and Applications · 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.