{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T21:41:02Z","timestamp":1794346862978,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540434535","type":"print"},{"value":"9783540460114","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-46011-x_15","type":"book-chapter","created":{"date-parts":[[2007,6,18]],"date-time":"2007-06-18T18:54:16Z","timestamp":1182192856000},"page":"186-196","source":"Crossref","is-referenced-by-count":4,"title":["Shuffle Quotient and Decompositions"],"prefix":"10.1007","author":[{"given":"C.","family":"C\u00e2mpeanu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"K.","family":"Salomaa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S.","family":"V\u00e1gv\u00f6lgyi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2002,3,19]]},"reference":[{"key":"15_CR1","unstructured":"J. Berstel, L. Boasson. Shuffle factorization is unique. Research report November 1999. \n                    http:\/\/www-igm.univ-mlv.fr\/ berstel\/Recherche.html\n                    \n                   complexity"},{"key":"15_CR2","unstructured":"C. C\u00e2mpeanu, K. Salomaa, S. Yu. Tight lower bound for the state complexity of shuffleof regular languages. Accepted for publication in Journal of Automata, Languages and Combinatorics."},{"key":"15_CR3","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/S0304-3975(98)00332-6","volume":"242","author":"P. Caron","year":"2000","unstructured":"P. Caron. Families of locally testable languages. Theoretical Computer Science\n                           242 (2000) 361\u2013376.","journal-title":"Theoretical Computer Science"},{"key":"15_CR4","unstructured":"J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979."},{"key":"15_CR5","unstructured":"B. Imreh, M. Ito, M. Katsura. On shuffle closures of commutative regular languages. In: Combinatorics, Complexity & Logic, Proc. of DMTCS\u201996, Springer-Verlag, 1996, pp. 276\u2013288."},{"key":"15_CR6","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/S0304-3975(99)00277-7","volume":"245","author":"M. Ito","year":"2000","unstructured":"M. Ito, L. Kari, G. Thierrin. Shuffle and scattered deletion closure of languages. Theoretical Computer Science\n                           245 (2000) 115\u2013133.","journal-title":"Theoretical Computer Science"},{"key":"15_CR7","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0304-3975(85)90221-X","volume":"38","author":"M. Jantzen","year":"1985","unstructured":"M. Jantzen. Extending regular expressions with iterated shuffle. Theoretical Computer Science\n                           38 (1985) 223\u2013247.","journal-title":"Theoretical Computer Science"},{"key":"15_CR8","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0304-3975(99)00109-7","volume":"250","author":"J. Jedrzejowicz","year":"2001","unstructured":"J. Jedrzejowicz, A. Szepietowski. Shuffle languages are in P. Theoretical Computer Science\n                           250 (2001) 31\u201353.","journal-title":"Theoretical Computer Science"},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1109\/12.93741","volume":"40","author":"S. Kim","year":"1991","unstructured":"S. Kim, R. McNaughton, R. McCloskey.Apolynomial time algorithm for the local testability problem of deterministic finite automata. IEEE Trans. Comput.\n                           40 (1991) 1087\u20131093.","journal-title":"IEEE Trans. Comput."},{"key":"15_CR10","doi-asserted-by":"publisher","first-page":"1193","DOI":"10.1137\/S0097539791216987","volume":"23","author":"S. Kim","year":"1994","unstructured":"S. Kim, R. McNaughton. Computing the order of a locally testable automaton. SIAM Journal of Computing\n                           23 (1994) 1193\u20131215.","journal-title":"SIAM Journal of Computing"},{"key":"15_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/3-540-62844-4_28","volume-title":"New Trends in Formal Languages","author":"A. Mateescu","year":"1997","unstructured":"A. Mateescu, G.D. Mateescu, G. Rozenberg, A. Salomaa. Shuffle-like operations on \u03c9-words. In: New Trends in Formal Languages, Lecture Notes in Computer Science 1218, Springer-Verlag, 1997, 395\u2013411."},{"key":"15_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00163-1","volume":"197","author":"A. Mateescu","year":"1998","unstructured":"A. Mateescu, G. Rozenberg, A. Salomaa. Shuffle on trajectories: Syntactic constraints. Theoretical Computer Science\n                           197 (1998) 1\u201356.","journal-title":"Theoretical Computer Science"},{"key":"15_CR13","volume-title":"Counter-Free Automata","author":"R. McNaughton","year":"1971","unstructured":"R. McNaughton, S. Papert. Counter-Free Automata. MIT Press, Cambridge, Mass. 1971."},{"key":"15_CR14","unstructured":"A. Salomaa. Formal Languages. Academic Press, 1973."},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0304-3975(99)00017-1","volume":"231","author":"A.N. Trahtman","year":"2000","unstructured":"A.N. Trahtman. Optimal estimation on the order of local testability of finite automata. Theoretical Computer Science\n                           231 (2000) 59\u201374.","journal-title":"Theoretical Computer Science"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"S. Yu. Regular languages. In: Handbook of Formal Languages, Vol. I, G. Rozenberg and A. Salomaa, eds., Springer-Verlag, pp. 41\u2013110, 1997.","DOI":"10.1007\/978-3-642-59136-5_2"},{"key":"15_CR17","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(92)00011-F","volume":"125","author":"S. Yu","year":"1994","unstructured":"S. Yu, Q. Zhuang, K. Salomaa. The state complexities of some basic operations on regular languages. Theoretical Computer Science\n                           125 (1994) 315\u2013328.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46011-X_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,17]],"date-time":"2019-02-17T05:45:38Z","timestamp":1550382338000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46011-X_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540434535","9783540460114"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-46011-x_15","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/3-540-46011-x","asserted-by":"object"}]},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2002]]}}}