Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-23T17:08:49.877Z Has data issue: false hasContentIssue false
  • English
  • Français

Linear size test sets for certain commutative languages

Published online by Cambridge University Press:  15 August 2002

Štěpán Holub  and
Juha Kortelainen
Štěpán Holub
Affiliation:
Turku Centre for Computer Science & Charles University, Prague, Czech Republic Department of Information Processing Science, University of Oulu, P.O. Box 3000, 90014 Oulun Yliopisto, Finland
Juha Kortelainen
Affiliation:
Turku Centre for Computer Science & Charles University, Prague, Czech Republic Department of Information Processing Science, University of Oulu, P.O. Box 3000, 90014 Oulun Yliopisto, Finland
Get access

Abstract

We prove that for each positive integer n, the finite commutative languageEn = c(a 1 a 2...an ) 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) 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.

Keywords

Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 35 , Issue 5 , September 2001 , pp. 453 - 475
Copyright
© EDP Sciences, 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

J. Albert, On test sets, checking sets, maximal extensions and their effective constructions. Habilitationsschirft, Fakultät für Wirtschaftswissenschaften der Universität Karlsruhe (1968).
Albert, M.H. and Lawrence, J., A proof of Ehrenfeucht`s Conjecture. Theoret. Comput. Sci. 41 (1985) 121-123. CrossRef
Albert, J. and Wood, D., Checking sets, test sets, rich languages and commutatively closed languages. J. Comput. System Sci. 26 (1983) 82-91. CrossRef
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.
Ehrenfeucht, A., Karhumäki, J. and Rosenberg, G., On binary equality sets and a solution to the test set conjecture in the binary case. J. Algebra 85 (1983) 76-85. CrossRef
Erdös, P. and Szekeres, G., 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).
Hakala, I. and Kortelainen, J., 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. CrossRef
Hakala, I. and Kortelainen, J., Linear size test sets for commutative languages. RAIRO: Theoret. Informatics Appl. 31 (1997) 291-304.
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).
Holub, S., Local and global cyclicity in free monoids. Theoret. Comput. Sci. 262 (2001) 25-36. CrossRef
Karhumäki, J. and Plandowski, W., On the size of independent systems of equations in semigroups. Theoret. Comput. Sci. 168 (1996) 105-119. CrossRef
Kortelainen, J., 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.
M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading Massachusetts (1983).
Salomaa, A., The Ehrenfeucht conjecture: A proof for language theorists. Bull. EATCS 27 (1985) 71-82.