Semigroup action

(Redirected from S-act)

In algebra and theoretical computer science, an action or act of a semigroup on a set is a rule which associates to each element of the semigroup a transformation of the set in such a way that the product of two elements of the semigroup (using the semigroup operation) is associated with the composite of the two corresponding transformations. The terminology conveys the idea that the elements of the semigroup are acting as transformations of the set. From an algebraic perspective, a semigroup action is a generalization of the notion of a group action in group theory. From the computer science point of view, semigroup actions are closely related to automata: the set models the state of the automaton and the action models transformations of that state in response to inputs.

An important special case is a monoid action or act, in which the semigroup is a monoid and the identity element of the monoid acts as the identity transformation of a set. From a category theoretic point of view, a monoid is a category with one object, and an act is a functor from that category to the category of sets. This immediately provides a generalization to monoid acts on objects in categories other than the category of sets.

Another important special case is a transformation semigroup. This is a semigroup of transformations of a set, and hence it has a tautological action on that set. This concept is linked to the more general notion of a semigroup by an analogue of Cayley's theorem.

(A note on terminology: the terminology used in this area varies, sometimes significantly, from one author to another. See the article for details.)

Formal definitions

edit

Let S be a semigroup. Then a (left) semigroup action (or act) of S is a set X together with an operation • : S × XX which is compatible with the semigroup operation ∗ as follows:

  • for all s, t in S and x in X, s • (tx) = (st) • x.

This is the analogue in semigroup theory of a (left) group action, and is equivalent to a semigroup homomorphism into the set of functions on X. Right semigroup actions are defined in a similar way using an operation • : X × SX satisfying (xa) • b = x • (ab).

If M is a monoid, then a (left) monoid action (or act) of M is a (left) semigroup action of M with the additional property that

  • for all x in X: ex = x

where e is the identity element of M. This correspondingly gives a monoid homomorphism. Right monoid actions are defined in a similar way. A monoid M with an action on a set is also called an operator monoid.

A semigroup action of S on X can be made into monoid act by adjoining an identity to the semigroup and requiring that it acts as the identity transformation on X.

Terminology and notation

edit

If S is a semigroup or monoid, then a set X on which S acts as above (on the left, say) is also known as a (left) S-act, S-set, S-action, S-operand, or left act over S. Some authors do not distinguish between semigroup and monoid actions, by regarding the identity axiom (ex = x) as empty when there is no identity element, or by using the term unitary S-act for an S-act with an identity.[1]

The defining property of an act is analogous to the associativity of the semigroup operation, and means that all parentheses can be omitted. It is common practice, especially in computer science, to omit the operations as well so that both the semigroup operation and the action are indicated by juxtaposition. In this way strings of letters from S act on X, as in the expression stx for s, t in S and x in X.

It is also quite common to work with right acts rather than left acts.[2] However, every right S-act can be interpreted as a left act over the opposite semigroup, which has the same elements as S, but where multiplication is defined by reversing the factors, st = ts, so the two notions are essentially equivalent. Here we primarily adopt the point of view of left acts.

Acts and transformations

edit

It is often convenient (for instance if there is more than one act under consideration) to use a letter, such as  , to denote the function

 

defining the  -action and hence write   in place of  . Then for any   in  , we denote by

 

the transformation of   defined by

 

By the defining property of an  -act,   satisfies

 

Further, consider a function  . It is the same as   (see Currying). Because   is a bijection, semigroup actions can be defined as functions   which satisfy

 

That is,   is a semigroup action of   on   if and only if   is a semigroup homomorphism from   to the full transformation monoid of  .

S-homomorphisms

edit

Let X and X′ be S-acts. Then 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

edit

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

edit
  • 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

edit

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[3] see no distinction between faithful semigroup actions and transformation semigroups.

Applications to computer science

edit

Semiautomata

edit

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 a function

 

called the transition function. Semiautomata arise from deterministic automata by ignoring the initial state and the set of accept states.

Given a semiautomaton, let Ta: XX, for a ∈ Σ, denote the transformation of X defined by Ta(x) = T(a,x). Then the semigroup of transformations of X generated by {Ta : a ∈ Σ} is called the characteristic semigroup or transition system of (Σ,X,T). This semigroup is a monoid, so this monoid is called the characteristic or transition monoid. It is also sometimes viewed as a Σ-act on X, where Σ is the free monoid of strings generated by the alphabet Σ,[note 1] and the action of strings extends the action of Σ via the property

 

Krohn–Rhodes theory

edit

Krohn–Rhodes theory, sometimes also called algebraic automata theory, gives powerful decomposition results for finite transformation semigroups by cascading simpler components.

Notes

edit
  1. ^ The monoid operation is concatenation; the identity element is the empty string.

References

edit
  1. ^ Kilp, Knauer and Mikhalev, 2000, pages 43–44.
  2. ^ Kilp, Knauer and Mikhalev, 2000.
  3. ^ Arbib, Michael A., ed. (1968). Algebraic Theory of Machines, Languages, and Semigroups. New York and London: Academic Press. p. 83.
  • A. H. Clifford and G. B. Preston (1961), The Algebraic Theory of Semigroups, volume 1. American Mathematical Society, ISBN 978-0-8218-0272-4.
  • A. H. Clifford and G. B. Preston (1967), The Algebraic Theory of Semigroups, volume 2. American Mathematical Society, ISBN 978-0-8218-0272-4.
  • Mati Kilp, Ulrich Knauer, Alexander V. Mikhalev (2000), Monoids, Acts and Categories: with Applications to Wreath Products and Graphs, Expositions in Mathematics 29, Walter de Gruyter, Berlin, ISBN 978-3-11-015248-7.
  • Rudolf Lidl and Günter Pilz, Applied Abstract Algebra (1998), Springer, ISBN 978-0-387-98290-8