Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/111873
Title: Words Guaranteeing Minimum Image
Authors: Margolis, S. W.
Pin, J. -E.
Volkov, M. V.
Issue Date: 2004
Publisher: World Scientific Pub Co Pte Lt
Citation: Margolis 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.
Abstract: Given 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.
URI: http://hdl.handle.net/10995/111873
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 11444266899
ISSN: 0129-0541
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.