Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Semigroup action
Résumé
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).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.