{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T08:15:32Z","timestamp":1649146532511},"reference-count":25,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2004,4]]},"abstract":"<jats:p> Given a positive integer n and a finite alphabet \u03a3, a word w over \u03a3 is said to guarantee minimum image if, for every homomorphism \u03c6 from the free monoid \u03a3* over \u03a3 into the monoid of all transformations of an n-element set, the range of the transformation w\u03c6 has the minimum cardinality among the ranges of all transformations of the form v\u03c6 where v runs over \u03a3*. Although the existence of words guaranteeing minimum image is pretty obvious, the problem of their explicit description is very far from being trivial. Sauer and Stone in 1991 gave a recursive construction for such a word w but the length of their word was doubly exponential (as a function of n). We first show that some known results of automata theory immediately lead to an alternative construction that yields a simpler word that guarantees minimum image: it has exponential length, more precisely, its length is O(|\u03a3|<jats:sup>\u2159(n<jats:sup>3<\/jats:sup>-n)<\/jats:sup>). Then with some more effort, we find a word guaranteeing minimum image similar to that of Sauer and Stone but of length O(|\u03a3|<jats:sup>\u00bd(n<jats:sup>2<\/jats:sup>-n)<\/jats:sup>). On the other hand, we prove that the length of any word guaranteeing minimum image cannot be less than |\u03a3|<jats:sup>n-1<\/jats:sup>. <\/jats:p>","DOI":"10.1142\/s0129054104002406","type":"journal-article","created":{"date-parts":[[2004,4,22]],"date-time":"2004-04-22T13:19:46Z","timestamp":1082639986000},"page":"259-276","source":"Crossref","is-referenced-by-count":14,"title":["WORDS GUARANTEEING MINIMUM IMAGE"],"prefix":"10.1142","volume":"15","author":[{"given":"S. W.","family":"MARGOLIS","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science,  Bar Ilan University, 52900 Ramat Gan, Israel"}]},{"given":"J.-E.","family":"PIN","sequence":"additional","affiliation":[{"name":"Laboratoire d'Informatique Algorithmique:  Fondements et Applications, Universit\u00e9 Paris Denis Diderot et  CNRS, 75251 Paris, France"}]},{"given":"M. V.","family":"VOLKOV","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Mechanics,  Ural State University, 620083 Ekaterinburg, Russia"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","volume-title":"The design and analysis of computer algorithms","author":"Aho A. V.","year":"1974"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1142\/S0219498803000519"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00093-8"},{"key":"rf6","volume-title":"El\u00e9ments d'algorithmique","author":"Beauquier D.","year":"1994"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1038\/35106533"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0535624100"},{"key":"rf9","volume-title":"Text algorithms","author":"Crochemore M.","year":"1994"},{"key":"rf10","first-page":"208","volume":"14","author":"\u010cern\u00fd J.","journal-title":"Mat.-Fyz. Cas. Slovensk. Akad. Vied."},{"key":"rf11","first-page":"289","volume":"7","author":"\u010cern\u00fd J.","journal-title":"Kybernetika, Praha"},{"key":"rf13","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1051\/ita\/1996300604951","volume":"30","author":"Dubuc L.","journal-title":"RAIRO, Inform. Theor. Appl."},{"key":"rf14","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1051\/ita\/1998321-300211","volume":"32","author":"Dubuc L.","journal-title":"RAIRO Inform. Theor. Appl."},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1137\/0219033"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(82)80025-5"},{"key":"rf17","first-page":"181","volume":"6","author":"Ito M.","journal-title":"Acta Cybernetica"},{"key":"rf18","first-page":"146","volume":"73","author":"Kari J.","journal-title":"EATCS Bull."},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"rf21","first-page":"16","author":"Klyachko A. A.","journal-title":"Kibernetika"},{"key":"rf22","doi-asserted-by":"crossref","unstructured":"E. F.\u00a0Moore, Automata Studies, eds. C. E.\u00a0Shannon and J.\u00a0McCarthy (Princeton University Press, 1956)\u00a0pp. 129\u2013153.","DOI":"10.1515\/9781400882618-006"},{"key":"rf23","first-page":"233","volume":"12","author":"Perles M.","journal-title":"IEEE Trans. Electron. Comput."},{"key":"rf27","first-page":"283","volume":"14","author":"Pin J.-E.","journal-title":"Elektron. Informationverarbeitung und Kybernetik"},{"key":"rf28","first-page":"535","volume":"17","author":"Pin J.-E.","journal-title":"Ann. Discrete Math."},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1007\/BF01236507"},{"key":"rf30","first-page":"40","author":"Rystsov I. K.","journal-title":"Kibernetika i Sistemnyj Analiz"},{"key":"rf31","first-page":"145","volume":"12","author":"Rystsov I. K.","journal-title":"Acta Cybern."},{"key":"rf32","first-page":"171","volume":"31","author":"Sauer N.","journal-title":"Ars Combinatoria"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054104002406","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:37:18Z","timestamp":1565138238000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054104002406"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,4]]},"references-count":25,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2004,4]]}},"alternative-id":["10.1142\/S0129054104002406"],"URL":"https:\/\/doi.org\/10.1142\/s0129054104002406","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,4]]}}}