Please use this identifier to cite or link to this item:
|Title:||Words Guaranteeing Minimum Image|
|Authors:||Margolis, S. W.|
Pin, J. -E.
Volkov, M. V.
|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.|
|Appears in Collections:||Научные публикации, проиндексированные в SCOPUS и WoS CC|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.