{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T15:04:22Z","timestamp":1786979062287,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642193903","type":"print"},{"value":"9783642193910","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-19391-0_5","type":"book-chapter","created":{"date-parts":[[2011,4,28]],"date-time":"2011-04-28T04:53:35Z","timestamp":1303966415000},"page":"63-75","source":"Crossref","is-referenced-by-count":2,"title":["On Language Decompositions and Primality"],"prefix":"10.1007","author":[{"given":"Michael","family":"Domaratzki","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1142\/S0218196796000246","volume":"6","author":"M. Anselmo","year":"1996","unstructured":"Anselmo, M., Restivo, A.: On languages factorizing the free monoid. Internat. J. Algebra and Computation\u00a06, 413\u2013427 (1996)","journal-title":"Internat. J. Algebra and Computation"},{"key":"5_CR2","doi-asserted-by":"publisher","first-page":"799","DOI":"10.1142\/S0129054102001461","volume":"13","author":"C. C\u00e2mpeanu","year":"2002","unstructured":"C\u00e2mpeanu, C., Salomaa, K., V\u00e1gv\u00f6lgyi, S.: Shuffle decompositions of regular languages. Internat. J. Foundations of Computer Science\u00a013, 799\u2013816 (2002)","journal-title":"Internat. J. Foundations of Computer Science"},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"Choffrut, C., Karhum\u00e4ki, J.: Fatou properties of rational languages. In: Martin-Vide, C., Mitrana, V. (eds.) Where Mathematics, Computer Science, Linguistics and Biology Meet, pp. 227\u2013235 (2000)","DOI":"10.1007\/978-94-015-9634-3_20"},{"key":"5_CR4","volume-title":"Regular Algebra and Finite Machines","author":"J.H. Conway","year":"1971","unstructured":"Conway, J.H.: Regular Algebra and Finite Machines. Chapman and Hall, Boca Raton (1971)"},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"1019","DOI":"10.1142\/S0129054103002151","volume":"14","author":"J. Czyzowicz","year":"2003","unstructured":"Czyzowicz, J., Fraczak, W., Pelc, A., Rytter, W.: Linear-time prime decomposition of regular prefix codes. Internat. J. Foundations of Computer Science\u00a014, 1019\u20131031 (2003)","journal-title":"Internat. J. Foundations of Computer Science"},{"key":"5_CR6","first-page":"653","volume":"16","author":"M. Daley","year":"2010","unstructured":"Daley, M., Domaratzki, M., Salomaa, K.: Orthogonal concatenation: Language equations and state complexity. J. Universal Comput. Sci.\u00a016, 653\u2013675 (2010)","journal-title":"J. Universal Comput. Sci."},{"key":"5_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-540-30550-7_14","volume-title":"Developments in Language Theory","author":"M. Domaratzki","year":"2004","unstructured":"Domaratzki, M.: Semantic shuffle on and deletion along trajectories. In: Calude, C.S., Calude, E., Dinneen, M.J. (eds.) DLT 2004. LNCS, vol.\u00a03340, pp. 163\u2013174. Springer, Heidelberg (2004)"},{"key":"5_CR8","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.\u00a0320, 293\u2013313 (2004)","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR9","unstructured":"Domaratzki, M.: Trajectory-Based Operations. PhD thesis, Queen\u2019s University (2004)"},{"key":"5_CR10","first-page":"107","volume":"86","author":"M. Domaratzki","year":"2005","unstructured":"Domaratzki, M.: More Words on Trajectories. Formal Language Theory Column, Bull. Eur. Assoc. Theor. Comp. Sci.\u00a086, 107\u2013145 (2005)","journal-title":"Formal Language Theory Column, Bull. Eur. Assoc. Theor. Comp. Sci."},{"key":"5_CR11","first-page":"182","volume":"73","author":"M. Domaratzki","year":"2006","unstructured":"Domaratzki, M., Rozenberg, G., Salomaa, K.: Interpreted trajectories. Fundamenta Informaticae\u00a073, 182\u2013193 (2006)","journal-title":"Fundamenta Informaticae"},{"key":"5_CR12","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.\u00a0345, 304\u2013330 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR13","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. Internat. J. Foundations of Computer Science\u00a016, 897\u2013912 (2005)","journal-title":"Internat. J. Foundations of Computer Science"},{"key":"5_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/978-3-540-73208-2_20","volume-title":"Developments in Language Theory","author":"A. Frid","year":"2007","unstructured":"Frid, A.: Commutation of binary factorial languages. In: Harju, T., Karhum\u00e4ki, J., Lepist\u00f6, A. (eds.) DLT 2007. LNCS, vol.\u00a04588, pp. 193\u2013204. Springer, Heidelberg (2007)"},{"key":"5_CR15","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.tcs.2007.01.013","volume":"376","author":"Y.-S. Han","year":"2007","unstructured":"Han, Y.-S., Salomaa, A., Salomaa, K., Wood, D., Yu, S.: On the existence of prime decompositions. Theoret. Comput. Sci.\u00a0376, 60\u201369 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR16","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1142\/S0129054106003887","volume":"17","author":"Y.-S. Han","year":"2006","unstructured":"Han, Y.-S., Wang, Y., Wood, D.: Infix-free regular expressions and languages. Internat. J. Found. Comput. Sci.\u00a017, 379\u2013393 (2006)","journal-title":"Internat. J. Found. Comput. Sci."},{"key":"5_CR17","first-page":"168","volume":"38","author":"F. Hinz","year":"1989","unstructured":"Hinz, F., Dassow, J.: An undecidability result for regular languages and its application to regulated rewriting. Bulletin of the EATCS\u00a038, 168\u2013174 (1989)","journal-title":"Bulletin of the EATCS"},{"key":"5_CR18","first-page":"257","volume":"8","author":"M. Ito","year":"2002","unstructured":"Ito, M.: Shuffle decomposition of regular languages. J. Universal Comput. Sci.\u00a08, 257\u2013259 (2002)","journal-title":"J. Universal Comput. Sci."},{"key":"5_CR19","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/S0304-3975(99)00277-7","volume":"245","author":"M. Ito","year":"2000","unstructured":"Ito, M., Kari, L., Thierrin, G.: Shuffle and scattered deletion closure of languages. Theor. Comp. Sci.\u00a0245, 115\u2013133 (2000)","journal-title":"Theor. Comp. Sci."},{"key":"5_CR20","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1137\/0222067","volume":"22","author":"T. Jiang","year":"1993","unstructured":"Jiang, T., Ravikumar, B.: Minimal NFA problems are hard. SIAM J. Comput.\u00a022, 1117\u20131141 (1993)","journal-title":"SIAM J. Comput."},{"key":"5_CR21","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1142\/9789812562494_0060","volume-title":"Current Trends in Theoretical Computer Science\u2013 The Challenge of the New Century","author":"J. Karhum\u00e4ki","year":"2004","unstructured":"Karhum\u00e4ki, J., Petre, I.: Two problems on commutation of languages. In: Current Trends in Theoretical Computer Science\u2013 The Challenge of the New Century, vol.\u00a02, pp. 477\u2013494. World Scientific, Singapore (2004)"},{"key":"5_CR22","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. Theor. Comp. Sci.\u00a0132, 129\u2013150 (1994)","journal-title":"Theor. Comp. Sci."},{"key":"5_CR23","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/j.jcss.2004.08.005","volume":"70","author":"L. Kari","year":"2005","unstructured":"Kari, L., Konstantinidis, S.: Language equations, maximality and error-detection. J. Comput. System Sci.\u00a070, 157\u2013178 (2005)","journal-title":"J. Comput. System Sci."},{"key":"5_CR24","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.\u00a0332, 47\u201361 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR25","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1006\/jcss.1996.0082","volume":"53","author":"L. Kari","year":"1996","unstructured":"Kari, L., Thierrin, G.: Maximal and minimal solutions to language equations. J. Comput. System Sci.\u00a053, 487\u2013496 (1996)","journal-title":"J. Comput. System Sci."},{"key":"5_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/978-3-540-73208-2_3","volume-title":"Developments in Language Theory","author":"M. Kunc","year":"2007","unstructured":"Kunc, M.: What do we know about language equations? In: Harju, T., Karhum\u00e4ki, J., Lepist\u00f6, A. (eds.) DLT 2007. LNCS, vol.\u00a04588, pp. 23\u201327. Springer, Heidelberg (2007)"},{"key":"5_CR27","doi-asserted-by":"crossref","unstructured":"Martens, W., Niewerth, M., Schwentick, T.: Schema design for XML repositories: Complexity and tractability. In: Proceedings of ACM Symposium on Principles of Database Systems, PODS 2010, June 6\u201311 (2010)","DOI":"10.1145\/1807085.1807117"},{"key":"5_CR28","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.\u00a0197, 1\u201356 (1998)","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR29","first-page":"339","volume":"15","author":"A. Mateescu","year":"2002","unstructured":"Mateescu, A., Salomaa, A., Yu, S.: Factorizations of languages and commutativity conditions. Acta Cybernetica\u00a015, 339\u2013351 (2002)","journal-title":"Acta Cybernetica"},{"key":"5_CR30","first-page":"125","volume-title":"Symposium on Switching and Automata Theory, SWAT 1972","author":"A.R. Meyer","year":"1972","unstructured":"Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential time. In: Symposium on Switching and Automata Theory, SWAT 1972, pp. 125\u2013129. IEEE Society Press, Los Alamitos (1972)"},{"key":"5_CR31","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/j.jcss.2009.08.002","volume":"76","author":"A. Okhotin","year":"2010","unstructured":"Okhotin, A.: Decision problems for language equations. J. Comput. System Sci.\u00a076, 251\u2013266 (2010)","journal-title":"J. Comput. System Sci."},{"key":"5_CR32","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/S0019-9958(72)90406-8","volume":"20","author":"D. Perrin","year":"1972","unstructured":"Perrin, D.: Codes conjugu\u00e9s. Inform. and Control\u00a020, 221\u2013231 (1972)","journal-title":"Inform. and Control"},{"key":"5_CR33","doi-asserted-by":"publisher","first-page":"2431","DOI":"10.1016\/j.tcs.2009.02.035","volume":"410","author":"N. Rampersad","year":"2009","unstructured":"Rampersad, N., Ravikumar, B., Santean, N., Shallit, J.: State complexity of unique rational operations. Theoret. Comput. Sci.\u00a0410, 2431\u20132441 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR34","unstructured":"Rampersad, N., Shallit, J.: Private communication (2006)"},{"key":"5_CR35","doi-asserted-by":"publisher","first-page":"1340","DOI":"10.1016\/j.ic.2009.03.004","volume":"207","author":"A. Salomaa","year":"2009","unstructured":"Salomaa, A., Salomaa, K., Yu, S.: Variants of codes and indecomposable languages. Information and Computation\u00a0207, 1340\u20131349 (2009)","journal-title":"Information and Computation"},{"key":"5_CR36","first-page":"22","volume-title":"Proc. Developments in Language Theory, DLT 1999","author":"A. Salomaa","year":"2000","unstructured":"Salomaa, A., Yu, S.: On the decomposition of finite languages. In: Proc. Developments in Language Theory, DLT 1999, pp. 22\u201331. World Scientific Publ. Co., Singapore (2000)"},{"key":"5_CR37","volume-title":"A Second Course in Formal Languages and Automata Theory","author":"J. Shallit","year":"2009","unstructured":"Shallit, J.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press, Cambridge (2009)"},{"key":"5_CR38","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-642-59136-5_2","volume-title":"Handbook of Formal Languages","author":"S. Yu","year":"1997","unstructured":"Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol.\u00a0I, pp. 41\u2013110. Springer, Heidelberg (1997)"}],"container-title":["Lecture Notes in Computer Science","Rainbow of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-19391-0_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T01:47:25Z","timestamp":1558576045000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-19391-0_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642193903","9783642193910"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-19391-0_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}