A note on the rank of semigroups

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 269
  • Download : 1
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
DOI
10.1007/s00233-010-9225-2
URI
http://hdl.handle.net/10203/96556
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0