Linear size test sets for certain commutative languages
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 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) alph(w)=alph(L); and (ii) each symbol aalph(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.

Classification : 68R15
@article{ITA_2001__35_5_453_0,
     author = {Holub, \v{S}t\v{e}p\'an and Kortelainen, Juha},
     title = {Linear size test sets for certain commutative languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {453--475},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {5},
     year = {2001},
     mrnumber = {1908866},
     zbl = {1010.68103},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_2001__35_5_453_0/}
}
TY  - JOUR
AU  - Holub, Štěpán
AU  - Kortelainen, Juha
TI  - Linear size test sets for certain commutative languages
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2001
SP  - 453
EP  - 475
VL  - 35
IS  - 5
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_2001__35_5_453_0/
LA  - en
ID  - ITA_2001__35_5_453_0
ER  - 
%0 Journal Article
%A Holub, Štěpán
%A Kortelainen, Juha
%T Linear size test sets for certain commutative languages
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2001
%P 453-475
%V 35
%N 5
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_2001__35_5_453_0/
%G en
%F ITA_2001__35_5_453_0
Holub, Štěpán; Kortelainen, Juha. Linear size test sets for certain commutative languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 5, pp. 453-475. http://archive.numdam.org/item/ITA_2001__35_5_453_0/

[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,) 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 u m i x m =y 0 v 1 i y 1 v 2 i y 2 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.