Linear size test sets for certain commutative languages

Holub, Štěpán; Kortelainen, Juha

Geodesic

Parcourir par

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) no. 5, pp. 453-475

Voir la notice de l'article provenant de la source Numdam

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.

EuDML MR Zbl

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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/item/ITA_2001__35_5_453_0/