×

Linear size test sets for certain commutative languages. (English) Zbl 1010.68103

Summary: 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 (alph}(L))\). The considerations rest on the analysis of some basic types of word equations.

MSC:

68R15 Combinatorics on words
PDF BibTeX XML Cite
Full Text: DOI Numdam Numdam EuDML

References:

[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 . Zbl 0602.68066 · Zbl 0602.68066
[3] J. Albert and D. Wood , Checking sets, test sets, rich languages and commutatively closed languages . J. Comput. System Sci. 26 ( 1983 ) 82 - 91 . MR 699221 | Zbl 0507.68049 · Zbl 0507.68049
[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 . MR 1469998
[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 . MR 723068 | Zbl 0523.68066 · Zbl 0523.68066
[6] P. Erdös and G. Szekeres , A combinatorial problem in geometry . Compositio Math. 2 ( 1935 ) 464 - 470 . Numdam | MR 1556929 | JFM 61.0651.04 · JFM 61.0651.04
[7] I. Hakala , On word equations and the morphism equivqalence problem for loop languages . Academic dissertation, Faculty of Science, University of Oulu ( 1997 ). MR 1486576 | Zbl 0978.68533 · Zbl 0978.68533
[8] I. Hakala and J. Kortelainen , On the system of word equations \(x_0u_1^ix_1u_2^ix_2u_3^ix_3 = y_0v_1^iy_1^iv_2^iy_2v_3^iy_3\) \((i=0,1,2,\dots )\) in a free monoid . Theoret. Comput. Sci. 225 ( 1999 ) 149 - 161 . MR 1708036 | Zbl 0930.68076 · Zbl 0930.68076
[9] I. Hakala and J. Kortelainen , Linear size test sets for commutative languages . RAIRO: Theoret. Informatics Appl. 31 ( 1997 ) 291 - 304 . Numdam | MR 1483261 | Zbl 0889.68091 · Zbl 0889.68091
[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 . MR 1469999 | Zbl 0866.68057 · Zbl 0866.68057
[11] M.A. Harrison , Introduction to Formal Language Theory . Addison-Wesley, Reading, Reading Massachusetts ( 1978 ). MR 526397 | Zbl 0411.68058 · Zbl 0411.68058
[12] Š. Holub , Local and global cyclicity in free monoids . Theoret. Comput. Sci. 262 ( 2001 ) 25 - 36 . MR 1836209 | Zbl 0983.68097 · Zbl 0983.68097
[13] J. Karhumäki and W. Plandowski , On the size of independent systems of equations in semigroups . Theoret. Comput. Sci. 168 ( 1996 ) 105 - 119 . MR 1424994 | Zbl 0877.20039 · Zbl 0877.20039
[14] J. Kortelainen , On the system of word equations \(x_0u_1^ix_1u_2^ix_2 \cdots u_m^ix_m=y_0v_1^iy_1v_2^iy_2 \cdots v_n^iy_n\) \((i=1,2, \ldots )\) in a free monoid . J. Autom. Lang. Comb. 3 ( 1998 ) 43 - 57 . MR 1663869 | Zbl 0919.68078 · Zbl 0919.68078
[15] M. Lothaire , Combinatorics on Words . Addison-Wesley, Reading Massachusetts ( 1983 ). MR 675953 | Zbl 0514.20045 · Zbl 0514.20045
[16] A. Salomaa , The Ehrenfeucht conjecture: A proof for language theorists . Bull. EATCS 27 ( 1985 ) 71 - 82 .
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.