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

Abstract

top
We prove that for each positive integer n , the finite commutative language E n = c ( a 1 a 2 ⋯ 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 ∈ 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.

How to cite

top

Holub, Š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. [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. [2] M.H. Albert and J. Lawrence, A proof of Ehrenfeucht‘s Conjecture. Theoret. Comput. Sci. 41 (1985) 121-123. Zbl0602.68066
  3. [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. [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. [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. [6] P. Erdös and G. Szekeres, A combinatorial problem in geometry. Compositio Math. 2 (1935) 464-470. MR1556929JFM61.0651.04
  7. [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. [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 , ⋯ ) in a free monoid. Theoret. Comput. Sci. 225 (1999) 149-161. Zbl0930.68076MR1708036
  9. [9] I. Hakala and J. Kortelainen, Linear size test sets for commutative languages. RAIRO: Theoret. Informatics Appl. 31 (1997) 291-304. Zbl0889.68091MR1483261
  10. [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. [11] M.A. Harrison, Introduction to Formal Language Theory. Addison-Wesley, Reading, Reading Massachusetts (1978). Zbl0411.68058MR526397
  12. [12] Š. Holub, Local and global cyclicity in free monoids. Theoret. Comput. Sci. 262 (2001) 25-36. Zbl0983.68097MR1836209
  13. [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. [14] J. Kortelainen, On the system of word equations x 0 u 1 i x 1 u 2 i x 2 ⋯ u m i x m = y 0 v 1 i y 1 v 2 i y 2 ⋯ v n i y n ( i = 1 , 2 , ... ) in a free monoid. J. Autom. Lang. Comb. 3 (1998) 43-57. Zbl0919.68078MR1663869
  15. [15] M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading Massachusetts (1983). Zbl0514.20045MR675953
  16. [16] A. Salomaa, The Ehrenfeucht conjecture: A proof for language theorists. Bull. EATCS 27 (1985) 71-82. 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.