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.

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.

[1] J. Albert, On test sets, checking sets, maximal extensions and their effective constructions. Habilitationsschirft, Fakultät für Wirtschaftswissenschaften der Universität Karlsruhe (1968).

[2] M.H. Albert and J. Lawrence, A proof of Ehrenfeucht‘s Conjecture. Theoret. Comput. Sci. 41 (1985) 121-123. | Zbl

[3] J. Albert and D. Wood, Checking sets, test sets, rich languages and commutatively closed languages. J. Comput. System Sci. 26 (1983) 82-91. | MR | Zbl

[4] Ch. Choffrut and J. Karhumäki, Combinatorics on words, in Handbook of Formal Languages, Vol. I, edited by G. Rosenberg and A. Salomaa. Springer-Verlag, Berlin (1997) 329-438. | MR

[5] A. Ehrenfeucht, J. Karhumäki and G. Rosenberg, On binary equality sets and a solution to the test set conjecture in the binary case. J. Algebra 85 (1983) 76-85. | MR | Zbl

[6] P. Erdös and G. Szekeres, A combinatorial problem in geometry. Compositio Math. 2 (1935) 464-470. | JFM | Numdam | MR

[7] I. Hakala, On word equations and the morphism equivqalence problem for loop languages. Academic dissertation, Faculty of Science, University of Oulu (1997). | MR | Zbl

[8] I. Hakala and J. Kortelainen, On the system of word equations $x_0{u}_1^i{x}_1{u}_2^i{x}_2{u}_3^i{x}_3=y_0{v}_1^i{y}_1^i{v}_2^i{y}_2{v}_3^i{y}_3$ $(i=0,1,2,\cdots )$ in a free monoid. Theoret. Comput. Sci. 225 (1999) 149-161. | MR | Zbl

[9] I. Hakala and J. Kortelainen, Linear size test sets for commutative languages. RAIRO: Theoret. Informatics Appl. 31 (1997) 291-304. | Numdam | MR | Zbl

[10] T. Harju and J. Karhumäki, Morphisms, in Handbook of Formal Languages, Vol. I, edited by G. Rosenberg and A. Salomaa. Springer-Verlag, Berlin (1997) 439-510. | MR | Zbl

[11] M.A. Harrison, Introduction to Formal Language Theory. Addison-Wesley, Reading, Reading Massachusetts (1978). | MR | Zbl

[12] Š. Holub, Local and global cyclicity in free monoids. Theoret. Comput. Sci. 262 (2001) 25-36. | MR | Zbl

[13] J. Karhumäki and W. Plandowski, On the size of independent systems of equations in semigroups. Theoret. Comput. Sci. 168 (1996) 105-119. | MR | Zbl

[14] J. Kortelainen, On the system of word equations $x_0{u}_1^i{x}_1{u}_2^i{x}_2\cdots u_m^i{x}_m=y_0{v}_1^i{y}_1{v}_2^i{y}_2\cdots v_n^i{y}_n$ $(i=1,2,...)$ in a free monoid. J. Autom. Lang. Comb. 3 (1998) 43-57. | MR | Zbl

[15] M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading Massachusetts (1983). | MR | Zbl

[16] A. Salomaa, The Ehrenfeucht conjecture: A proof for language theorists. Bull. EATCS 27 (1985) 71-82.