{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T22:29:05Z","timestamp":1791412145543,"version":"4.3.3"},"reference-count":18,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2011,8]]},"abstract":"<jats:p>Solid codes have a nice property called synchronization property, which is useful in data transmission. The property is derived from infix-freeness and overlap-freeness of solid codes. Since a code is a language, we look at solid codes from formal language viewpoint. In particular, we study regular solid codes (that are solid codes and regular). We first tackle the solid code decidability problem for regular languages and propose a polynomial time algorithm. We, then, investigate the decidability of the overlap-freeness property and show that it is decidable for regular languages but is undecidable for context-free languages. Then, we study the prime solid code decomposition of regular solid codes and propose an efficient algorithm for the prime solid code decomposition problem. We also demonstrate that a solid code does not always have a unique prime solid code decomposition.<\/jats:p>","DOI":"10.1142\/s0129054111008647","type":"journal-article","created":{"date-parts":[[2011,8,10]],"date-time":"2011-08-10T09:42:53Z","timestamp":1312969373000},"page":"1197-1209","source":"Crossref","is-referenced-by-count":5,"title":["OVERLAP-FREE LANGUAGES AND SOLID CODES"],"prefix":"10.1142","volume":"22","author":[{"given":"YO-SUB","family":"HAN","sequence":"first","affiliation":[{"name":"Department of Computer Science, Yonsei University, Seoul 120-794, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"KAI","family":"SALOMAA","sequence":"additional","affiliation":[{"name":"School of Computing, Queen's University, Kingston, Ontario K7L 3N6, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","volume-title":"Theory of Codes","author":"Berstel J.","year":"1985"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"rf3","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2001"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103002151"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054106003887"},{"key":"rf6","doi-asserted-by":"crossref","first-page":"441","DOI":"10.3233\/FUN-2007-81404","volume":"81","author":"Han Y.-S.","journal-title":"Fundamenta Informaticae"},{"key":"rf7","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J.","year":"1979"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1080\/00207168908803768"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90026-2"},{"key":"rf11","first-page":"1033","volume":"206","author":"J\u00fcrgensen H.","journal-title":"Information and Control"},{"key":"rf12","doi-asserted-by":"crossref","unstructured":"H.\u00a0J\u00fcrgensen and S.\u00a0Konstantinidis, Word, Language, Grammar, Handbook of Formal Languages\u00a01, eds. G.\u00a0Rozenberg and A.\u00a0Salomaa (Springer-Verlag, 1997)\u00a0pp. 511\u2013607.","DOI":"10.1007\/978-3-642-59136-5_8"},{"key":"rf13","first-page":"375","volume":"29","author":"J\u00fcrgensen H.","journal-title":"Elektronische Informationsverarbeitung und Kybernetik"},{"key":"rf14","first-page":"563","volume":"26","author":"J\u00fcrgensen H.","journal-title":"Elektronische Informationsverarbeitung und Kybernetik"},{"key":"rf15","first-page":"88","volume":"6","author":"Levenshtein V. I.","journal-title":"Problemy Peredachi Informatsii"},{"key":"rf17","first-page":"339","volume":"15","author":"Mateescu A.","journal-title":"Acta Cybernetica"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1946-08555-9"},{"key":"rf19","first-page":"95","volume":"16","author":"Shyr H.","journal-title":"Soochow J. Math."},{"key":"rf20","volume-title":"Theory of Computation","author":"Wood D.","year":"1987"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054111008647","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T13:23:37Z","timestamp":1741440217000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054111008647"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,8]]},"references-count":18,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2011,8]]}},"alternative-id":["10.1142\/S0129054111008647"],"URL":"https:\/\/doi.org\/10.1142\/s0129054111008647","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,8]]}}}