Linear size test sets for certain commutative languages

Holub, Štěpán ; Kortelainen, Juha

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 5, pp. 453-475

Résumé

We prove that for each positive integer $n,$ the finite commutative language $E_n=c(a_1{a}_2\cdots a_n)$ 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) $\text{alph}\left(w\right)=\text{alph}\left(L\right);$ and (ii) each symbol $a\in \text{alph}\left(L\right)$ 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=\text{Card}\left(\text{alph}\left(L\right)\right)$. The considerations rest on the analysis of some basic types of word equations.

Détail

Classification : 68R15