Non-standard stringology

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Non-standard stringology: algorithms and complexity

Full text

Pdf (1.11 MB)

Source

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

Montreal, Quebec, Canada

Pages: 770 - 779

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

S. Muthukrishnan	Courant Institute of Mathematical science, 251 Mercer Street, New York, NY
Krishna Palem	IBM Research Division, T. J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 37, Citation Count: 5

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/195058.195457 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.

	Ab86	K. Abrahamson. Time-space tradeoffs for branching programs constructed with those for straight line programs. 27th Ann #,ymp FOCS, 1986, 402-409.
	Ab87	Karl Abrahamson, Generalized string matching, SIAM Journal on Computing, v.16 n.6, p.1039-1051, December 1, 1987 [doi>10.1137/0216067]
	An87	I. Anderson. Combinatorics of Finite Sets, Oxford Science Publications, 1987.
	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]
	AF91	Amihood Amir , Martin Farach, Efficient 2-dimensional approximate matching of non-rectangular figures, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.212-223, January 28-30, 1991, San Francisco, California, United States
	AHU74	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	AHiU	J. D. Ullman , A. V. Aho , D. S. Hirschberg, Bounds on the Complexity of the Longest Common Subsequence Problem, Journal of the ACM (JACM), v.23 n.1, p.1-12, Jan. 1976 [doi>10.1145/321921.321922]
	AL88	Amihood Amir , Gad M. Landau, Fast parallel and serial multidimensional approximate array matching, Theoretical Computer Science, v.81 n.1, p.97-115, April 22, 1991 [doi>10.1016/0304-3975(91)90318-V]
	Ba78	T. J. Baker. A technique for extending rapid exact-match string matching to arrays of more than one dimension. SIAM J. Comput., Vol. 7, 1978, 533-541.
	Bi77	R. S. Bird. Two dimensional pattern matching. Informalion Processing Lel#ers, Vol. 6, No. 5, 1977, 168-170.
	Br93	D. Breslauer. Dictionary matching with unbounded alphabet-the uniform length case. Manuscript, 1993.
	BG91	Dany Breslauer , Zvi Galil, A lower bound for parallel string matching, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.439-443, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103465]
	C92	W. Chang. Private Communication.
	CC+93	R. Cole, M. Crochemore, Z. Galil, L. Gasieniec, R. Hariharan, S. Muthukrishnan, K. Park, and W. Rytter. Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions. Proc IEEE Symp. on FOCS, 1993.
	CH92	R.. Cole and R. Hariharan. On the exact complexity of string matching. Proc IEEE Ann Symp on FOCS, 1992, 600-609.
	CL90	W. Chang and E. Lawler. Approximate string matching in sublinear expected time. Proc IEEE Ann Symp on FOCS, 1990, 116-124.
	CP91	M. Crochemore and D. Perrin. Two-way pattern matching, journal of ACM, 38, 1991, 651- 675.
	DGM90	M. Dubiner, Z. Galil, and E. Magen. Faster tree pattern matching. Proc IEEE Ann Symp FOCS, 1990, 145-150.
	FP74	M. Fischer and M. Paterson. String Matching and other Products. SIAM-AMS Proceedings, Vol. 7, 113-125, 1974.
	Ga85	Z. G#lil. Open Problems in Strlngology. Combinatorial Algorithms on Words, A. Apostolico and Z. Galil Eds, Springer-Verlag Lecture Notes, 1985. 1-8.
	GG88	Z. Galil , R. Giancarlo, Data structures and algorithms for approximate string matching, Journal of Complexity, v.4 n.1, p.33-72, March 1988 [doi>10.1016/0885-064X(88)90008-8]
	GG91	Zvi Galil , Raffaele Giancarlo, On the exact complexity of string matching: lower bounds, SIAM Journal on Computing, v.20 n.6, p.1008-1020, Dec. 1991 [doi>10.1137/0220063]
	GG92	Zvi Galil , Raffaele Giancarlo, On the exact complexity of string matching: upper bounds, SIAM Journal on Computing, v.21 n.3, p.407-437, June 1992 [doi>10.1137/0221028]
	GP92	Z. Galil and K. Park. Truly alphabetindependent two dimensional matching. Proc. of 33rd Ann. IEEE Symp. FOCS, 1992, 247-256.
	GS83	Z. Galil and J. Seiferas. Time space optimal string matching. Journal Comput. Syst. Sci: 26(1983), 280-294.
	HO85	Christoph M. Hoffmann , Michael J. O'Donnell, Pattern Matching in Trees, Journal of the ACM (JACM), v.29 n.1, p.68-95, Jan. 1982 [doi>10.1145/322290.322295]
	Ka93	H. Karloff. Fast algorithms for approximately counting mismatches. Manuscript, 1993.
	Ko89	S.R. Kosaraju. Efficient tree pattern matching. Proc IEEE Ann. Symp. on FOCS, 1989, 178-183.
	KMP77	D.E. Knuth, J. Morris, V. Pratt. Fast pattern matching in strings. SIAM Journal on Computing, 6(1973), 323-350.
	KMR72	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]
	KP84	Brian W. Kernighan , Robert Pike , Rob Pike, The UNIX Programming Environment, Prentice Hall Professional Technical Reference, 1984
	KR87	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
	Lov	L. Lovasz. Communication complexity- a survey. Paths, Flows and VLSI Layout, Korte, Lovasz, Promel, Schrijver Eds., Springer-Verlag (1990), 235-266
	MR92	S. Muthukrishnan , H. Ramesh, String Matching Under a General Matching Relation, Proceedings of the 12th Conference on Foundations of Software Technology and Theoretical Computer Science, p.356-367, December 18-20, 1992
	W86	Ingo Wegener, The complexity of Boolean functions, John Wiley & Sons, Inc., New York, NY, 1987
	WC76	C. K. Wong , Ashok K. Chandra, Bounds for the String Editing Problem, Journal of the ACM (JACM), v.23 n.1, p.13-16, Jan. 1976 [doi>10.1145/321921.321923]
	WM92	Sun Wu , Udi Manber, Fast text searching: allowing errors, Communications of the ACM, v.35 n.10, p.83-91, Oct. 1992 [doi>10.1145/135239.135244]

CITED BY 5

	Adam Kalai, Efficient pattern-matching with don't cares, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.655-656, January 06-08, 2002, San Francisco, California
	Richard Cole , Ramesh Hariharan , Piotr Indyk, Tree pattern matching and subset matching in deterministic O(n log3 n)-time, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.245-254, January 17-19, 1999, Baltimore, Maryland, United States
	Vesa Halava , Tero Harju , Tomi Kärki, Relational codes of words, Theoretical Computer Science, v.389 n.1-2, p.237-249, December, 2007
	Minos N. Garofalakis , Yannis E. Ioannidis , Banu Özden, Resource Scheduling for Composite Multimedia Objects, Proceedings of the 24rd International Conference on Very Large Data Bases, p.74-85, August 24-27, 1998
	Martha L. Escobar-Molano , David A. Barrett, Resource scheduling with variable requirements over time, Journal of Scheduling, v.11 n.6, p.475-489, December 2008