{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T11:20:40Z","timestamp":1710328840286},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1995,7,1]],"date-time":"1995-07-01T00:00:00Z","timestamp":804556800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1995,7]]},"DOI":"10.1007\/bf01300375","type":"journal-article","created":{"date-parts":[[2005,3,25]],"date-time":"2005-03-25T09:45:54Z","timestamp":1111743954000},"page":"85-121","source":"Crossref","is-referenced-by-count":7,"title":["Approximate regular expression pattern matching with concave gap penalties"],"prefix":"10.1007","volume":"14","author":[{"given":"J. R.","family":"Knight","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"E. W.","family":"Myers","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF01840359","volume":"2","author":"A. Aggarwal","year":"1987","unstructured":"Aggarwal, A., Klawe, M., Moran, S., Shor, P., and Wilber, R. Geometric Applications of a Matrix-Searching Algorithm.Algorithmica,2 (1987), 195?208.","journal-title":"Algorithmica"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/390013.808479","volume":"5","author":"F. E. Allen","year":"1970","unstructured":"Allen, F. E. Control Flow Analysis.SIGPLAN Notices,5 (1970), 1?19.","journal-title":"SIGPLAN Notices"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0196-6774(90)90031-9","volume":"11","author":"D. Eppstein","year":"1990","unstructured":"Eppstein, D. Sequence Comparison with Mixed Convex and Concave Costs.J. Algorithms,11 (1990), 85?101.","journal-title":"J. Algorithms"},{"issue":"3","key":"CR4","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1145\/146637.146656","volume":"39","author":"D. Eppstein","year":"1992","unstructured":"Eppstein, D., Galil, Z., Giancarlo, R., and Italiano, G. Sparse Dynamic Programming II: Convex and Concave Cost Functions.J. Assoc. Comput. Mach. 39(3) (1992), 546?567.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0304-3975(89)90101-1","volume":"64","author":"Z. Galil","year":"1989","unstructured":"Galil, Z., and Giancarlo, R. Speeding Up Dynamic Programming with Applications to Molecular Biology.Theoret. Comput. Sci.,64 (1989), 107?118.","journal-title":"Theoret. Comput. Sci."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0020-0190(90)90215-J","volume":"33","author":"Z. Galil","year":"1989\/90","unstructured":"Galil, Z., and Park, K. A Linear-Time Algorithm for Concave One-Dimensional Dynamic Programming.Inform. Process. Lett.,33 (1989\/90), 309?311.","journal-title":"Inform. Process. Lett."},{"issue":"4","key":"CR7","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1137\/0204044","volume":"4","author":"M. S. Hecht","year":"1975","unstructured":"Hecht, M. S., and Ullman, J. D. A. Simple Algorithm for Global Dataflow Analysis Programs.SIAM J. Comput.,4(4) (1975), 519?532.","journal-title":"SIAM J. Comput."},{"issue":"4","key":"CR8","doi-asserted-by":"crossref","first-page":"628","DOI":"10.1137\/0216043","volume":"16","author":"D. S. Hirschberg","year":"1987","unstructured":"Hirschberg, D. S., and Larmore, L. L. The Least Weight Subsequence Problem.SIAM J. Comput.,16(4) (1987), 628?638.","journal-title":"SIAM J. Comput."},{"key":"CR9","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. E. Hopcroft","year":"1979","unstructured":"Hopcroft, J. E., and Ullman, J. D.Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA (1979), Chapter 2."},{"key":"CR10","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1137\/0403009","volume":"3","author":"M. Klawe","year":"1990","unstructured":"Klawe, M., and Kleitman, D. An Almost Linear Algorithm for Generalized Matrix Searching.SIAM J. Discrete Math.,3 (1990), 81?97.","journal-title":"SIAM J. Discrete Math."},{"key":"CR11","first-page":"463","volume-title":"Sorting and Searching: The Art of Computer Programming, Vol. 3.","author":"D. Knuth","year":"1973","unstructured":"Knuth, D.Sorting and Searching: The Art of Computer Programming, Vol. 3. Addison-Wesley, Reading, MA, 1973, pp. 463?468."},{"issue":"2","key":"CR12","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF02459948","volume":"50","author":"W. Miller","year":"1988","unstructured":"Miller, W., and Myers, E. W. Sequence Comparison with Concave Weighting Functions.Bull. Math. Biol.,50(2) (1988), 97?120.","journal-title":"Bull. Math. Biol."},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"Myers, E. W. Efficient Applicative Data Types.Proc. 11th Symp. on the Principles of Programming Languages, 1984, pp. 66?75.","DOI":"10.1145\/800017.800517"},{"issue":"1","key":"CR14","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/BF02458834","volume":"51","author":"E. W. Myers","year":"1989","unstructured":"Myers, E. W., and Miller, W. Approximate Matching of Regular Expressions.Bull. Math. Biol.,51(1) (1989), 5?37.","journal-title":"Bull. Math. Biol."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"S. B. Needleman","year":"1970","unstructured":"Needleman, S. B., and Wunsch, C. D. A. General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins.J. Molecular Biol.,48 (1970), 443?453.","journal-title":"J. Molecular Biol."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1073\/pnas.69.1.4","volume":"69","author":"D. Sankoff","year":"1972","unstructured":"Sankoff, D. Matching Sequences Under Deletion\/Insertion Constraints.Proc. Nat. Acad. Sci. U.S.A.,69 (1972), 4?6.","journal-title":"Proc. Nat. Acad. Sci. U.S.A."},{"issue":"3","key":"CR17","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D. D. Sleator","year":"1985","unstructured":"Sleator, D. D., and Tarjan, R. E. Self-Adjusting Binary Search Trees.J. Assoc. Comput. Mach.,32(3) (1985), 652?686.","journal-title":"J. Assoc. Comput. Mach."},{"issue":"1","key":"CR18","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R. A. Wagner","year":"1974","unstructured":"Wagner, R. A., and Fischer, M. J. The String-to-String Correction Problem.J. Assoc. Comput. Mach.,21(1) (1974), 168?173.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1007\/BF02459498","volume":"46","author":"M. S. Waterman","year":"1984","unstructured":"Waterman, M. S. General Methods of Sequence Comparison.Bull. Math. Biol.,46 (1984), 473?501.","journal-title":"Bull. Math. Biol."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1016\/0196-6774(88)90032-6","volume":"9","author":"R. Wilber","year":"1988","unstructured":"Wilber, R. The Concave Least-Weight Subsequence Problem Revisited.J. Algorithms,9 (1988), 418?425.","journal-title":"J. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01300375.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01300375\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01300375","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T18:08:19Z","timestamp":1556647699000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01300375"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,7]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1995,7]]}},"alternative-id":["BF01300375"],"URL":"https:\/\/doi.org\/10.1007\/bf01300375","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,7]]}}}