an S-homomorphism from X to X′ is a map such that for all and . The set of all such S-homomorphisms is commonly written as . M-homomorphisms of M-acts, for M a monoid, are defined in exactly the same way. S-Act and M-Act For a fixed semigroup S, the left S-acts are the objects of a category, denoted S-Act, whose morphisms are the S-homomorphisms. The corresponding category of right S-acts is sometimes denoted by Act-S. (This is analogous to the categories R-Mod and Mod-R of left and right modules over a ring.) For a monoid M, the categories M-Act and Act-M are defined in the same way. Examples Any semigroup has an action on , where . The action property holds due to the associativity of . More generally, for any semigroup homomorphism , the semigroup has an action on given by . For any set , let be the set of sequences of elements of . The semigroup has an action on given by (where denotes repeated times). The semigroup has a right action , given by . Transformation semigroups A correspondence between transformation semigroups and semigroup actions is described below. If we restrict it to faithful semigroup actions, it has nice properties. Any transformation semigroup can be turned into a semigroup action by the following construction. For any transformation semigroup of , define a semigroup action of on as for . This action is faithful, which is equivalent to being injective. Conversely, for any semigroup action of on , define a transformation semigroup . In this construction we "forget" the set . is equal to the image of . Let us denote as for brevity. If is injective, then it is a semigroup isomorphism from to . In other words, if is faithful, then we forget nothing important. This claim is made precise by the following observation: if we turn back into a semigroup action of on , then for all . and are "isomorphic" via , i.e., we essentially recovered . Thus some authors see no distinction between faithful semigroup actions and transformation semigroups. Applications to computer science Semiautomata Transformation semigroups are of essential importance for the structure theory of finite state machines in automata theory. In particular, a semiautomaton is a triple (Σ,X,T), where Σ is a non-empty set called the input alphabet, X is a non-empty set called the set of states and T is