{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T08:48:16Z","timestamp":1780822096928,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642385353","type":"print"},{"value":"9783642385360","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38536-0_21","type":"book-chapter","created":{"date-parts":[[2013,6,2]],"date-time":"2013-06-02T21:03:04Z","timestamp":1370206984000},"page":"235-245","source":"Crossref","is-referenced-by-count":7,"title":["On Recognizing Words That Are Squares for the Shuffle Product"],"prefix":"10.1007","author":[{"given":"Romeo","family":"Rizzi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"St\u00e9phane","family":"Vialette","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"21_CR1","unstructured":"Allauzen, C.: Calcul efficace du shuffle de k mots. Tech. rep., Institut Gaspard Monge, Universit Marne-la-Vall\u00e9 (2000)"},{"key":"21_CR2","unstructured":"Aoki, H., Uehara, R., Yamazaki, K.: Expected length of longest common subsequences of two biased random strings and its application. Tech. Rep. 1185, RIMS Kokyuroku (2001)"},{"key":"21_CR3","unstructured":"Buss, S., Soltys, M.: Unshuffling a square is NP-hard (2012) (submitted)"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Choffrut, C., Karhum\u00e4ki, J.: Combinatorics of Words. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages. Springer (1997)","DOI":"10.1007\/978-3-642-59136-5_6"},{"key":"21_CR5","unstructured":"Iwama, K.: Personal communication (2012)"},{"issue":"3","key":"21_CR6","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/0022-0000(84)90018-7","volume":"28","author":"M.K. Warmutht","year":"1984","unstructured":"Warmutht, M.K., Haussler, D.: On the complexity of iterated shuffle. Journal of Computer and System Sciences\u00a028(3), 345\u2013358 (1984)","journal-title":"Journal of Computer and System Sciences"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Springer (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"21_CR8","first-page":"263","volume":"13","author":"C. Erdong","year":"1983","unstructured":"Erdong, C., Linji, Y., Hao, Y.: Improved algorithms for 2-interval pattern problem. Journal of Combinatorial Optimization\u00a013, 263\u2013275 (1983)","journal-title":"Journal of Combinatorial Optimization"},{"key":"21_CR9","doi-asserted-by":"crossref","unstructured":"Iwama, K.: Unique decomposability of shuffled strings: A formal treatment of asynchronous time-multiplexed communication. In: Proc. 15th Annual ACM Symposium on Theory of Computing (STOC), Boston, Massachusetts, USA, pp. 374\u2013381. ACM (1983)","DOI":"10.1145\/800061.808768"},{"key":"21_CR10","unstructured":"Erickson, J.: How hard is unshuffling a string? Theoretical Computer Science, \n                    \n                      http:\/\/cstheory.stackexchange.com\/q\/34\n                    \n                    \n                   (version: 2010-12-01)"},{"issue":"1-3","key":"21_CR11","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0166-218X(98)00074-2","volume":"88","author":"J.D. Kececioglu","year":"1998","unstructured":"Kececioglu, J.D., Gusfield, D.: Reconstructing a history of recombinations from a set of sequences. Discrete Applied Mathematics\u00a088(1-3), 239\u2013260 (1998)","journal-title":"Discrete Applied Mathematics"},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"Kimura, T.: An algebraic system for process structuring and interprocess communication. In: Chandra, A., Wotschke, D., Friedman, E., Harrison, M.A. (eds.) Proc. 8th Annual ACM Symposium on Theory of Computing (STOC), Hershey, Pennsylvania, USA, pp. 92\u2013100. ACM (1976)","DOI":"10.1145\/800113.803636"},{"issue":"1","key":"21_CR13","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/0020-0190(82)90138-7","volume":"14","author":"J. Leeuwen van","year":"1982","unstructured":"van Leeuwen, J., Nivat, M.: Efficient recognition of rational relations. Information Processing Letters\u00a014(1), 34\u201338 (1982)","journal-title":"Information Processing Letters"},{"issue":"24-25","key":"21_CR14","doi-asserted-by":"publisher","first-page":"2410","DOI":"10.1016\/j.tcs.2009.02.033","volume":"410","author":"S. Li","year":"2009","unstructured":"Li, S., Li, M.: On two open problems of 2-interval patterns. Theoretical Computer Science\u00a0410(24-25), 2410\u20132423 (2009)","journal-title":"Theoretical Computer Science"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Lothaire, M.: Applied Combinatorics on Words. Encyclopedia of Mathematics and its Applications, vol.\u00a0105. Cambridge university press (2005)","DOI":"10.1017\/CBO9781107341005"},{"issue":"2","key":"21_CR16","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D. Maier","year":"1978","unstructured":"Maier, D.: The complexity of some problems on subsequences and supersequences. Journal of the ACM\u00a025(2), 322\u2013336 (1978)","journal-title":"Journal of the ACM"},{"key":"21_CR17","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0166-218X(83)90021-5","volume":"5","author":"A. Mansfield","year":"1983","unstructured":"Mansfield, A.: On the computational complexity of a merge recognition problem. Discrete Applied Mathematics\u00a05, 119\u2013122 (1983)","journal-title":"Discrete Applied Mathematics"},{"key":"21_CR18","unstructured":"Rampersad, D.H.N., Shallit, J.: Shuffling and unshuffling (2011), \n                    \n                      http:\/\/arxiv.org\/abs\/1106.5767"},{"key":"21_CR19","doi-asserted-by":"crossref","unstructured":"Spehner, J.C.: Le calcul rapide des melanges de deux mots. In: Theoretical Computer Science pp. 171\u2013203 (1986)","DOI":"10.1016\/0304-3975(86)90145-3"},{"issue":"2-3","key":"21_CR20","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/j.tcs.2003.08.010","volume":"312","author":"S. Vialette","year":"2004","unstructured":"Vialette, S.: On the computational complexity of 2-interval pattern matching problems. Theoretical Computer Science\u00a0312(2-3), 223\u2013249 (2004)","journal-title":"Theoretical Computer Science"},{"key":"21_CR21","doi-asserted-by":"crossref","unstructured":"Vialette, S.: Two-interval pattern problems. In: Kao, M.Y. (ed.) Encyclopedia of Algorithms, pp. 985\u2013989. Springer (2008)","DOI":"10.1007\/978-0-387-30162-4_445"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38536-0_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T12:27:01Z","timestamp":1557750421000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38536-0_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642385353","9783642385360"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38536-0_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}