Free Access
Issue
RAIRO-Theor. Inf. Appl.
Volume 30, Number 6, 1996
Page(s) 521 - 544
DOI https://doi.org/10.1051/ita/1996300605211
Published online 01 February 2017
  1. 1. C. AMIR, G. BENSON and M. FARACH, An alphabet-independent approach to two-dimensional pattern-matching, SIAM J. Comput., 1994, 23 (2), pp. 313-323. [MR: 1267212] [Zbl: 0804.68056]
  2. 2. A. APOSTOLICO, On context constrained squares and repetitions in a string, RAIRO Informatique théorique, 1984, 18 (2), pp. 147-159. [EuDML: 92203] [MR: 761514] [Zbl: 0543.68067]
  3. 3. A. APOSTOLICO, Optimal parallel detection of squares in strings, Algorithmica, 1992, 8, pp. 285-319. [MR: 1186900] [Zbl: 0748.68022]
  4. 4. A. APOSTOLICO and D. BRESLAUER, An optimal O (log log n) time parallel algorithm for detecting all squares in a string, SIAM J. Comput., to appear. [MR: 1417902] [Zbl: 0864.68045]
  5. 5. A. APOSTOLICO, D. BRESLAUER and Z. GALIL, Optimal parallel algorithms for periods, palindromes and squares. In Proc. 19th International Colloquium on Automata, Languages, and Programming, number 623 in Lecture Notes in Computer Science, pages 206-307. Springer-Verlag, Berlin, Germany, 1992.
  6. 6. A. APOSTOLICO, D. BRESLAUER and Z. GALIL, Parallel detection of all palindromes in a string, Theoret. Comput. Sci., 1995, 141 (1), pp. 163-173. [MR: 1323153] [Zbl: 0873.68039]
  7. 7. 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]
  8. 8. V. L. ARLAZAROV, E. A. DINIC, M. A. KRONROD and I. A. FARADZEV, On economic construction of the transitive closure of a directed graph, Soviet Math. Dokl., 1970, 11, pp. 1209-1210. [Zbl: 0214.23601]
  9. 9. R. P. BRENT, Evaluation of general arithmetic expressions, J. Assoc. Comput. Mach., 1974, 21, pp. 201-206. [MR: 660280] [Zbl: 0276.68010]
  10. 10. D. BRESLAUER, A. CZUMAJ, D. DUBHASI and F. MEYER auf der Heide, Transforming comparison model lower bounds to the parallel-random-access-machine, 5th Italian Conference on Theoretical Computer Science, Villa Rufolo, 1995, Italy.
  11. 11. D. BRESLAUER and Z. GALIL, An optimal O (log log n) time parallel string matching algorithm, SIAM J. Comput., 1990, 19 (6), pp. 1051-1058. [MR: 1069098] [Zbl: 0711.68057]
  12. 12. D. BRESLAUER and Z. GALIL, A lower bound for parallel string matching, SIAM J. Comput., 1992, 21 (5), pp. 856-862. [MR: 1181403] [Zbl: 0756.68048]
  13. 13. D. BRESLAUER and Z. GALIL, Finding all periods and initial palindromes of a string in parallel, Algorithmica, to appear. [MR: 1343321] [Zbl: 0833.68053]
  14. 14. R. COLE, M. CROCHEMORE, Z. GALIL, L. GASIENIEC, R. HARIHARAN, S. MUTHUKRISHNAN, K. PARK and W. RYTTER, Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions. In Proc. 34th IEEE Symp. on Foundations of Computer Science, 1993, pp. 248-258. [MR: 1328425]
  15. 15. M. CROCHEMORE, An optimal algorithm for Computing the repetitions in a word, Inform. Process. Lett., 1981, 12 (5), pp. 244-250. [MR: 632873] [Zbl: 0467.68075]
  16. 16. M. CROCHEMORE, Transducers and repetitions, Theoret. Comput. Sci., 1986, 12, pp. 63-86. [MR: 865967] [Zbl: 0615.68053]
  17. 17. M. CROCHEMORE, Z. GALIL, L. GASIENIEC, K. PARK and W. RYTTER, Constant-time randomized parallel string matching, Manuscript, 1994. [Zbl: 0885.68078]
  18. 18. M. CROCHEMORE, L. GASIENIEC, R. HARIHARAN, S. MUTHUKRISHNAN and W. RYTTER, A constant time optimal parallel algorithm for two dimensional pattern matching. Manuscript, 1993. [Zbl: 0912.68067]
  19. 19. M. CROCHEMORE and W. RYTTER, Efficient parallel algorithms to test square-freeness and factorize strings, Inform. Process. Lett., 1991, 38, pp. 57-60. [MR: 1113337] [Zbl: 0736.68033]
  20. 20. M. CROCHEMORE and W. RYTTER, Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays, Theoret. Comput. Sci., 1991, 88, pp. 59-82. [MR: 1130372] [Zbl: 0737.68037]
  21. 21. F. E. RICH, R. L. RAGDE and A. WIGDERSON, Relations between concurrent-write models of parallel computation, SIAM J. Comput., 1988, 17 (3), pp. 606-627. [MR: 941948] [Zbl: 0652.68065]
  22. 22. M. J. FISCHER and M. S. PATERSON, String matching and other products. In R. M. KARP, editor, Complexity of Computation, pp. 113-125. American Mathematical Society, Prividence, RI., 1974. [MR: 400782] [Zbl: 0301.68027]
  23. 23. Z. GALIL, Palindrome recognition in real time by a multiple turing machine, J. Comput. System. Sci., 1978, 16 (2), pp. 140-157. [MR: 483670] [Zbl: 0386.03020]
  24. 24. Z. GALIL, Optimal parallel algorithms for string matching, Inform. and Control, 1985, 67, pp. 144-157. [MR: 833865] [Zbl: 0588.68022]
  25. 25. Z. GALIL, A constant-time optimal parallel string-matching algorithm. In Proc. 24th ACM Symp. on Theory of Computing, 1992, pp. 69-76.
  26. 26. Z. GALIL and K. PARK, Truly alphabet-independent two-dimensional pattern matching. In Proc. 33th IEEE Symp. on Foundations of Computer Sciences, 1992, pp. 247-256. [Zbl: 0942.68707]
  27. 27. T. GOLDBERG and U. ZWICK, Faster parallel string matching via larger deterministic samples. J. Algorithms, 1994, 16 (2), pp. 295-308. [MR: 1258241] [Zbl: 0797.68083]
  28. 28. D. E. KNUTH, J. H. MORRIS and V. R. PRATT, Fast pattern matching in strings, SIAM J. Comput. Sci., 1977, 6, pp. 322-350. [MR: 451916] [Zbl: 0372.68005]
  29. 29. S. R. KOSARAJU, Computation of squares in a string. In Proc. 5th Symp. on Combinatorial Pattern Matching, number 807 in Lecture Notes in Computer Science, pp. 146-150. Springer-Verlag, Berlin, Germany, 1994.
  30. 30. R. E. LADNER and M. J. FISCHER, Parallel prefix computation, J. Assoc. Comput. Mach., 1980, 27 (4), pp. 831-838. [MR: 594702] [Zbl: 0445.68066]
  31. 31. R. C. LYNDON and M. P. SCHÜTZENBRGER, The equation am = bn cp in a free group. Michigan Math. J., 1962, 9, pp. 289-298. [MR: 162838] [Zbl: 0106.02204]
  32. 32. G. M. MAIN and R. J. LORENTZ, An O (n log n) algorithm for finding all repetitions in a string, J. Algorithms, 1984, 5, pp. 422-432. [MR: 756167] [Zbl: 0547.68083]
  33. 33. G. M. MAIN and R. J. LORENTZ, Linear time recognition of squarefree strings. In A. APOSTOLICO and Z. GALIL, editors, Combinatorial Algorithms on Words, volume 12 of NATO ASI Series F, pp. 271-278. Springer-Verlag, Berlin, Germany, 1985. [MR: 815345] [Zbl: 0572.68068]
  34. 34. G. MANACHER, A new linear-time "on-line" algorithm for finding the smallest initial palindrome of a string, J. Assoc. Comput. Mach., 1975, 22, pp. 346-351. [Zbl: 0305.68027]
  35. 35. M. O. RABIN, Discovering repetitions in strings. In A. APOSTOLICO and Z. GALIL, editors, Combinatorial Algorithms on Words, volume 12 of NATO ASI Series F, pp. 279-288. Springer-Verlag, Berlin, Germany, 1985. [MR: 815346] [Zbl: 0604.68074]
  36. 36. A. O. SLISENKO, Recognition of palindromes by multihead turing machines. In V. P. ORVERKOV and N. A. SONIN, editors, Problems in the Constructive Trend in Mathematics VI (Proceedings of the Steklov Institute of Mathematics, No. 129), pp. 30-202. Academy of Sciences of the USSR, 1973. English Translation by R. H. SILVERMAN, pp. 25-208, Amer. Math. Soc., Providence, RI, 1976. [MR: 432422] [Zbl: 0326.02027]
  37. 37. A. THUE, Über unendliche zeichenreihen, Norske Vid. Selsk. Skr. Mat. Nat. Kl. (Cristiania), 1906, 7, pp. 1-22. [JFM: 39.0283.01]
  38. 38. A. THUE, Über die gegenseitige lage gleicher teile gewisser zeichenreihen, Norske Vid. Selsk. Skr. Mat. Nat. Kl. (Cristiania), 1912, 1, pp. 1-67. [Zbl: 44.0462.01] [JFM: 44.0462.01]
  39. 39. U. VISHKIN, Optimal parallel pattern matching in strings, Inform. and Control, 1985, 67, pp. 91-113. [MR: 833862] [Zbl: 0588.68023]
  40. 40. U. VISHKIN, Deterministic sampling - a new technique for fast pattern matching, SIAM J. Comput., 1990, 20 (1), pp. 22-40. [MR: 1082134] [Zbl: 0716.68074]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.