ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Optimal parallel suffix-prefix matching algorithm and applications
Full text PdfPdf (1.07 MB)
Source ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the first annual ACM symposium on Parallel algorithms and architectures table of contents
Santa Fe, New Mexico, United States
Pages: 388 - 398  
Year of Publication: 1989
ISBN:0-89791-323-X
Authors
Z. M. Kedem  Department of Computer Science, Courant Institute, of Mathematical Sciences, New York University, 251 Mercer St., New York, NY
G. M. Landau  lComputer Science Division, Polytechnic Univ., 333 Jay St., Brooklyn New York, NY
K. V. Palem  IBM Research Division, T.J. Watson Research Center, P. O. Box 704, Yorktown Heights, NY
Sponsors
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 7,   Downloads (12 Months): 35,   Citation Count: 9
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/72935.72977
What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

1
Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975  [doi>10.1145/360825.360855]
 
2
G. M. Landau , B. Schieber , U. Vishkin, Parallel construction of a suffix tree, 14th International Colloquium on Automata, languages and programming, p.314-325, July 1987, Karlsruhe, Germany
 
3
A. Amir , G. M. Landau, Fast parallel and serial multidimensional approximate array matching, Sequences: combinatorics, compression, security, and transmission, Springer-Verlag New York, Inc., New York, NY, 1990
 
4
[Ba78] T.P. Baker, "A Technique For Extending Rapid Exact-Match String Matching to Arrays of More Than One Dimension," SIAM J. Comput, Vol. 7, No. 4, 1978, 533- 541.
 
5
[Bi77] R.S. Bird, "Two Dimensional Pattern Matching," Information Processing Letters , Vol. 6, No. 5, 1977, 168-170.
6
Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974  [doi>10.1145/321812.321815]
7
O. Berkman , Z. Galil , B. Schieber , U. Vishkin, Highly parallelizable problems, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.309-319, May 14-17, 1989, Seattle, Washington, United States  [doi>10.1145/73007.73036]
8
Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977  [doi>10.1145/359842.359859]
 
9
[CD88] J. L. Cornette and C. Delisi, "Some Mathematical Aspects of Mapping DNA Cosmids," Cell Biopysics, Vol. 12, 1988, 271- 293.
10
Richard E. Ladner , Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980  [doi>10.1145/322217.322232]
11
Zvi Galil*, Optimal parallel algorithms for string matching, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.240-248, December 1984  [doi>10.1145/800057.808687]
 
12
[GS83] Z. Galil and J. I. Seiferas, "Time-space Optimal String Matching," J. Computer and Systems Sciences, Vol. 26, 1983, 280-294. 338.-355.
 
13
[KLP88] Z. M. Kedem, G. M. Landau, and K. V. Palem, "Optimal Parallel Algorithms for Matching Problems," Technical report 410, Dept. of Computer Science, Courant Inst., NYU, November, 1988.
 
14
[KMP77] D.E. Knuth, J.H. Morris and V.R. Pratt, "Fast pattern matching in strings," SIAM J. Comput., Vol. 6, 1977, 323-350.
15
Richard M. Karp , Raymond E. Miller , Arnold L. Rosenberg, Rapid identification of repeated patterns in strings, trees and arrays, Proceedings of the fourth annual ACM symposium on Theory of computing, p.125-136, May 01-03, 1972, Denver, Colorado, United States  [doi>10.1145/800152.804905]
 
16
Zvi M. Kedem , Krishna V. Palem, Optimal parallel algorithms for forest and term matching, Theoretical Computer Science, v.93 n.2, p.245-264, 17 Feb. 1992  [doi>10.1016/0304-3975(92)90332-A]
 
17
Richard M. Karp , Michael O. Rabin, Efficient randomized pattern-matching algorithms, IBM Journal of Research and Development, v.31 n.2, p.249-260, March 1987
 
18
[M88] T.R. Mathies, "A Fast Parallel Algorithm to Determine Edit Distance," CMU-CS- 88-130.
 
19
J. Tarhio , E. Ukkonen, A greedy approximation algorithm for constructing shortest common superstrings, Theoretical Computer Science, v.57 n.1, p.131-145, April 1988  [doi>10.1016/0304-3975(88)90167-3]
 
20
Uzi Vishkin, Optimal parallel pattern matching in strings, Information and Control, v.67 n.1-3, p.91-113, Oct./Nov./Dec. 1986  [doi>10.1016/S0019-9958(85)80028-0]

CITED BY  9
Zvi Galil, A constant-time optimal parallel string-matching algorithm, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.69-76, May 04-06, 1992, Victoria, British Columbia, Canada
Zvi Galil, A constant-time optimal parallel string-matching algorithm, Journal of the ACM (JACM), v.42 n.4, p.908-918, July 1995
S. Muthukrishnan , K. Palem, Highly efficient dictionary matching in parallel, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.69-78, June 30-July 02, 1993, Velen, Germany
Amihood Amir , Gary Benson , Martin Farach, Optimal parallel two dimensional pattern matching, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.79-85, June 30-July 02, 1993, Velen, Germany
Z. M. Kedem , K. V. Palem , P. G. Spirakis, Efficient robust parallel computations, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.138-148, May 13-17, 1990, Baltimore, Maryland, United States
Martin Farach , S. Muthukrishnan, Optimal parallel dictionary matching and compression (extended abstract), Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.244-253, June 24-26, 1995, Santa Barbara, California, United States
Ramesh Hariharan, Optimal parallel suffix tree construction, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.290-299, May 23-25, 1994, Montreal, Quebec, Canada
Raffaele Giancarlo , Roberto Grossi, Parallel construction and query of suffix trees for two-dimensional matrices, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.86-97, June 30-July 02, 1993, Velen, Germany
R. A. Baeza-Yates, Algorithms for string searching, ACM SIGIR Forum, v.23 n.3-4, p.34-58, Spring 1989

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION


General Terms:
Algorithms, Theory

Collaborative Colleagues:
Z. M. Kedem: colleagues
G. M. Landau: colleagues
K. V. Palem: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player