Detecting the morphic images of a word : improving the general algorithm

 Access to full text

 Full (PDF)

1. [An 80] D. ANGLUIN, Finding Patterns Common to a Set of Strings, Journal of Computer and Syst. Sci., 1980, 21, pp. 46-62. Zbl0454.68108MR589803
2. [AC 75] A. AHAO and M. CORACICK, Efficient String Matching: An Aid to Bibliographic Search, Comm. ACM, 1975. Zbl0301.68048MR371172
3. [AP 83] A. APOSTOLICO and F. P. PREPARATA, Optimal off-line detection of repetitions in a string, Theoret. Comput. Sci., 1983, 22, pp. 297-315. Zbl0497.68052MR693062
4. [B 92] K. BAKER, Open problems on avoidable and unavoidable patterns, manuscript (Université de Rouen, France). 
5. [C 81] M. CROCHEMORE, An optimal algorithm for computing the repetitions in a word, Information Proc. Letters, 1981, 12, pp. 244-250. Zbl0467.68075MR632873
6. [CN 89] M. CROCHEMORE and J. NÉRAUD, Unitary monoid with two generators: an algorithmic point of view, in: Proceedings of CAAP'90, 1990. Zbl0758.68053MR1075026
7. [CLR 90] T. TCORMEN, C. LEISERSON and R. RIVEST, "Introduction to Algorithm", The MIT Press, 1990 Zbl1158.68538
8. [CR 91] M. CROCHEMORE and W. RYTTER, Periodic prefixes of string, in: Acts of Sequences '91, 1991. 
9. [CR 94] M. CROCHEMORE and W. RYTTER, "Text Algoriths", Oxford University Press, 1994. Zbl0844.68101MR1307378
10. [GS 83] Z. GALIL and J. SEIFERAS, Saving space in fast string-matching, SIAM J. Comput., 1980, pp. 417-438. Zbl0446.68041MR568822
11. [JSSY 95] TAO JIANG, A. SALOMAA, K. SALOMAA and SHENG YU, Decision problems for patters, Journ. of Comput. Syst. Sci., 1995, 50(1), pp. 53-63. Zbl0827.68066MR1322633
12. [K 73] D. KNUTH, "Sorting and Searching", vol. 3, of "The Art of Computer Programming". Addison Wesley 1969, Second edition, 1981. Zbl0883.68015
13. [KMP 77] D. KNUTH, J. MORRIS and V. PRATT, Fast pattern matching in string, SIAM J. Comput., 1977, 6, No. 2, pp. 323-350. Zbl0372.68005MR451916
14. [Lo 83] M. LOTHAIRE, "Compbinatorics on words", Encyclopedia of Mathematics and appl., Addison Wesley Publish. Company, 1983. Zbl0514.20045MR675953
15. [ML 85] G. MAIN and J. LORENTZ, Linear time recognition of squarefree string, in "Combinatoric Algorithms on Words", A. Apostolica and Z. Galil eds., NATO ASI, Springer Verlag, Berlin, 1985 (1), pp. 5-37 Zbl0572.68068MR815345
16. [N 95] J. NÉRAUD, Algorithms for detecting morphic images of a word, Info. and Comput., 1995,120, No. 1, pp. 126-148. Zbl0835.68091MR1340812
17. [N 95.1] J. NÉRAUD, Detecting morphic images of a word: On the rank of a pattern, Acta Info., 1994. Zbl0843.68106MR1348438
18. [R 85] O. RABIN, Discovering repetitions in string, in "Combinatoric Algorithms on Words", A. Apostolico and Z. Galil eds., NATO ASI, Springer Verlag, Berlin, 1985. Zbl0604.68074MR815327