{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T06:35:18Z","timestamp":1649140518482},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2005,10]]},"abstract":"<jats:p> The decidability of the shuffle decomposition problem for regular languages is a long standing open question. We consider decompositions of regular languages with respect to shuffle along a regular set of trajectories and obtain positive decidability results for restricted classes of trajectories. Also we consider decompositions of unary regular languages. Finally, we establish in the spirit of the Dassow-Hinz undecidability result an undecidability result for regular languages shuffled along a fixed linear context-free set of trajectories. <\/jats:p>","DOI":"10.1142\/s0129054105003364","type":"journal-article","created":{"date-parts":[[2005,10,13]],"date-time":"2005-10-13T11:41:41Z","timestamp":1129203701000},"page":"897-912","source":"Crossref","is-referenced-by-count":3,"title":["RESTRICTED SETS OF TRAJECTORIES AND DECIDABILITY OF SHUFFLE DECOMPOSITIONS"],"prefix":"10.1142","volume":"16","author":[{"given":"MICHAEL","family":"DOMARATZKI","sequence":"first","affiliation":[{"name":"Jodrey School of Computer Science,  Acadia University, Wolfville, Nova Scotia B4P 2R6, Canada"}]},{"given":"KAI","family":"SALOMAA","sequence":"additional","affiliation":[{"name":"School of Computing,  Queen's University, Kingston, Ontario K7L 3N6, Canada"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054102001461"},{"key":"rf2","first-page":"29","volume":"45","author":"Dassow J.","journal-title":"Theoret. Comput. Sci."},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.02.031"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)80003-7"},{"key":"rf7","first-page":"168","volume":"38","author":"Hinz F.","journal-title":"Bulletin of the EATCS"},{"key":"rf8","volume-title":"Introduction to automata theory, languages and computation","author":"Hopcroft J. E.","year":"1979"},{"key":"rf9","first-page":"257","volume":"8","author":"Ito M.","journal-title":"J. Universal Comput. Sci."},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.09.038"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00163-1"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45711-9_7"},{"key":"rf14","first-page":"145","volume":"5","author":"Mateescu A.","journal-title":"J. Automata, Languages and Combinatorics"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.2307\/1970290"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00014-5"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054105003364","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:41:14Z","timestamp":1565138474000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054105003364"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,10]]},"references-count":13,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,10]]}},"alternative-id":["10.1142\/S0129054105003364"],"URL":"https:\/\/doi.org\/10.1142\/s0129054105003364","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,10]]}}}