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

Abstract

top
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.

How to cite

top

Holub, Š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
  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.  
  3. J. Albert and D. Wood, Checking sets, test sets, rich languages and commutatively closed languages. J. Comput. System Sci.26 (1983) 82-91.  
  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.  
  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. Algebra85 (1983) 76-85.  
  6. P. Erdös and G. Szekeres, A combinatorial problem in geometry. Compositio Math.2 (1935) 464-470.  
  7. I. Hakala, On word equations and the morphism equivqalence problem for loop languages. Academic dissertation, Faculty of Science, University of Oulu (1997).  
  8. 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.  
  9. I. Hakala and J. Kortelainen, Linear size test sets for commutative languages. RAIRO: Theoret. Informatics Appl.31 (1997) 291-304.  
  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.  
  11. M.A. Harrison, Introduction to Formal Language Theory. Addison-Wesley, Reading, Reading Massachusetts (1978).  
  12. S. Holub, Local and global cyclicity in free monoids. Theoret. Comput. Sci.262 (2001) 25-36.  
  13. J. Karhumäki and W. Plandowski, On the size of independent systems of equations in semigroups. Theoret. Comput. Sci.168 (1996) 105-119.  
  14. 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.  
  15. M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading Massachusetts (1983).  
  16. A. Salomaa, The Ehrenfeucht conjecture: A proof for language theorists. Bull. EATCS27 (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.