{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T13:17:39Z","timestamp":1774444659273,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662495285","type":"print"},{"value":"9783662495292","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-49529-2_38","type":"book-chapter","created":{"date-parts":[[2016,3,21]],"date-time":"2016-03-21T08:09:41Z","timestamp":1458547781000},"page":"509-521","source":"Crossref","is-referenced-by-count":2,"title":["Unshuffling Permutations"],"prefix":"10.1007","author":[{"given":"Samuele","family":"Giraudo","sequence":"first","affiliation":[]},{"given":"St\u00e9phane","family":"Vialette","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,3,22]]},"reference":[{"key":"38_CR1","unstructured":"Allauzen, C.: Calcul efficace du shuffle de $$k$$ k mots. Technical report, Institut Gaspard Monge, Universit\u00e9 Marne-la-Vall\u00e9e (2000)"},{"issue":"5","key":"38_CR2","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/S0020-0190(97)00209-3","volume":"65","author":"P Bose","year":"1998","unstructured":"Bose, P., Buss, J.F., Lubiw, A.: Pattern matching for permutations. Inf. Process. Lett. 65(5), 277\u2013283 (1998)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"38_CR3","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1016\/j.jcss.2013.11.002","volume":"80","author":"S Buss","year":"2014","unstructured":"Buss, S., Soltys, M.: Unshuffling a square is NP-hard. J. Comput. Syst. Sci. 80(4), 766\u2013776 (2014)","journal-title":"J. Comput. Syst. Sci."},{"key":"38_CR4","volume-title":"Handbook of Formal Languages","author":"C Choffrut","year":"1997","unstructured":"Choffrut, C., Karhum\u00e4ki, J.: Combinatorics of words. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages. Springer, Heidelberg (1997)"},{"issue":"5","key":"38_CR5","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1142\/S0218196702001139","volume":"12","author":"G Duchamp","year":"2002","unstructured":"Duchamp, G., Hivert, F., Thibon, J.-Y.: Noncommutative symmetric functions. VI. Free quasi-symmetric functions and related algebras. Int. J. Algebr. Comput. 12(5), 671\u2013717 (2002)","journal-title":"Int. J. Algebr. Comput."},{"issue":"2","key":"38_CR6","first-page":"58:55","volume":"58","author":"S Eilenberg","year":"1953","unstructured":"Eilenberg, S., Mac Lane, S.: On the groups of $$H(\\Pi, n)$$ H ( \u03a0 , n ) . I. Ann. of Math. 58(2), 58:55\u201358:106 (1953)","journal-title":"I. Ann. of Math."},{"key":"38_CR7","unstructured":"Grinberg, D., Reiner, V.: Hopf Algebras in Combinatorics (2014). arxiv:1409.8356"},{"issue":"2","key":"38_CR8","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1002\/sapm197961293","volume":"61","author":"SA Joni","year":"1979","unstructured":"Joni, S.A., Rota, G.-C.: Coalgebras and bialgebras in combinatorics. Stud. Appl. Math. 61(2), 93\u2013139 (1979)","journal-title":"Stud. Appl. Math."},{"key":"38_CR9","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 Appl. Math. 5, 119\u2013122 (1983)","journal-title":"Discrete Appl. Math."},{"key":"38_CR10","unstructured":"Henshall, D., Rampersad, N., Shallit, J.: Shuffling and unshuffling (2011). http:\/\/arxiv.org\/abs\/1106.5767"},{"key":"38_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-642-38536-0_21","volume-title":"Computer Science \u2013 Theory and Applications","author":"R Rizzi","year":"2013","unstructured":"Rizzi, R., Vialette, S.: On recognizing words that are squares for the shuffle product. In: Bulatov, A.A., Shur, A.M. (eds.) CSR 2013. LNCS, vol. 7913, pp. 235\u2013245. Springer, Heidelberg (2013)"},{"issue":"4","key":"38_CR12","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/S0195-6698(85)80052-4","volume":"6","author":"R Simion","year":"1985","unstructured":"Simion, R., Schmidt, F.W.: Restricted permutations. Eur. J. Comb. 6(4), 383\u2013406 (1985)","journal-title":"Eur. J. Comb."},{"key":"38_CR13","unstructured":"Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences. https:\/\/oeis.org\/"},{"key":"38_CR14","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0304-3975(86)90145-3","volume":"47","author":"J-C Spehner","year":"1986","unstructured":"Spehner, J.-C.: Le calcul rapide des melanges de deux mots. Theoret. Comput. Sci. 47, 181\u2013203 (1986)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"38_CR15","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. Inf. Process. Lett. 14(1), 34\u201338 (1982)","journal-title":"Inf. Process. Lett."},{"key":"38_CR16","doi-asserted-by":"crossref","unstructured":"Y. Vargas. Hopf algebra of permutation pattern functions. In: 26th International Conference on Formal Power Series and Algebraic Combinatorics, pp. 839\u2013850 (2014)","DOI":"10.46298\/dmtcs.2446"},{"issue":"3","key":"38_CR17","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/0022-0000(84)90018-7","volume":"28","author":"MK Warmuth","year":"1984","unstructured":"Warmuth, M.K., Haussler, D.: On the complexity of iterated shuffle. J. Comput. Syst. Sci. 28(3), 345\u2013358 (1984)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Lecture Notes in Computer Science","LATIN 2016: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49529-2_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,15]],"date-time":"2022-06-15T19:16:15Z","timestamp":1655320575000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49529-2_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662495285","9783662495292"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49529-2_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}