The rank of a semigroup A of functions from a finite set X to X is the minimum of vertical bar f(X)vertical bar over f is an element of A. Given a finite set X and a subset Y of X, we show that if A is a semigroup of functions from X to X and B a transitive semigroup of functions from Y to Y, then the rank of A divides that of B provided that f (X) subset of Y for some f is an element of A and that each function in B is the restriction of a function in A to Y. To prove this, we generalize a result of Friedman which says that one can partition Y into q subsets of equal weight where q is the rank of B. When one extends a transitive automaton by adding new states and letters, a similar condition guarantees that the rank of the extension divides the original rank.

- Publisher
- SPRINGER

- Issue Date
- 2010-10

- Language
- English

- Article Type
- Article

- Keywords
ROAD-COLORING PROBLEM; AUTOMATA

- Citation
SEMIGROUP FORUM, v.81, no.2, pp.335 - 343

- ISSN
- 0037-1912

- Appears in Collection
- MA-Journal Papers(저널논문)

- Files in This Item

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