A lower bound for parallel string matching

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A lower bound for parallel string matching

Full text

Pdf (467 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-third annual ACM symposium on Theory of computing table of contents

New Orleans, Louisiana, United States

Pages: 439 - 443

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

Dany Breslauer	Columbia Univ., New York, NY
Zvi Galil	Columbia Univ., New York, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 26, 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/103418.103465 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.

	AILSV	Ap#talia#, A., Iliopoulae, C., Landau, C_ M., Schieber, B. and Vishkin, U. (1988), Parallel construction of a suffix tree with applications, Algorithmica 2, 347-365.
	BG	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]
	BFKLT	A. Borodin , S. Cook, A time-space tradeoff for sorting on a general sequential model of computation, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.294-301, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804677]
	BM	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]
	C	Crochemore, M., String-Matching and Periods, In Bulletin of EATCS, October 1989.
	CP	Crochemore, M. and Perrin, D. (1989), Two way pattern matching, JA CM, to appear.
	FRW	Faith E. Fich , Prabhakar L. Ragde , Avi Wigderson, Relations between concurrent-write models of parallel computation, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.179-189, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806745]
	G	Zvi Galil, Optimal parallel algorithms for string matching, Information and Control, v.67 n.1-3, p.144-157, Oct./Nov./Dec. 1986 [doi>10.1016/S0019-9958(85)80031-0]
	GS80	Galil, Z., Seiferas, J. (1980), Saving space in fast string-matching, SIAM J. on Comput. 2, 417-438.
	GS83	Galil, Z., Seifera.s, J. (1983), Time-spaceoptimal string matching, J. Comput. Sysl. Sci. 26, 280-294.
	GL	Ger6b-Oraus, M. and Li, M. (199,9), Three one-way heads cannot do string matching, manuscript.
	KMP	Knuth, D. E., Morris, a. H. and Pratt, V. R. (1977), Fast pattern matching in strings, SIAM J. Comput. 6, 322-350.
	L	Ming Li, Lower Bounds on String-Matching, Cornell University, Ithaca, NY, 1984
	LY	Ming Li , Y. Yesha, String-matching cannot be done by a two-head one-way deterministic finite automation, Information Processing Letters, v.22 n.5, p.231-235, April 1986 [doi>10.1016/0020-0190(86)90099-2]
	RS	Rosser, J. B. and Schoenfeld, L. (1962), Approximate formulas for some functions of prime numbers, Illinois Journal of Mathematics, 6:64-94.
	Va	Valiant, L. G. (1975), Parallelism in comparison models, SIAM J. of Comput. .4, 348-355.
	V85	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]
	V90	U. Vishkin, Deterministic sampling—a new technique for fast pattern matching, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.170-180, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100235]

CITED BY 4

	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 , Krishna Palem, Non-standard stringology: algorithms and complexity, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.770-779, May 23-25, 1994, Montreal, Quebec, Canada
	Philip D. MacKenzie, Load balancing requires &OHgr;(log*n) expected time, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.94-99, September 1992, Orlando, Florida, United States