{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T09:40:28Z","timestamp":1742636428881},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,12,28]],"date-time":"2012-12-28T00:00:00Z","timestamp":1356652800000},"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":[[2014,6]]},"DOI":"10.1007\/s00453-012-9734-3","type":"journal-article","created":{"date-parts":[[2012,12,27]],"date-time":"2012-12-27T10:39:18Z","timestamp":1356604758000},"page":"294-314","source":"Crossref","is-referenced-by-count":30,"title":["Necklaces, Convolutions, and X+Y"],"prefix":"10.1007","volume":"69","author":[{"given":"David","family":"Bremner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Timothy M.","family":"Chan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik D.","family":"Demaine","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeff","family":"Erickson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ferran","family":"Hurtado","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Iacono","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Langerman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mihai","family":"P\u01cetra\u015fcu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Perouz","family":"Taslakian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,12,28]]},"reference":[{"issue":"3","key":"9734_CR1","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1162\/comj.2006.30.3.67","volume":"30","author":"G. Aloupis","year":"2006","unstructured":"Aloupis, G., Fevens, T., Langerman, S., Matsui, T., Mesa, A., Nu\u00f1ez, Y., Rappaport, D., Toussaint,\u00a0G.: Algorithms for computing geometric measures of melodic similarity. J. Comput. Music 30(3), 67\u201376 (2006)","journal-title":"J. Comput. Music"},{"issue":"3","key":"9734_CR2","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1142\/S0219876208001583","volume":"5","author":"Y.J.P. Ardila","year":"2008","unstructured":"Ardila, Y.J.P., Clifford, R., Iliopoulos, C.S., Landau, G.M., Mohamed, M.: Necklace swap problem for rhythmic similarity measures. Int. J. Comput. Methods 5(3), 351\u2013363 (2008)","journal-title":"Int. J. Comput. Methods"},{"issue":"4","key":"9734_CR3","doi-asserted-by":"crossref","first-page":"584","DOI":"10.1007\/s00453-007-9036-3","volume":"50","author":"I. Baran","year":"2008","unstructured":"Baran, I., Demaine, E.D., P\u01cetra\u015fcu, M.: Subquadratic algorithms for 3SUM. Algorithmica 50(4), 584\u2013596 (2008). Special issue of selected papers from the 9th Workshop on Algorithms and Data Structures, 2005","journal-title":"Algorithmica"},{"issue":"3","key":"9734_CR4","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1137\/0110042","volume":"10","author":"R. Bellman","year":"1962","unstructured":"Bellman, R., Karush, W.: Mathematical programming and the maximum transform. J. Soc. Ind. Appl. Math. 10(3), 550\u2013567 (1962)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"9734_CR5","series-title":"MSRI Publications","volume-title":"Algorithmic Number Theory","author":"D.J. Bernstein","year":"2008","unstructured":"Bernstein, D.J.: Fast multiplication and its applications. In: Buhler, J., Stevenhagen, P. (eds.) Algorithmic Number Theory. MSRI Publications, vol. 44 (2008)"},{"issue":"4","key":"9734_CR6","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1973","unstructured":"Blum, M., Floyd, R.W., Pratt, V., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. J. Comput. Syst. Sci. 7(4), 448\u2013461 (1973)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9734_CR7","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0167-6377(94)90048-5","volume":"15","author":"M. Bussieck","year":"1994","unstructured":"Bussieck, M., Hassler, H., Woeginger, G.J., Zimmermann, U.T.: Fast algorithms for the maximum convolution problem. Oper. Res. Lett. 15(3), 133\u2013141 (1994)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"9734_CR8","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1007\/s00224-005-1239-x","volume":"39","author":"J. Cardinal","year":"2006","unstructured":"Cardinal, J., Kremer, S., Langerman, S.: Juggling with pattern matching. Theory Comput. Syst. 39(3), 425\u2013437 (2006)","journal-title":"Theory Comput. Syst."},{"key":"9734_CR9","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1007\/s00453-007-9062-1","volume":"50","author":"T.M. Chan","year":"2008","unstructured":"Chan, T.M.: All-pairs shortest paths with real weights in O(n 3\/logn) time. Algorithmica 50, 236\u2013243 (2008)","journal-title":"Algorithmica"},{"key":"9734_CR10","doi-asserted-by":"crossref","first-page":"2075","DOI":"10.1137\/08071990X","volume":"39","author":"T.M. Chan","year":"2010","unstructured":"Chan, T.M.: More algorithms for all-pairs shortest paths in weighted graphs. SIAM J. Comput. 39, 2075\u20132089 (2010)","journal-title":"SIAM J. Comput."},{"key":"9734_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/978-3-540-73437-6_9","volume-title":"Combinatorial Pattern Matching","author":"P. Clifford","year":"2007","unstructured":"Clifford, P., Clifford, R.: Self-normalised distance with don\u2019t cares. In: Ma, B., Zhang, K. (eds.) Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 4580, pp. 63\u201370. Springer, Berlin (2007)"},{"issue":"2","key":"9734_CR12","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.ipl.2006.08.002","volume":"101","author":"P. Clifford","year":"2007","unstructured":"Clifford, P., Clifford, R.: Simple deterministic wildcard matching. Inf. Process. Lett. 101(2), 53\u201354 (2007)","journal-title":"Inf. Process. Lett."},{"key":"9734_CR13","unstructured":"Clifford, P., Clifford, R., Iliopoulos, C.: Fourier transform methods for \u03b4 and (\u03b4,\u03b3) matching and other measures of string similarity. Tech. Rep. TR-04-09, King\u2019s College, London (2004)"},{"key":"9734_CR14","series-title":"Lecture Notes in Computer Science","first-page":"71","volume-title":"Combinatorial Pattern Matching","author":"P. Clifford","year":"2005","unstructured":"Clifford, P., Clifford, R., Iliopoulos, C.: Faster algorithms for \u03b4, \u03b3-matching and related problems. In: Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 3537, pp. 71\u201390. Springer, Berlin (2005)"},{"key":"9734_CR15","first-page":"379","volume-title":"Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science","author":"H. Cohn","year":"2005","unstructured":"Cohn, H., Kleinberg, R., Szegedy, B., Umans, C.: Group-theoretic algorithms for matrix multiplication. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pp.\u00a0379\u2013388 (2005)"},{"issue":"4","key":"9734_CR16","doi-asserted-by":"crossref","first-page":"979","DOI":"10.1089\/cmb.2006.13.979","volume":"13","author":"J. Colannino","year":"2006","unstructured":"Colannino, J., Damian, M., Hurtado, F., Iacono, J., Meijer, H., Ramaswami, S., Toussaint, G.: An O(nlogn)-time algorithm for the restriction scaffold assignment. J. Comput. Biol. 13(4), 979\u2013989 (2006)","journal-title":"J. Comput. Biol."},{"key":"9734_CR17","first-page":"592","volume-title":"Proceedings of the 34th Annual ACM Symposium on Theory of Computing","author":"R. Cole","year":"2002","unstructured":"Cole, R., Hariharan, R.: Verifying candidate matches in sparse and wildcard matching. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, Montr\u00e9al, Canada, pp. 592\u2013601 (2002)"},{"key":"9734_CR18","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1090\/S0025-5718-1965-0178586-1","volume":"19","author":"J.W. Cooley","year":"1965","unstructured":"Cooley, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19, 297\u2013301 (1965)","journal-title":"Math. Comput."},{"key":"9734_CR19","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"9734_CR20","volume-title":"The Open Problems Project","author":"E.D. Demaine","year":"2006","unstructured":"Demaine, E.D., Mitchell, J.S.B., O\u2019Rourke, J.: Problem 41: Sorting X+Y (pairwise sums). In: The Open Problems Project (2006). http:\/\/cs.smith.edu\/~orourke\/TOPP\/P41.html"},{"key":"9734_CR21","volume-title":"Proceedings of the 18th Canadian Conference on Computational Geometry","author":"E.D. Demaine","year":"2006","unstructured":"Demaine, E.D., O\u2019Rourke, J.: Open problems from CCCG 2005. Proceedings of the 18th Canadian Conference on Computational Geometry, Kingston, Canada (2006)"},{"key":"9734_CR22","first-page":"61","volume-title":"Proceedings of BRIDGES: Mathematical Connections in Art, Music, and Science","author":"J.M. D\u00edaz-B\u00e1\u00f1ez","year":"2004","unstructured":"D\u00edaz-B\u00e1\u00f1ez, J.M., Farigu, G., G\u00f3mez, F., Rappaport, D., Toussaint, G.T.: El comp\u00e1s flamenco: a\u00a0phylogenetic analysis. In: Proceedings of BRIDGES: Mathematical Connections in Art, Music, and Science, Winfield, KS, pp. 61\u201370 (2004)"},{"key":"9734_CR23","unstructured":"Erickson, J.: Lower bounds for linear satisfiability problems. Chic. J. Theor. Comput. Sci. 8 (1999)"},{"key":"9734_CR24","unstructured":"Felzenszwalb, P.F., Huttenlocher, D.P.: Distance transforms of sampled functions. Tech. Rep. TR2004-1963, Faculty of Computing and Information Science, Cornell University (2004)"},{"key":"9734_CR25","series-title":"SIAM-AMS Proceedings","first-page":"113","volume-title":"Complexity of computation","author":"M.J. Fischer","year":"1974","unstructured":"Fischer, M.J., Paterson, M.S.: String-matching and other products. In: Complexity of computation. SIAM-AMS Proceedings, vol. VII, pp. 113\u2013125. Am. Math. Soc., New York (1974)"},{"issue":"2","key":"9734_CR26","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0022-0000(82)90048-4","volume":"24","author":"G.N. Frederickson","year":"1982","unstructured":"Frederickson, G.N., Johnson, D.B.: The complexity of selection and ranking in X+Y and matrices with sorted columns. J. Comput. Syst. Sci. 24(2), 197\u2013208 (1982)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9734_CR27","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/0304-3975(76)90078-5","volume":"1","author":"M.L. Fredman","year":"1976","unstructured":"Fredman, M.L.: How good is the information theory bound in sorting? Theor. Comput. Sci. 1(4), 355\u2013361 (1976)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9734_CR28","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1137\/0205006","volume":"5","author":"M.L. Fredman","year":"1976","unstructured":"Fredman, M.L.: New bounds on the complexity of the shortest path problem. SIAM J. Comput. 5(1), 83\u201389 (1976)","journal-title":"SIAM J. Comput."},{"key":"9734_CR29","volume-title":"Werke","author":"C.F. Gauss","year":"1866","unstructured":"Gauss, C.F.: Werke, vol. 3. K\u00f6niglichen Gesellschaft der Wissenschaften, G\u00f6ttingen (1866)"},{"issue":"3","key":"9734_CR30","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF00348431","volume":"34","author":"M.T. Heideman","year":"1985","unstructured":"Heideman, M.T., Johnson, D.H., Burrus, C.S.: Gauss and the history of the fast Fourier transform. Arch. Hist. Exact Sci. 34(3), 265\u2013277 (1985)","journal-title":"Arch. Hist. Exact Sci."},{"key":"9734_CR31","first-page":"166","volume-title":"Proceedings of the 39th Annual Symposium on Foundations of Computer Science","author":"P. Indyk","year":"1998","unstructured":"Indyk, P.: Faster algorithms for string matching problems: Matching the convolution bound. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, pp.\u00a0166\u2013173 (1998)"},{"key":"9734_CR32","first-page":"655","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"A. Kalai","year":"2002","unstructured":"Kalai, A.: Efficient pattern-matching with don\u2019t cares. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, pp. 655\u2013656 (2002)"},{"key":"9734_CR33","first-page":"289","volume-title":"Nonlinear Image Processing","author":"P. Maragos","year":"2000","unstructured":"Maragos, P.: Differential morphology. In: Mitra, S., Sicuranza, G. (eds.) Nonlinear Image Processing, pp. 289\u2013329. Academic Press, New York (2000)"},{"key":"9734_CR34","first-page":"109","volume":"49","author":"J.J. Moreau","year":"1970","unstructured":"Moreau, J.J.: Inf-convolution, sous-additivit\u00e9, convexit\u00e9 des fonctions num\u00e9riques. J. Math. Pures Appl., Neuv. S\u00e9r. 49, 109\u2013154 (1970)","journal-title":"J. Math. Pures Appl., Neuv. S\u00e9r."},{"key":"9734_CR35","series-title":"Princeton Mathematical Series","doi-asserted-by":"crossref","DOI":"10.1515\/9781400873173","volume-title":"Convex Analysis","author":"R.T. Rockafellar","year":"1970","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton Mathematical Series. Princeton University Press, Princeton (1970)"},{"issue":"2","key":"9734_CR36","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1016\/S0022-0000(76)80029-3","volume":"13","author":"A. Sch\u00f6nhage","year":"1976","unstructured":"Sch\u00f6nhage, A., Paterson, M., Pippenger, N.: Finding the median. J. Comput. Syst. Sci. 13(2), 184\u2013199 (1976)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"9734_CR37","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/0020-0190(94)00201-9","volume":"53","author":"W.L. Steiger","year":"1995","unstructured":"Steiger, W.L., Streinu, I.: A pseudo-algorithmic separation of lines from pseudo-lines. Inf. Process. Lett. 53(5), 295\u2013299 (1995)","journal-title":"Inf. Process. Lett."},{"key":"9734_CR38","first-page":"58","volume":"352","author":"T. Str\u00f6mberg","year":"1996","unstructured":"Str\u00f6mberg, T.: The operation of infimal convolution. Diss. Math. 352, 58 (1996)","journal-title":"Diss. Math."},{"key":"9734_CR39","series-title":"Lecture Notes in Computer Science","first-page":"198","volume-title":"Revised Papers from the Japan Conference on Discrete and Computational Geometry","author":"G. Toussaint","year":"2004","unstructured":"Toussaint, G.: The geometry of musical rhythm. In: Revised Papers from the Japan Conference on Discrete and Computational Geometry, Tokyo, Japan. Lecture Notes in Computer Science, vol. 3742, pp. 198\u2013212 (2004)"},{"key":"9734_CR40","first-page":"242","volume-title":"Proceedings of the 5th International Conference on Music Information Retrieval","author":"G.T. Toussaint","year":"2004","unstructured":"Toussaint, G.T.: A comparison of rhythmic similarity measures. In: Proceedings of the 5th International Conference on Music Information Retrieval, Barcelona, Spain, pp. 242\u2013245 (2004) A longer version appears as Technical Report SOCS-TR-2004.6, School of Computer Science, McGill University, August 2004"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9734-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9734-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9734-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:11Z","timestamp":1559123111000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9734-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12,28]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,6]]}},"alternative-id":["9734"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9734-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12,28]]}}}