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\left({a}_{1}{a}_{2}\cdots {a}_{n}\right)$ 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.

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},
zbl = {1010.68103},
mrnumber = {1908866},
language = {en},
url = {http://www.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
DA  - 2001///
SP  - 453
EP  - 475
VL  - 35
IS  - 5
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_2001__35_5_453_0/
UR  - https://zbmath.org/?q=an%3A1010.68103
UR  - https://www.ams.org/mathscinet-getitem?mr=1908866
LA  - en
ID  - ITA_2001__35_5_453_0
ER  - 
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://www.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 0602.68066

[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 699221 | Zbl 0507.68049

[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 1469998

[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 723068 | Zbl 0523.68066

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

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

[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}$ $\left(i=0,1,2,\cdots \right)$ in a free monoid. Theoret. Comput. Sci. 225 (1999) 149-161. | MR 1708036 | Zbl 0930.68076

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

[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 1469999 | Zbl 0866.68057

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

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

[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 1424994 | Zbl 0877.20039

[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}$ $\left(i=1,2,...\right)$ in a free monoid. J. Autom. Lang. Comb. 3 (1998) 43-57. | MR 1663869 | Zbl 0919.68078

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

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