Detecting the morphic images of a word : improving the general algorithm
Néraud, Jean
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 31 (1997), p. 1-14 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1997-01-01
@article{ITA_1997__31_1_1_0,
     author = {N\'eraud, Jean},
     title = {Detecting the morphic images of a word : improving the general algorithm},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {31},
     year = {1997},
     pages = {1-14},
     mrnumber = {1460455},
     zbl = {0878.68079},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1997__31_1_1_0}
}

Néraud, Jean. Detecting the morphic images of a word : improving the general algorithm. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 31 (1997) pp. 1-14. http://gdmltest.u-ga.fr/item/ITA_1997__31_1_1_0/

[An 80] D. Angluin, Finding Patterns Common to a Set of Strings, Journal of Computer and Syst. Sci., 1980, 21, pp. 46-62. | MR 589803 | Zbl 0454.68108

[AC 75] A. Ahao and M. Coracick, Efficient String Matching: An Aid to Bibliographic Search, Comm. ACM, 1975. | MR 371172 | Zbl 0301.68048

[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. | MR 693062 | Zbl 0497.68052

[B 92] K. Baker, Open problems on avoidable and unavoidable patterns, manuscript (Université de Rouen, France).

[C 81] M. Crochemore, An optimal algorithm for computing the repetitions in a word, Information Proc. Letters, 1981, 12, pp. 244-250. | MR 632873 | Zbl 0467.68075

[CN 89] M. Crochemore and J. Néraud, Unitary monoid with two generators: an algorithmic point of view, in: Proceedings of CAAP'90, 1990. | MR 1075026 | Zbl 0758.68053

[CLR 90] T. Tcormen, C. Leiserson and R. Rivest, "Introduction to Algorithm", The MIT Press, 1990 | Zbl 1158.68538

[CR 91] M. Crochemore and W. Rytter, Periodic prefixes of string, in: Acts of Sequences '91, 1991.

[CR 94] M. Crochemore and W. Rytter, "Text Algoriths", Oxford University Press, 1994. | MR 1307378 | Zbl 0844.68101

[GS 83] Z. Galil and J. Seiferas, Saving space in fast string-matching, SIAM J. Comput., 1980, pp. 417-438. | MR 568822 | Zbl 0446.68041

[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. | MR 1322633 | Zbl 0827.68066

[K 73] D. Knuth, "Sorting and Searching", vol. 3, of "The Art of Computer Programming". Addison Wesley 1969, Second edition, 1981. | Zbl 0883.68015

[KMP 77] D. Knuth, J. Morris and V. Pratt, Fast pattern matching in string, SIAM J. Comput., 1977, 6, No. 2, pp. 323-350. | MR 451916 | Zbl 0372.68005

[Lo 83] M. Lothaire, "Compbinatorics on words", Encyclopedia of Mathematics and appl., Addison Wesley Publish. Company, 1983. | MR 675953 | Zbl 0514.20045

[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 | MR 815345 | Zbl 0572.68068

[N 95] J. Néraud, Algorithms for detecting morphic images of a word, Info. and Comput., 1995,120, No. 1, pp. 126-148. | MR 1340812 | Zbl 0835.68091

[N 95.1] J. Néraud, Detecting morphic images of a word: On the rank of a pattern, Acta Info., 1994. | MR 1348438 | Zbl 0843.68106

[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. | MR 815327 | Zbl 0604.68074