{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:48:00Z","timestamp":1759063680953},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540404934"},{"type":"electronic","value":"9783540450610"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45061-0_72","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T15:54:04Z","timestamp":1184601244000},"page":"929-942","source":"Crossref","is-referenced-by-count":25,"title":["Function Matching: Algorithms, Applications, and a Lower Bound"],"prefix":"10.1007","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yonatan","family":"Aumann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard","family":"Cole","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moshe","family":"Lewenstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ely","family":"Porat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,18]]},"reference":[{"issue":"6","key":"72_CR1","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1137\/0216067","volume":"16","author":"K. Abrahamson","year":"1987","unstructured":"K. Abrahamson. Generalized string matching. SIAM J. Comp., 16(6):1039\u20131051, 1987.","journal-title":"SIAM J. Comp."},{"issue":"2","key":"72_CR2","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1137\/S0097539792226321","volume":"23","author":"A. Amir","year":"1994","unstructured":"A. Amir, G. Benson, and M. Farach. An alphabet independent approach to two dimensional pattern matching. SIAM J. Comp., 23(2):313\u2013323, 1994.","journal-title":"SIAM J. Comp."},{"key":"72_CR3","unstructured":"A. Amir, K.W. Church, and E. Dar. Separable attributes: a technique for solving the submatrices character count problem. In Proc. 13th ACM-SIAM Symp. on. Discrete Algorithms (SODA), pages 400\u2013401, 2002."},{"issue":"1","key":"72_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1995.1047","volume":"118","author":"A. Amir","year":"1995","unstructured":"A. Amir and M. Farach. Efficient 2-dimensional approximate matching of half-rectangular figures. Information and Computation, 118(1):1\u201311, April 1995.","journal-title":"Information and Computation"},{"key":"72_CR5","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0020-0190(94)90086-8","volume":"49","author":"A. Amir","year":"1994","unstructured":"A. Amir, M. Farach, and S. Muthukrishnan. Alphabet dependence in parameterized matching. Information Processing Letters, 49:111\u2013115, 1994.","journal-title":"Information Processing Letters"},{"issue":"4","key":"72_CR6","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/BF01215882","volume":"1","author":"G.P. Babu","year":"1995","unstructured":"G.P. Babu, B.M. Mehtre, and M.S. Kankanhalli. Color indexing for efficient image retrieval. Multimedia Tools and Applications, 1(4):327\u2013348, Nov. 1995.","journal-title":"Multimedia Tools and Applications"},{"key":"72_CR7","doi-asserted-by":"crossref","unstructured":"B.S. Baker. A theory of parameterized pattern matching: algorithms and applications. In Proc. 25th Annual ACM Symposium on the Theory of Computation, pages 71\u201380, 1993.","DOI":"10.1145\/167088.167115"},{"key":"72_CR8","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1126\/science.1853201","volume":"253","author":"J.H. Bowie","year":"1991","unstructured":"J.H. Bowie, R. Luthy, and D. Eisenberg. A method to identify protein sequences that fold into a known three-dimensional structure. Science, (253):164\u2013176, 1991.","journal-title":"Science"},{"key":"72_CR9","doi-asserted-by":"crossref","unstructured":"R. Cole and R. Hariharan. Verifying candidate matches in sparse and wildcard matching. In Proc. 34st Annual Symposium on the Theory of Computing (STOC), pages 592\u2013601, 2002.","DOI":"10.1145\/509907.509992"},{"key":"72_CR10","unstructured":"M. Crochemore and W. Rytter. Text Algorithms. Oxford University Press, 1994."},{"key":"72_CR11","unstructured":"M.J. Fischer and M.S. Paterson. String matching and other products. Complexity. of Computation, R.M. Karp (editor), SIAM-AMS Proceedings, 7:113\u2013125, 1974."},{"key":"72_CR12","doi-asserted-by":"crossref","unstructured":"W.C. Kreahling and C. Norris. Profile assisted register allocation. In Proc. ACM. Symp. on Applied Computing (SAC), pages 774\u2013781, 2000.","DOI":"10.1145\/338407.338562"},{"issue":"3","key":"72_CR13","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1145\/353926.353929","volume":"22","author":"G.-Y. Lueh","year":"2000","unstructured":"G-Y. Lueh, T. Gross, and A-R. Adl-Tabatabai. Fusion-based register allocation. ACM Transactions on Programming Languages and Sustems (TOPLAS), 22(3):431\u2013470, 2000.","journal-title":"ACM Transactions on Programming Languages and Sustems (TOPLAS)"},{"key":"72_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4684-6831-1","volume-title":"The Protein Folding Problem and Tertiary. Structure Prediction","author":"K. Merz Jr.","year":"1994","unstructured":"Jr. K. Merz and S.M. La Grand. The Protein Folding Problem and Tertiary. Structure Prediction. Birkhauser, Boston, 1994."},{"key":"72_CR15","doi-asserted-by":"crossref","unstructured":"S. Muthukrishnan and K. Palem. Non-standard stringology: Algorithms and complexity. In Proc. 26th Annual Symposium on the Theory of Computing, pages 770\u2013779, 1994.","DOI":"10.1145\/195058.195457"},{"issue":"1","key":"72_CR16","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/BF00130487","volume":"7","author":"M. Swain","year":"1991","unstructured":"M. Swain and D. Ballard. Color indexing. International Journal of Computer. Vision, 7(1):11\u201332, 1991.","journal-title":"International Journal of Computer. Vision"},{"key":"72_CR17","unstructured":"J. Yadgari, Amihood Amir, and Ron Unger Genetic algorithms for protein threading. In J. Glasgow, T. Littlejohn, F. Major, R. Lathrop, D. Sankoff, and C. Sensen, editors, Proc. 6th Int\u2019l Conference on Intellingent Systems for Molecular Biology. (ISMB 98), pages 193\u2013202. AAAI, AAAI Press, 1998."},{"key":"72_CR18","doi-asserted-by":"crossref","unstructured":"A.C.C. Yao. Some complexity questions related to distributed computing. In Proc. 11th Annual Symposium on the Theory of Computing (STOC), pages 209\u2013213, 1979.","DOI":"10.1145\/800135.804414"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45061-0_72","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T03:15:17Z","timestamp":1556680517000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45061-0_72"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540404934","9783540450610"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-45061-0_72","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}