Polynomial size test sets for commutative languages
Hakala, Ismo ; Kortelainen, Juha
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 31 (1997), p. 291-304 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{ITA_1997__31_3_291_0,
     author = {Hakala, Ismo and Kortelainen, Juha},
     title = {Polynomial size test sets for commutative languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {31},
     year = {1997},
     pages = {291-304},
     mrnumber = {1483261},
     zbl = {0889.68091},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1997__31_3_291_0}
}

Hakala, Ismo; Kortelainen, Juha. Polynomial size test sets for commutative languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 31 (1997) pp. 291-304. http://gdmltest.u-ga.fr/item/ITA_1997__31_3_291_0/

1. J. Albert and K. Culik Ii, Test sets for homomorphism équivalence on context free languages, Information and Control, 1980, 45, pp. 273-284. | MR 590851 | Zbl 0453.68048

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. | MR 701592 | Zbl 0522.68064

3. M. H. Albert and J. Lawrence, A proof of Ehrenfeucht's conjecture, Theoret. Comput. Sci., 1985, 41, pp. 121-123. | MR 841029 | Zbl 0602.68066

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. | MR 699221 | Zbl 0507.68049

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. | MR 1465039 | Zbl 0877.68073

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). | MR 1708036

7. M. A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, Reading Massachusetts, 1978. | MR 526397 | Zbl 0411.68058

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. | MR 1250630 | Zbl 0834.68065

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. | MR 1322629 | Zbl 0834.68065

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. | MR 1231947 | Zbl 0793.68090

11. M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading Massachusetts, 1983. | MR 675953 | Zbl 0514.20045