## Polynomial size test sets for commutative languages.(English)Zbl 0889.68091

Summary: It is proved that any commutative language over an alphabet of $$n$$ symbols possesses a test set of size $$O(n^2)$$. If the Parikh-map of the language is a linear set, then the minimum size of the test set is $$O(n\log n)$$. A finite commutative language over an alphabet of $$n$$ symbols such that the smallest test set for the language is of size $$\Omega(n^2)$$ is shown to exist.

### MSC:

 68Q45 Formal languages and automata

### Keywords:

commutative language
Full Text:

### References:

 [1] 1. J. ALBERT and K. CULIK II, Test sets for homomorphism équivalence on context free languages, Information and Control, 1980, 45, pp. 273-284. Zbl0453.68048 MR590851 · Zbl 0453.68048 [2] 2. J. ALBERT, K. CULIK II and J. KARHUMÄKI, Test sets for context free languages and algebraic systems of equations over free monoid, Information and Control, 1982, 52, pp. 172-186. Zbl0522.68064 MR701592 · Zbl 0522.68064 [3] 3. M. H. ALBERT and J. LAWRENCE, A proof of Ehrenfeucht’s conjecture, Theoret. Comput. Sci., 1985, 41, pp. 121-123. Zbl0602.68066 MR841029 · Zbl 0602.68066 [4] 4. J. ALBERT and D. WOOD, Checking sets, test sets rich languages and commutatively closed languages, Journal of Computer and System Sciences, 1983, 26, pp. 82-91. Zbl0507.68049 MR699221 · Zbl 0507.68049 [5] 5. I. HAKALA and J. KORTELAINEN, On the system of word equations xi1 xi2...xim = yi1 yi2...y1n (i = 1, 2, ...) in a free monoid, Acta Inform., 1997, 34, pp. 217-230. Zbl0877.68073 MR1465039 · Zbl 0877.68073 [6] 6. I. HAKALA and J. KORTELAINEN, On the system of word equations xo ui1 xo ui1 x1 ui2 x2 ui3 x3 = yo vi1 y1 vi2 y2 vi3 y3 (i = 0, 1, 2,...) in a free monoid, Theor. Comput Sci. (to appear). MR1708036 [7] 7. M. A. HARRISON, Introduction to Formal Language Theory, Addison-Wesley, Reading Massachusetts, 1978. Zbl0411.68058 MR526397 · Zbl 0411.68058 [8] 8. J. KARHUMÄKI, W. PLANDOWSKI and W. RYTTER, Polynomial-size test sets for context-free languages, Lecture Notes in Computer Sciences, 1992, 623, pp. 53-64. Zbl0834.68065 MR1250630 · Zbl 0834.68065 [9] 9. J. KARHUMÄKI, W. PLANDOWSKI and W. RYTTER, Polynomial-size test sets for context-free languages, Journal of Computer and System Sciences, 1995, 50, pp. 11-19. Zbl0834.68065 MR1322629 · Zbl 0834.68065 [10] 10. J. KARHUMÄKI, W. PLANDOWSKI and S. JAROMINEK, Efficient construction of test sets for regular and context-free languages, Theor. Comp. Sci., 1993, 116, pp. 305-316. Zbl0793.68090 MR1231947 · Zbl 0793.68090 [11] 11. M. LOTHAIRE, Combinatorics on Words, Addison-Wesley, Reading Massachusetts, 1983. Zbl0514.20045 MR675953 · Zbl 0514.20045
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.