{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,11]],"date-time":"2026-08-11T19:28:06Z","timestamp":1786476486737,"version":"build-2736575974"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032311764","type":"print"},{"value":"9783032359674","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-31176-4_7","type":"book-chapter","created":{"date-parts":[[2026,8,11]],"date-time":"2026-08-11T18:44:44Z","timestamp":1786473884000},"page":"92-107","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Decomposing Regular Languages Under Shuffle Along Trajectories"],"prefix":"10.1007","author":[{"given":"Sungmin","family":"Kim","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hyunki","family":"Hong","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Taeryung","family":"Lim","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yo-Sub","family":"Han","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,8,5]]},"reference":[{"issue":"2","key":"7_CR1","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/0304-3975(93)90327-P","volume":"116","author":"M Andrasiu","year":"1993","unstructured":"Andrasiu, M., Paun, G., Dassow, J., Salomaa, A.: Language-theoretic problems arising from Richelieu cryptosystems. Theoret. Comput. Sci. 116(2), 339\u2013357 (1993)","journal-title":"Theoret. Comput. Sci."},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, H., Bojanczyk, M.: Shuffle expressions and words with nested data. In: Proceedings of the 32nd International Symposium on Mathematical Foundations of Computer Science, MFCS, pp. 750\u2013761 (2007)","DOI":"10.1007\/978-3-540-74456-6_66"},{"issue":"1","key":"7_CR3","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1145\/321495.321505","volume":"16","author":"JA Brzozowski","year":"1969","unstructured":"Brzozowski, J.A., Cohen, R.S.: On decompositions of regular events. J. ACM 16(1), 132\u2013144 (1969)","journal-title":"J. ACM"},{"issue":"3","key":"7_CR4","first-page":"303","volume":"7","author":"C C\u00e2mpeanu","year":"2002","unstructured":"C\u00e2mpeanu, C., Salomaa, K., Yu, S.: Tight lower bound for the state complexity of shuffle of regular languages. J. Autom. Lang. Comb. 7(3), 303\u2013310 (2002)","journal-title":"J. Autom. Lang. Comb."},{"issue":"2\u20133","key":"7_CR5","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/j.tcs.2004.02.031","volume":"320","author":"M Domaratzki","year":"2004","unstructured":"Domaratzki, M.: Deletion along trajectories. Theoret. Comput. Sci. 320(2\u20133), 293\u2013313 (2004)","journal-title":"Theoret. Comput. Sci."},{"issue":"2\/3","key":"7_CR6","first-page":"217","volume":"9","author":"M Domaratzki","year":"2004","unstructured":"Domaratzki, M., Salomaa, K.: State complexity of shuffle on trajectories. J. Autom. Lang. Comb. 9(2\/3), 217\u2013232 (2004)","journal-title":"J. Autom. Lang. Comb."},{"issue":"2\u20133","key":"7_CR7","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1016\/j.tcs.2005.07.013","volume":"345","author":"M Domaratzki","year":"2005","unstructured":"Domaratzki, M., Salomaa, K.: Decidability of trajectory-based equations. Theoret. Comput. Sci. 345(2\u20133), 304\u2013330 (2005)","journal-title":"Theoret. Comput. Sci."},{"issue":"5","key":"7_CR8","doi-asserted-by":"publisher","first-page":"897","DOI":"10.1142\/S0129054105003364","volume":"16","author":"M Domaratzki","year":"2005","unstructured":"Domaratzki, M., Salomaa, K.: Restricted sets of trajectories and decidability of shuffle decompositions. Int. J. Found. Comput. Sci. 16(5), 897\u2013912 (2005)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"Domaratzki, M., Salomaa, K.: On language decompositions and primality. In: Rainbow of Computer Science - Dedicated to Hermann Maurer on the Occasion of His 70th Birthday, pp. 63\u201375 (2011)","DOI":"10.1007\/978-3-642-19391-0_5"},{"key":"7_CR10","unstructured":"Emerson, E.A., Lei, C.: Temporal model checking under generalized fairness constraints. In: Proceedings of the 18th Annual Hawaii International Conference on System Sciences (1985)"},{"issue":"3","key":"7_CR11","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0167-6423(87)90036-0","volume":"8","author":"EA Emerson","year":"1987","unstructured":"Emerson, E.A., Lei, C.: Modalities for model checking: branching time logic strikes back. Sci. Comput. Program. 8(3), 275\u2013306 (1987)","journal-title":"Sci. Comput. Program."},{"issue":"2","key":"7_CR12","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/0304-3975(92)90339-H","volume":"96","author":"VK Garg","year":"1992","unstructured":"Garg, V.K., Ragunath, M.T.: Concurrent regular expressions and their relationship to Petri nets. Theoret. Comput. Sci. 96(2), 285\u2013304 (1992)","journal-title":"Theoret. Comput. Sci."},{"issue":"5","key":"7_CR13","doi-asserted-by":"publisher","first-page":"2021","DOI":"10.1137\/070697367","volume":"38","author":"W Gelade","year":"2009","unstructured":"Gelade, W., Martens, W., Neven, F.: Optimizing schema languages for XML: numerical constraints and interleaving. SIAM J. Comput. 38(5), 2021\u20132043 (2009)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"7_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":"9","key":"7_CR15","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1145\/358746.358767","volume":"24","author":"JL Gischer","year":"1981","unstructured":"Gischer, J.L.: Shuffle languages, Petri nets, and context-sensitive grammars. Commun. ACM 24(9), 597\u2013605 (1981)","journal-title":"Commun. ACM"},{"issue":"1\u20132","key":"7_CR16","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.tcs.2007.01.013","volume":"376","author":"YS Han","year":"2007","unstructured":"Han, Y.S., Salomaa, A., Salomaa, K., Wood, D., Yu, S.: On the existence of prime decompositions. Theoret. Comput. Sci. 376(1\u20132), 60\u201369 (2007)","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20132","key":"7_CR17","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0304-3975(99)00109-7","volume":"250","author":"J Jedrzejowicz","year":"2001","unstructured":"Jedrzejowicz, J., Szepietowski, A.: Shuffle languages are in P. Theoret. Comput. Sci. 250(1\u20132), 31\u201353 (2001)","journal-title":"Theoret. Comput. Sci."},{"key":"7_CR18","doi-asserted-by":"crossref","unstructured":"Kuhlmann, M., Satta, G.: Treebank grammar techniques for non-projective dependency parsing. In: Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics, EACL, pp. 478\u2013486. The Association for Computer Linguistics (2009)","DOI":"10.3115\/1609067.1609120"},{"issue":"1\u20132","key":"7_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00163-1","volume":"197","author":"A Mateescu","year":"1998","unstructured":"Mateescu, A., Rozenberg, G., Salomaa, A.: Shuffle on trajectories: Syntactic constraints. Theoret. Comput. Sci. 197(1\u20132), 1\u201356 (1998)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"7_CR20","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/0304-3975(84)90049-5","volume":"32","author":"S Miyano","year":"1984","unstructured":"Miyano, S., Hayashi, T.: Alternating finite automata on $$\\omega $$-words. Theoret. Comput. Sci. 32(3), 321\u2013330 (1984)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"7_CR21","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0166-218X(94)00014-5","volume":"61","author":"G Paun","year":"1995","unstructured":"Paun, G., Salomaa, A.: Thin and slender languages. Discret. Appl. Math. 61(3), 257\u2013270 (1995)","journal-title":"Discret. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-31176-4_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,11]],"date-time":"2026-08-11T18:44:46Z","timestamp":1786473886000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-31176-4_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032311764","9783032359674"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-31176-4_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"5 August 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Implementation and Application of Automata","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Kingston","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 May 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 May 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wia2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/research.cs.queensu.ca\/ciaa2026\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}