{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T08:29:31Z","timestamp":1676968171350},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2006,6]]},"abstract":"<jats:p> We study a fundamental combinatorial problem on morphisms in free semigroups: With regard to any string \u03b1 over some alphabet we ask for the existence of a morphism \u03c3 such that \u03c3(\u03b1) is unambiguous, i.e. there is no morphism \u03c4 with \u03c4(i) \u2260 \u03c3(i) for some symbol i in \u03b1 and, nevertheless, \u03c4(\u03b1) = \u03c3(\u03b1). As a consequence of its elementary nature, this question shows a variety of connections to those topics in discrete mathematics which are based on finite strings and morphisms such as pattern languages, equality sets and, thus, the Post Correspondence Problem. <\/jats:p><jats:p> Our studies demonstrate that the existence of unambiguous morphic images essentially depends on the structure of \u03b1: We introduce a partition of the set of all finite strings into those that are decomposable (referred to as prolix) in a particular manner and those that are indecomposable (called succinct). This partition, that is also known to be of major importance for the research on pattern languages and on finite fixed points of morphisms, allows to formulate our main result according to which a string \u03b1 can be mapped by an injective morphism onto an unambiguous image if and only if \u03b1 is succinct. <\/jats:p>","DOI":"10.1142\/s0129054106004017","type":"journal-article","created":{"date-parts":[[2006,6,6]],"date-time":"2006-06-06T07:11:37Z","timestamp":1149577897000},"page":"601-628","source":"Crossref","is-referenced-by-count":25,"title":["UNAMBIGUOUS MORPHIC IMAGES OF STRINGS"],"prefix":"10.1142","volume":"17","author":[{"given":"DOMINIK D.","family":"FREYDENBERGER","sequence":"first","affiliation":[{"name":"Fachbereich Informatik, Technische Universit\u00e4t Kaiserslautern, Postfach 3049, 67653 Kaiserslautern, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DANIEL","family":"REIDENBACH","sequence":"additional","affiliation":[{"name":"Fachbereich Informatik, Technische Universit\u00e4t Kaiserslautern, Postfach 3049, 67653 Kaiserslautern, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JOHANNES C.","family":"SCHNEIDER","sequence":"additional","affiliation":[{"name":"Fachbereich Informatik, Technische Universit\u00e4t Kaiserslautern, Postfach 3049, 67653 Kaiserslautern, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90041-0"},{"key":"rf2","volume-title":"Theory of Codes","author":"Berstel J.","year":"1985"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_6"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)91165-5"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_7"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1080\/00207168108803273"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037093"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.01.011"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00064-X"},{"key":"rf11","volume-title":"Combinatorics on Words","author":"Lothaire M.","year":"1983"},{"key":"rf12","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1051\/ita\/1994283-402331","volume":"28","author":"Mateescu A.","journal-title":"RAIRO Informatique th\u00e9'oretique et Applications"},{"key":"rf13","doi-asserted-by":"crossref","unstructured":"A.\u00a0Mateescu and A.\u00a0Salomaa, Handbook of Formal Languages\u00a01, eds. G.\u00a0Rozenberg and A.\u00a0Salomaa (Springer, 1997)\u00a0pp. 230\u2013242.","DOI":"10.1007\/978-3-642-59136-5_1"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1946-08555-9"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.017"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054106004017","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:28:21Z","timestamp":1565177301000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054106004017"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,6]]},"references-count":14,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2006,6]]}},"alternative-id":["10.1142\/S0129054106004017"],"URL":"https:\/\/doi.org\/10.1142\/s0129054106004017","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,6]]}}}