Optimal parallel two dimensional pattern matching

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal parallel two dimensional pattern matching

Full text

Pdf (661 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures table of contents

Velen, Germany

Pages: 79 - 85

Year of Publication: 1993

ISBN:0-89791-599-2

Authors

Amihood Amir
Gary Benson
Martin Farach

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
European Comp Soc : European Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 33, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/165231.165242 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.

	AB92	Amihood Amir , Gary Benson, Two-dimensional periodicity and its applications, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.440-452, September 1992, Orlando, Florida, United States
	ABF92	Amihood Amir , Gary Benson , Martin Farach, Alphabet independent two dimensional matching, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.59-68, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129719]
	AC75	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]
	Bak78	T.J. Baker. A technique for extending rapid exact-match string matching to arrays of more than one dimension. SIAM J. Comp, 7:533-541, 1978.
	BG90	Dany Breslauer , Zvi Galil, An optimal O(log n)time parallel string matching algorithm, SIAM Journal on Computing, v.19 n.6, p.1051-1058, Dec. 1990 [doi>10.1137/0219072]
	Bir77	R.S. Bird. Two dimensional pattern matching. Information Processing Letters, 6:168- 170, 1977.
	BM77	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]
	CDR86	Stephen Cook , Cynthia Dwork , Ru&duml;ger Reischuk, Upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM Journal on Computing, v.15 n.1, p.87-97, Feb. 1986 [doi>10.1137/0215006]
	CGG+93	M. Crochemore, Z. Galil, L. Gasieniec, S. Muthukrishnan, K. Park, H. Ramesh, and W. Rytter. Manuscript, 1993.
	CGR92	M. Crochemore, L. Gasieniec, and W. Rytter. Constant time optimal parallel algorithm for 2d-pattern matching. Manuscript, 1992.
	FRA88	Faith E. Fich , Prabhakar Ragde , Avi Wigderson, Relations between concurrent-write models of parallel computation, SIAM Journal on Computing, v.17 n.3, p.606-627, June 1988 [doi>10.1137/0217037]
	Gal85	Z. Galil. Open problems in stringology. In Z. Galil A. Apostolico, editor, Combinatorial Algorithms on Words, volume 12, pages 1-8. NATO ASI Series F, 1985.
	Gal92	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 [doi>10.1145/129712.129720]
	GP92	Z. Galil and K. Park. Truly alphabet independent two-dimensional pattern matching. Prec. of the 33rd IEEE Annual Syrup. on Foundation of Computer Science, 1992.
	KLP89	Z. M. Kedem , G. M. Landau , K. V. Palem, Optimal parallel suffix-prefix matching algorithm and applications, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.388-398, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72977]
	KMP77	D.E. Knuth, 3. H. Morris, and V. R. Pratt. Fast pattern matching in strings. SIAM J. Comp., 6:323-350, 1977.
	MR92	S. Muthukrishnan and H. Ramesh. A constant time optimal parallel algorithm for two dimensional pattern matching. Manuscript, 1992.
	RK82	Azriel Rosenfeld , Avinash C. Kak, Digital Picture Processing, Academic Press, Inc., Orlando, FL, 1982
	Vis85	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]
	Vis91	Uzi Vishkin, Deterministic sampling: a new technique for fast pattern matching, SIAM Journal on Computing, v.20 n.1, p.22-40, Feb. 1991 [doi>10.1137/0220002]

CITED BY 4

	Artur Czumaj , Zvi Galil , Leszek Gąsieniec , Kunsoo Park , Wojciech Plandowski, Work-time-optimal parallel algorithms for string problems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.713-722, May 29-June 01, 1995, Las Vegas, Nevada, United States
	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
	Zvi Galil , Jong Geun Park , Kunsoo Park, Three-dimensional pattern matching, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.53-62, June 23-25, 1997, Newport, Rhode Island, United States
	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