RAIRO - Theoretical Informatics and Applications

Research Article

Linear size test sets for certain commutative languages

Štěpán Holuba1a2 and Juha Kortelainena1a2

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:

  • 68R15