Words guaranteeing minimum image / Margolis SW,Pin JE,Volkov MV // INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE. - 2004. - V. 15, l. 2. - P. 259-276.

ISSN/EISSN:

0129-0541 / нет данных

Type:

Article

Abstract:

Given a positive integer n and a finite alphabet Sigma, a word w over Sigma is said to guarantee minimum image if, for every homomorphism phi from the free monoid Sigma{*} over Sigma into the monoid of all transformations of an n-element set, the range of the transformation wphi has the minimum cardinality among the ranges of all transformations of the form vphi where v runs over Sigma{*}. 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(\textbackslash{}Sigma1/2((n2-n))). Then with some more effort, we find a word guaranteeing minimum image similar to that of Sauer and Stone but of length O(\textbackslash{}Sigma1/2((n2-n))). On the other hand, we prove that the length of any word guaranteeing minimum image cannot be less than /Sigma/(n-1).

Author keywords:

COMPUTING MACHINE; AUTOMATA; LENGTH

DOI:

10.1142/S0129054104002406

Web of Science ID:

ISI:000227176000003

Соавторы в МНС:

—

Другие поля

Поле	Значение
Month	APR
Publisher	WORLD SCIENTIFIC PUBL CO PTE LTD
Address	5 TOH TUCK LINK, SINGAPORE 596224, SINGAPORE
Language	English
Keywords-Plus	COMPUTING MACHINE; AUTOMATA; LENGTH
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Theory \& Methods
Author-Email	margolis@macs.biu.ac.il Jean-Eric.Pin@liafa.jussieu.fr Mikhail.Volkov@usu.ru
ResearcherID-Numbers	Volkov, Mikhail/F-1407-2014
ORCID-Numbers	Volkov, Mikhail/0000-0002-9327-243X
Number-of-Cited-References	32
Usage-Count-Since-2013	2
Journal-ISO	Int. J. Found. Comput. Sci.
Doc-Delivery-Number	899WH