Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/111873
Full metadata record
DC FieldValueLanguage
dc.contributor.authorMargolis, S. W.en
dc.contributor.authorPin, J. -E.en
dc.contributor.authorVolkov, M. V.en
dc.date.accessioned2022-05-12T08:24:25Z-
dc.date.available2022-05-12T08:24:25Z-
dc.date.issued2004-
dc.identifier.citationMargolis S. W. Words Guaranteeing Minimum Image / S. W. Margolis, J. -E. Pin, M. V. Volkov // International Journal of Foundations of Computer Science. — 2004. — Vol. 15. — Iss. 2. — P. 259-276.en
dc.identifier.issn0129-0541-
dc.identifier.otherAll Open Access, Green3
dc.identifier.urihttp://hdl.handle.net/10995/111873-
dc.description.abstractGiven a positive integer n and a finite alphabet Σ, a word w over Σ is said to guarantee minimum image if, for every homomorphism φ from the free monoid Σ* over Σ into the monoid of all transformations of an n-element set, the range of the transformation wφ has the minimum cardinality among the ranges of all transformations of the form vφ where v runs over Σ*. 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(|Σ|(n3-n)). Then with some more effort, we find a word guaranteeing minimum image similar to that of Sauer and Stone but of length O(|Σ|(n2-n)). On the other hand, we prove that the length of any word guaranteeing minimum image cannot be less than |Σ|n-1. © 2004 World Scientific Publishing Company.en
dc.format.mimetypeapplication/pdfen
dc.language.isoenen
dc.publisherWorld Scientific Pub Co Pte Lten
dc.rightsinfo:eu-repo/semantics/openAccessen
dc.sourceInt. J. Found. Comput. Sci.2
dc.sourceInternational Journal of Foundations of Computer Scienceen
dc.titleWords Guaranteeing Minimum Imageen
dc.typeArticleen
dc.typeinfo:eu-repo/semantics/articleen
dc.typeinfo:eu-repo/semantics/submittedVersionen
dc.identifier.scopus11444266899-
local.contributor.employeeMargolis, S.W., Department of Mathematics and Computer Science, Bar Ilan University, 52900 Ramat Gan, Israel; Pin, J.-E., Laboratoire d'Informatique Algorithmique: Fondements et Applications, Université Paris Denis Diderot, CNRS, 75251 Paris, France; Volkov, M.V., Department of Mathematics and Mechanics, Ural State University, 620083 Ekaterinburg, Russian Federationen
local.description.firstpage259-
local.description.lastpage276-
local.issue2-
local.volume15-
local.contributor.departmentDepartment of Mathematics and Computer Science, Bar Ilan University, 52900 Ramat Gan, Israel; Laboratoire d'Informatique Algorithmique: Fondements et Applications, Université Paris Denis Diderot, CNRS, 75251 Paris, France; Department of Mathematics and Mechanics, Ural State University, 620083 Ekaterinburg, Russian Federationen
local.identifier.eid2-s2.0-11444266899-
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-11444266899.pdf184,76 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.