# Linear size test sets for certain commutative languages

Štěpán Holub; Juha Kortelainen

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2001)

- Volume: 35, Issue: 5, page 453-475
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topHolub, Štěpán, and Kortelainen, Juha. "Linear size test sets for certain commutative languages." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 35.5 (2001): 453-475. <http://eudml.org/doc/92677>.

@article{Holub2001,

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

author = {Holub, Štěpán, Kortelainen, Juha},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {finite commutative language; word equations},

language = {eng},

number = {5},

pages = {453-475},

publisher = {EDP-Sciences},

title = {Linear size test sets for certain commutative languages},

url = {http://eudml.org/doc/92677},

volume = {35},

year = {2001},

}

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

PB - EDP-Sciences

VL - 35

IS - 5

SP - 453

EP - 475

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

LA - eng

KW - finite commutative language; word equations

UR - http://eudml.org/doc/92677

ER -

## References

top- [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. Zbl0602.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. Zbl0507.68049MR699221
- [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. MR1469998
- [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. Zbl0523.68066MR723068
- [6] P. Erdös and G. Szekeres, A combinatorial problem in geometry. Compositio Math. 2 (1935) 464-470. MR1556929JFM61.0651.04
- [7] I. Hakala, On word equations and the morphism equivqalence problem for loop languages. Academic dissertation, Faculty of Science, University of Oulu (1997). Zbl0978.68533MR1486576
- [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. Zbl0930.68076MR1708036
- [9] I. Hakala and J. Kortelainen, Linear size test sets for commutative languages. RAIRO: Theoret. Informatics Appl. 31 (1997) 291-304. Zbl0889.68091MR1483261
- [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. Zbl0866.68057MR1469999
- [11] M.A. Harrison, Introduction to Formal Language Theory. Addison-Wesley, Reading, Reading Massachusetts (1978). Zbl0411.68058MR526397
- [12] Š. Holub, Local and global cyclicity in free monoids. Theoret. Comput. Sci. 262 (2001) 25-36. Zbl0983.68097MR1836209
- [13] J. Karhumäki and W. Plandowski, On the size of independent systems of equations in semigroups. Theoret. Comput. Sci. 168 (1996) 105-119. Zbl0877.20039MR1424994
- [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. Zbl0919.68078MR1663869
- [15] M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading Massachusetts (1983). Zbl0514.20045MR675953
- [16] A. Salomaa, The Ehrenfeucht conjecture: A proof for language theorists. Bull. EATCS 27 (1985) 71-82.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.