{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T18:42:16Z","timestamp":1742928136846,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319192246"},{"type":"electronic","value":"9783319192253"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-19225-3_9","type":"book-chapter","created":{"date-parts":[[2015,6,15]],"date-time":"2015-06-15T15:51:06Z","timestamp":1434383466000},"page":"105-116","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Complexity and Decidability of Some Problems Involving Shuffle"],"prefix":"10.1007","author":[{"given":"Joey","family":"Eremondi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oscar H.","family":"Ibarra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ian","family":"McQuillan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,16]]},"reference":[{"issue":"3","key":"9_CR1","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/S0022-0000(74)80027-9","volume":"8","author":"BS Baker","year":"1974","unstructured":"Baker, B.S., Book, R.V.: Reversal-bounded multipushdown machines. J. Comput. Syst. Sci. 8(3), 315\u2013332 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR2","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/S0304-3975(00)00433-3","volume":"273","author":"J Berstel","year":"2002","unstructured":"Berstel, J., Boasson, L.: Shuffle factorization is unique. Theoret. Comput. Sci. 273, 47\u201367 (2002)","journal-title":"Theoret. Comput. Sci."},{"key":"9_CR3","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.tcs.2012.04.001","volume":"454","author":"F Biegler","year":"2012","unstructured":"Biegler, F., Daley, M., McQuillan, I.: Algorithmic decomposition of shuffle on words. Theoret. Comput. Sci. 454, 38\u201350 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"9_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1007\/978-3-319-08846-4_7","volume-title":"Implementation and Application of Automata","author":"F Biegler","year":"2014","unstructured":"Biegler, F., McQuillan, I.: On comparing deterministic finite automata and the shuffle of words. In: Holzer, M., Kutrib, M. (eds.) CIAA 2014. LNCS, vol. 8587, pp. 98\u2013109. Springer, Heidelberg (2014)"},{"key":"9_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/978-3-540-30500-2_7","volume-title":"Implementation and Application of Automata","author":"H Bordihn","year":"2005","unstructured":"Bordihn, H., Holzer, M., Kutrib, M.: Some non-semi-decidability problems for linear and deterministic context-free languages. In: Domaratzki, M., Okhotin, A., Salomaa, K., Yu, S. (eds.) CIAA 2004. LNCS, vol. 3317, pp. 68\u201379. Springer, Heidelberg (2005)"},{"issue":"4","key":"9_CR6","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":"9_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/3-540-46011-X_15","volume-title":"Developments in Language Theory","author":"C C\u00e2mpeanu","year":"2002","unstructured":"C\u00e2mpeanu, C., Salomaa, K., V\u00e1gv\u00f6lgyi, S.: Shuffle quotient and decompositions. In: Kuich, W., Rozenberg, G., Salomaa, A. (eds.) DLT 2001. LNCS, vol. 2295, pp. 186\u2013196. Springer, Heidelberg (2002)"},{"key":"9_CR8","first-page":"53","volume":"15","author":"M Daley","year":"2010","unstructured":"Daley, M., Biegler, F., McQuillan, I.: On the shuffle automaton size for words. J. Autom. Lang. Comb. 15, 53\u201370 (2010)","journal-title":"J. Autom. Lang. Comb."},{"key":"9_CR9","first-page":"107","volume":"86","author":"M Domaratzki","year":"2005","unstructured":"Domaratzki, M.: More words on trajectories. Bull. EATCS 86, 107\u2013145 (2005)","journal-title":"Bull. EATCS"},{"key":"9_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1007\/978-3-319-17142-5_33","volume-title":"Theory and Applications of Models of Computation","author":"J Eremondi","year":"2015","unstructured":"Eremondi, J., Ibarra, O.H., McQuillan, I.: Deletion operations on deterministic families of automata. In: Jain, R., Jain, S., Stephan, F. (eds.) TAMC 2015. LNCS, vol. 9076, pp. 388\u2013399. Springer, Heidelberg (2015)"},{"key":"9_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/978-3-319-15579-1_15","volume-title":"Language and Automata Theory and Applications","author":"J Eremondi","year":"2015","unstructured":"Eremondi, J., Ibarra, O.H., McQuillan, I.: Insertion operations on deterministic reversal-bounded counter machines. In: Dediu, A.-H., Formenti, E., Mart\u00edn-Vide, C., Truthe, B. (eds.) LATA 2015. LNCS, vol. 8977, pp. 200\u2013211. Springer, Heidelberg (2015)"},{"key":"9_CR12","series-title":"Series of Books in the Mathematical Sciences","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences. W. H. Freeman and Company, New York (1979)"},{"key":"9_CR13","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0304-3975(77)90033-0","volume":"4","author":"MM Geller","year":"1977","unstructured":"Geller, M.M., Hunt III, H.B., Szymanski, T.G., Ullman, J.D.: Economy of description by parsers, dpda\u2019s, and pda\u2019s. Theoret. Comput. Sci. 4, 143\u2013153 (1977)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"9_CR14","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1145\/321281.321294","volume":"12","author":"S Ginsburg","year":"1965","unstructured":"Ginsburg, S., Spanier, E.H.: Mappings of languages by two-tape devices. J. ACM 12(3), 423\u2013434 (1965)","journal-title":"J. ACM"},{"issue":"2","key":"9_CR15","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0022-0000(81)90028-3","volume":"22","author":"EM Gurari","year":"1981","unstructured":"Gurari, E.M., Ibarra, O.H.: The complexity of decision problems for finite-turn multicounter machines. J. Comput. Syst. Sci. 22(2), 220\u2013229 (1981)","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR16","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"JE Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)"},{"issue":"1","key":"9_CR17","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/322047.322058","volume":"25","author":"OH Ibarra","year":"1978","unstructured":"Ibarra, O.H.: Reversal-bounded multicounter machines and their decision problems. J. ACM 25(1), 116\u2013133 (1978)","journal-title":"J. ACM"},{"key":"9_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/978-3-319-09704-6_2","volume-title":"Descriptional Complexity of Formal Systems","author":"OH Ibarra","year":"2014","unstructured":"Ibarra, O.H.: Automata with reversal-bounded counters: a survey. In: J\u00fcrgensen, H., Karhum\u00e4ki, J., Okhotin, A. (eds.) DCFS 2014. LNCS, vol. 8614, pp. 5\u201322. Springer, Heidelberg (2014)"},{"key":"9_CR19","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0304-3975(99)00109-7","volume":"250","author":"J J\u0229drzejowicz","year":"2001","unstructured":"J\u0229drzejowicz, J., Szepietowski, A.: Shuffle languages are in P. Theoret. Comput. Sci. 250, 31\u201353 (2001)","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20132","key":"9_CR20","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0304-3975(94)90230-5","volume":"132","author":"L Kari","year":"1994","unstructured":"Kari, L.: On language equations with invertible operations. Theoret. Comput. Sci. 132(1\u20132), 129\u2013150 (1994)","journal-title":"Theoret. Comput. Sci."},{"key":"9_CR21","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/j.tcs.2004.12.032","volume":"334","author":"L Kari","year":"2005","unstructured":"Kari, L., Konstandtinidis, S., Sos\u00edk, P.: On properties of bond-free DNA languages. Theoret. Comput. Sci. 334, 131\u2013159 (2005)","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20133","key":"9_CR22","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.tcs.2004.09.038","volume":"332","author":"L Kari","year":"2005","unstructured":"Kari, L., Sos\u00edk, P.: Aspects of shuffle and deletion on trajectories. Theoret. Comput. Sci. 332(1\u20133), 47\u201361 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"9_CR23","volume-title":"Seminumerical Algorithms, The Art of Computer Programming","author":"DE Knuth","year":"1998","unstructured":"Knuth, D.E.: Seminumerical Algorithms, The Art of Computer Programming, 3rd edn. Addison-Wesley, Reading (1998)","edition":"3"},{"issue":"3","key":"9_CR24","doi-asserted-by":"publisher","first-page":"437","DOI":"10.2307\/1970290","volume":"74","author":"ML Minsky","year":"1961","unstructured":"Minsky, M.L.: Recursive unsolvability of Post\u2019s problem of \u201ctag\u201d and other topics in theory of Turing machines. Ann. Math. 74(3), 437\u2013455 (1961)","journal-title":"Ann. Math."},{"key":"9_CR25","doi-asserted-by":"crossref","unstructured":"Ogden, W.F., Riddle, W.E., Round, W.C.: Complexity of expressions allowing concurrency. In: Proceedings of the 5th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL 1978, pp. 185\u2013194. ACM NY, USA (1978)","DOI":"10.1145\/512760.512780"}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19225-3_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T12:43:34Z","timestamp":1676637814000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19225-3_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319192246","9783319192253"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19225-3_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}