Deterministic sampling—a new technique for fast pattern matching

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.

	A-78	Adleman, L., Two theorems on random polynomial time, Proc. 19 IEEE Symp. on Foundations of Computer Science, 1978, 75-83.
	A-89	Alon, N., personal communication.
	BG-88	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]
	BR-89	Berger, B. and Rompel, J., Simulating (log2n)-wise independence in NC, Prec. 30th IEEE Symp. on Foundations of Computer Science, 1989.
	BV-89	Berkman, O. and Vishkin, U., Recursive *-tree parallel data-structure, Proc. 30th IEEE Syrup. on Foundations of Computer Science, 1989,
	BV-90	Omer Berkman , Uzi Vishkin, On parallel integer merging, University of Maryland at College Park, College Park, MD, 1990
	BM-77	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]
	CV-86	R Cole , U Vishkin, Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.206-219, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12151]
	CV-89	Richard Cole , Uzi Vishkin, Faster optimal parallel prefix sums and list ranking, Information and Computation, v.81 n.3, p.334-352, June 1989 [doi>10.1016/0890-5401(89)90036-9]
	FRW-88	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]
	Ga-85a	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]
	Ga-85b	Galil, Z., Open problems in stringology, in Combinatorial Algorithms on Words, Springer-Verlag, ed. A. Apostolico and Z. Galil, 1985, 1-8.
	Gi-59	Gill, A., Minimum-scan pattern recognition, IRE Trans. on Information Theory IT-5 (1959), 52-58.
	GS-83	Galil, Z. and Seiferas, J.I., Time-space-optimal string matching, J. Computer and Systems Sciences 26 (1983), 280- 294.
	KMP-77	Knuth, D.E., Morris, J.H. and Pratt, V.R., Fast pattern matching in strings, SIAM J. Comput. 6 (1977), 322-350.
	KR-87	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
	LF-80	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]
	LS-62	Lyndon, R.C. and Schutzenberger, M.P., The equation am=bncp in a free group, Michigan Math. J. 9 (1962), 289- 298.
	Lu-88	Luby, M., Removing randomness in parallel computation without a processor penalty, Prec. 29th IEEE Symp. on Foundations of Computer Science, 1988, 162-173.
	MNN-89	Rajeev Motwani , Joseph Seffi Naor , Moni Naor, The probabilistic method yields deterministic parallel algorithms, Proceedings of the 30th IEEE symposium on Foundations of computer science, p.478-516, December 1994, Research Triangle Park, North Carolina, United States
	Ra-76	Rabin, M.O., Probabilistic algorithms, Algorithms and Complexity, J.F. Traub, Editor, Academic Press, 1976, 21-39.
	Ri-77	Rivest, R.L., On the worst-case behavior of stringsearching algorithms, SlAM J. Comput. 6 (1977), 669-674.
	Se-89	Sen, S., Finding an approximate-median with highprobability in constant time, manuscript, 1989.
	St-88	Stout, Q., Constant-time geometry on PRAMs, Proc. Int. Conf. on Parallel Processing, 1988.
	SV-81	Shiloach, Y. and Vishkin, U., Finding the maximum, merging and sorting in a parallel model of computation, J. Algorithms 2 (1981), 88-102
	U-85	Ukkonen, E., Finding approximate patterns in strings, J. Algorithms 6 (1985), 132-137.
	Va-75	Valiant, L.G., Parallelism in comparisons models, SlAM J. Comput. 4 (1975), 348-355.
	Vi-85	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]
	W-73	Weiner, P., Linear pattern matching algorithm, Proc. 14th IEEE Symp. on Switching and Automata Theory, 1973, 1- 11.