EDP Sciences logo
Subscriber Authentication Point
Search
Menu
All issues Volume 30 / No 6 (1996) RAIRO-Theor. Inf. Appl., 30 6 (1996) 521-544 References
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] [Google Scholar]
  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] [Google Scholar]
  3. 3. A. APOSTOLICO, Optimal parallel detection of squares in strings, Algorithmica, 1992, 8, pp. 285-319. [MR: 1186900] [Zbl: 0748.68022] [Google Scholar]
  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] [Google Scholar]
  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. [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  9. 9. R. P. BRENT, Evaluation of general arithmetic expressions, J. Assoc. Comput. Mach., 1974, 21, pp. 201-206. [MR: 660280] [Zbl: 0276.68010] [Google Scholar]
  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. [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  16. 16. M. CROCHEMORE, Transducers and repetitions, Theoret. Comput. Sci., 1986, 12, pp. 63-86. [MR: 865967] [Zbl: 0615.68053] [Google Scholar]
  17. 17. M. CROCHEMORE, Z. GALIL, L. GASIENIEC, K. PARK and W. RYTTER, Constant-time randomized parallel string matching, Manuscript, 1994. [Zbl: 0885.68078] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  24. 24. Z. GALIL, Optimal parallel algorithms for string matching, Inform. and Control, 1985, 67, pp. 144-157. [MR: 833865] [Zbl: 0588.68022] [Google Scholar]
  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. [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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. [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  37. 37. A. THUE, Über unendliche zeichenreihen, Norske Vid. Selsk. Skr. Mat. Nat. Kl. (Cristiania), 1906, 7, pp. 1-22. [JFM: 39.0283.01] [Google Scholar]
  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] [Google Scholar]
  39. 39. U. VISHKIN, Optimal parallel pattern matching in strings, Inform. and Control, 1985, 67, pp. 91-113. [MR: 833862] [Zbl: 0588.68023] [Google Scholar]
  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] [Google Scholar]

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.