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), p. 453-475 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

Résumé

We prove that for each positive integer $n,$ the finite commutative language $E_{n} = c (a_{1} a_{2} \dots a_{n})$ possesses a test set of size at most $5 n .$ 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 \in 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 $11 n$ , where $n = Card (alph (L))$ . The considerations rest on the analysis of some basic types of word equations.

Publié le : 2001-01-01

MR 1908866 | Zbl 1010.68103 | 1 citation dans Numdam

Classification: 68R15

@article{ITA_2001__35_5_453_0,
     author = {Holub, \v St\v ep\'an and Kortelainen, Juha},
     title = {Linear size test sets for certain commutative languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {35},
     year = {2001},
     pages = {453-475},
     mrnumber = {1908866},
     zbl = {1010.68103},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 453-475. http://gdmltest.u-ga.fr/item/ITA_2001__35_5_453_0/

Bibliographie

[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}$ $(i = 0, 1, 2, \dots)$ 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} \dots u_{m}^{i} x_{m} = y_{0} v_{1}^{i} y_{1} v_{2}^{i} y_{2} \dots v_{n}^{i} y_{n}$ $(i = 1, 2, ...)$ 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.