Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Semigroup action
Summary
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 point of view, a monoid is a with one object, and an act is a functor from that category to the . 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.)
Let S be a semigroup. Then a (left) semigroup action (or act) of S is a set X together with an operation • : S × X → X which is compatible with the semigroup operation ∗ as follows:
for all s, t in S and x in X, s • (t • x) = (s ∗ t) • 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 × S → X satisfying (x • a) • b = x • (a ∗ b).
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.