Polynomial size test sets for commutative languages
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1997)
- Volume: 31, Issue: 3, page 291-304
- ISSN: 0988-3754
Access Full Article
topHow to cite
topReferences
top- 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.68048MR590851
- 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.68064MR701592
- 3. M. H. ALBERT and J. LAWRENCE, A proof of Ehrenfeucht's conjecture, Theoret. Comput. Sci., 1985, 41, pp. 121-123. Zbl0602.68066MR841029
- 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.68049MR699221
- 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.68073MR1465039
- 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. M. A. HARRISON, Introduction to Formal Language Theory, Addison-Wesley, Reading Massachusetts, 1978. Zbl0411.68058MR526397
- 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.68065MR1250630
- 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.68065MR1322629
- 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.68090MR1231947
- 11. M. LOTHAIRE, Combinatorics on Words, Addison-Wesley, Reading Massachusetts, 1983. Zbl0514.20045MR675953