{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T23:01:13Z","timestamp":1648940473251},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2002,12]]},"abstract":"<jats:p> We study the shuffle quotient operation and introduce equivalence relations it defines with respect to a (regular) language. Corresponding to an arbitrary shuffle decomposition we construct a normalized decomposition that is defined in terms of maximal languages. Using closure properties of the normalized decompositions we show that for certain subclasses of regular languages we can effectively decide whether or not the language has a non-trivial shuffle decomposition. We show that shuffle decomposition is undecidable for context-free languages. <\/jats:p>","DOI":"10.1142\/s0129054102001461","type":"journal-article","created":{"date-parts":[[2002,11,21]],"date-time":"2002-11-21T10:17:37Z","timestamp":1037873857000},"page":"799-816","source":"Crossref","is-referenced-by-count":8,"title":["SHUFFLE DECOMPOSITIONS OF REGULAR LANGUAGES"],"prefix":"10.1142","volume":"13","author":[{"given":"C.","family":"C\u00c2MPEANU","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science,  University of Prince Edward Island, Charlottetown,  P.E.I. C1A 4P3, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K.","family":"SALOMAA","sequence":"additional","affiliation":[{"name":"Department of Computing and Information Science,  Queen's University, Kingston, Ontario, K7L 3N6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"V\u00c1GV\u00d6LGYI","sequence":"additional","affiliation":[{"name":"Department of Applied Informatics,  University of Szeged, Szeged \u00c1rp\u00e1d t\u00e9r 2,  H-6720, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00433-3"},{"key":"p_4","author":"Campeanu C.","journal-title":"Accepted for publication in J. of Automata, Languages and Combinatorics."},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00332-6"},{"key":"p_9","first-page":"257","volume":"8","author":"Ito M.","year":"2002","journal-title":"J. Universal Computer Science"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00277-7"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90221-X"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00109-7"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1109\/12.93741"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791216987"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-62844-4_28"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00163-1"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00014-5"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55808-X_48"},{"key":"p_22","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00017-1"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054102001461","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:34:02Z","timestamp":1565192042000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054102001461"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,12]]},"references-count":14,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2002,12]]}},"alternative-id":["10.1142\/S0129054102001461"],"URL":"https:\/\/doi.org\/10.1142\/s0129054102001461","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,12]]}}}