# Linear size test sets for certain commutative languages

Štěpán Holub; Juha Kortelainen

RAIRO - Theoretical Informatics and Applications (2010)

- 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 35.5 (2010): 453-475. <http://eudml.org/doc/222009>.

@article{Holub2010,

abstract = {
We prove that for each positive integer n, the finite commutative language
En = c(a1a2...an) possesses a test set of size at most 5n. Moreover, it is shown that each test set for En 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 ∈ 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 = Card(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},

keywords = {finite commutative language; word equations},

language = {eng},

month = {3},

number = {5},

pages = {453-475},

publisher = {EDP Sciences},

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

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

volume = {35},

year = {2010},

}

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

DA - 2010/3//

PB - EDP Sciences

VL - 35

IS - 5

SP - 453

EP - 475

AB -
We prove that for each positive integer n, the finite commutative language
En = c(a1a2...an) possesses a test set of size at most 5n. Moreover, it is shown that each test set for En 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 ∈ 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 = Card(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/222009

ER -

## References

top- J. Albert, On test sets, checking sets, maximal extensions and their effective constructions. Habilitationsschirft, Fakultät für Wirtschaftswissenschaften der Universität Karlsruhe (1968).
- M.H. Albert and J. Lawrence, A proof of Ehrenfeucht`s Conjecture. Theoret. Comput. Sci.41 (1985) 121-123.
- J. Albert and D. Wood, Checking sets, test sets, rich languages and commutatively closed languages. J. Comput. System Sci.26 (1983) 82-91. Zbl0507.68049
- 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.
- 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. Algebra85 (1983) 76-85.
- P. Erdös and G. Szekeres, A combinatorial problem in geometry. Compositio Math.2 (1935) 464-470.
- I. Hakala, On word equations and the morphism equivqalence problem for loop languages. Academic dissertation, Faculty of Science, University of Oulu (1997).
- I. Hakala and J. Kortelainen, On the system of word equations x0u1ix1u2ix2u3ix3 = y0v1iy1iv2iy2v3iy3(i = 0,1,2,...) in a free monoid. Theoret. Comput. Sci.225 (1999) 149-161.
- I. Hakala and J. Kortelainen, Linear size test sets for commutative languages. RAIRO: Theoret. Informatics Appl.31 (1997) 291-304. Zbl0889.68091
- 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.
- M.A. Harrison, Introduction to Formal Language Theory. Addison-Wesley, Reading, Reading Massachusetts (1978). Zbl0411.68058
- S. Holub, Local and global cyclicity in free monoids. Theoret. Comput. Sci.262 (2001) 25-36. Zbl0983.68097
- J. Karhumäki and W. Plandowski, On the size of independent systems of equations in semigroups. Theoret. Comput. Sci.168 (1996) 105-119. Zbl0877.20039
- J. Kortelainen, On the system of word equations x0u1ix1u2ix2...umixm=y0v1iy1v2iy2...vniyn(i=1,2,...) in a free monoid. J. Autom. Lang. Comb.3 (1998) 43-57.
- M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading Massachusetts (1983). Zbl0514.20045
- A. Salomaa, The Ehrenfeucht conjecture: A proof for language theorists. Bull. EATCS27 (1985) 71-82.

## Citations in EuDML Documents

top## NotesEmbed ?

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