Work-time-optimal parallel algorithms for string problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Work-time-optimal parallel algorithms for string problems

Full text

Pdf (975 KB)

Source

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

Las Vegas, Nevada, United States

Pages: 713 - 722

Year of Publication: 1995

ISBN:0-89791-718-9

Authors

Artur Czumaj	Heinz Nixdorf Institute, University of Paderborn, D-33095, Paderborn, Germany
Zvi Galil	Department of Computer Science, Columbia University and Tel Aviv University
Leszek Gąsieniec	Warsaw University
Kunsoo Park	Department of Computer Engineering, Seoul National University, Seoul 151-742, Korea
Wojciech Plandowski	Instytut Informatyki, Uniwersytet Warszawski, 02-097, Warszawa, Poland

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 26, Citation Count: 2

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/225058.225289 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	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
	2	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 [doi>10.1145/165231.165242]
	3	A. Apostolic and D. 13reslauer, An optimal ()(log log 7L) time parallel algorithm for detecting all squarm in a string, Manuscript, 1993.
	4	Alberto Apostolico , Dany Breslauer , Zvi Galil, Optimal Parallel Algorithms for Periods, Palindromes and Squares (Extended Abstract), Proceedings of the 19th International Colloquium on Automata, Languages and Programming, p.296-307, July 13-17, 1992
	5	Alberto Apostolico , Dany Breslauer , Zvi Galil, Parallel Detection of all Palindromes in a String, Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science, p.497-506, February 24-26, 1994
	6	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]
	7	Danny Breslauer , Zvi Galil, A lower bound for parallel string matching, SIAM Journal on Computing, v.21 n.5, p.856-862, Oct. 1992 [doi>10.1137/0221050]
	8	D. Breslauer and L. Gqsieniec, Efficient String Matching on ~oded Texts, Manuscript, 1994.
	9	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]
	10	Bogdan S. Chlebus , Leszek Gasieniec, Optimal Pattern Matching on Meshes, Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science, p.213-224, February 24-26, 1994
	11	Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
	12	R. C;ole, M. Crochemore, Z. Galil, L. Gasieniec, R. Harihman, S. Muthukrishnan, K. Park and W. Rytter, optimally fast parallel algorithms for pre-processing and pattern matching in one and two dinlensions, F)roc, Wth IEEE ,Symp, Found. (kn~-1) u ter ,Scien ce, 1993, 248-258.
	13	R ("!ole Z. Galil, R. Hariharan, S. Muthukrish-nan and K. Park, Parallel two dimensional witness computation, Manuscript, 1994.
	14	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]
	15	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]
	16	Z. Galil and K. Park, Alphahet-independent two-dirnensional pattern matching, Manuscript, 1992.
	17	Z. (ialil and K. Park, Parallel two-dimensional pat-tern matching, Manuscript, 1993.
	18	Leszek Gasieniec , Kunsoo Park, Work-Time Optimal Parallel Prefix Matching (Extended Abstract), Proceedings of the Second Annual European Symposium on Algorithms, p.471-482, September 26-28, 1994
	19	H. Gazit, Optimal EREW parallel algorithms for connectivity, ear decomposition and st-numl>eriug of planar graphs, Proc. 5tL International} Parallel Processing Symposium, 1991, 84-91.
	20	Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
	21	Marek Karpinski , Wojciech Rytter, An Alphabet-Independent Optimal Parallel Search for Three Dimensional Pattern, Proceedings of the 5th Annual Symposium on Combinatorial Pattern Matching, p.125-135, June 05-08, 1994
	22	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	23	Michael G. Main , Richard J. Lorentz, An O(n log n) algorithm for finding all repetitions in a string, Journal of Algorithms, v.5 n.3, p.422-432, Sept. 1984 [doi>10.1016/0196-6774(84)90021-X]
	24	David Nassimi , Sartaj Sahni, Parallel permutation and sorting algorithms and a new generalized connection network, Journal of the ACM (JACM), v.29 n.3, p.642-667, July 1982 [doi>10.1145/322326.322329]
	25	F. Preparata, New parallel sorting schemes, IEEE Transactions OJI ~~omputers, 27(7) (1978), 669-673.
	26	Y. Shiloach and {J. Vishliin, Finding the maxi-mum, merging, and sorting in a parallel corripu-tation model, J. Algorithms 2 (1981), 88-102.
	27	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]
	28	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 2

	Zvi Galil, A constant-time optimal parallel string-matching algorithm, Journal of the ACM (JACM), v.42 n.4, p.908-918, July 1995
	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