Transformation semigroup
Encyclopedia
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 of 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.)
* as follows:
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).
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
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.
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. However, every right S-act can be interpreted as a left act over the opposite monoid, which has the same elements as S, but where multiplication is defined by reversing the factors, s•t = t•s, so the two notions are essentially equivalent. Here we primarily adopt the point of view of left acts.
, 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 satisfies
I.e.
is a semigroup action of 
on 
iff 
is a semigroup homomorphism from 
to the full transformation monoid of 
.
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.
over a ring
.)
For a monoid M, the categories M-Act and Act-M are defined in the same way.
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
. Lets denote 
as 
for brevity. If 
is injective, then 
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.
s 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: X → X, for a ∈ Σ, denote the transformation of X defined by Ta(x) = T(a,x). Then semigroup of transformations of X generated by {Ta : a ∈ Σ} is called the characteristic semigroup or transition system of (Σ,X,T). The corresponding monoid is called the characteristic or transition monoid. It is also sometimes viewed as an Σ∗-act on X, where Σ∗ is the free monoid of strings generated by the alphabet Σ and the action of strings extends the action of Σ via the property
Algebra
Algebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from them, including terms, polynomials, equations and algebraic structures...
and theoretical computer science
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
, an action or act of a semigroup
Semigroup
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation. A semigroup generalizes a monoid in that there might not exist an identity element...
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
Binary operation
In mathematics, a binary operation is a calculation involving two operands, in other words, an operation whose arity is two. Examples include the familiar arithmetic operations of addition, subtraction, multiplication and division....
) is associated with the composite
Function composition
In mathematics, function composition is the application of one function to the results of another. For instance, the functions and can be composed by computing the output of g when it has an argument of f instead of x...
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
Algebraic structure
In abstract algebra, an algebraic structure consists of one or more sets, called underlying sets or carriers or sorts, closed under one or more operations, satisfying some axioms. Abstract algebra is primarily the study of algebraic structures and their properties...
perspective, a semigroup action is a generalization of the notion of a group action
Group action
In algebra and geometry, a group action is a way of describing symmetries of objects using groups. The essential elements of the object are described by a set, and the symmetries of the object are described by the symmetry group of this set, which consists of bijective transformations of the set...
in group theory
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
. From the computer science point of view, semigroup actions are closely related to automata
Finite state machine
A finite-state machine or finite-state automaton , or simply a state machine, is a mathematical model used to design computer programs and digital logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states...
: 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
Monoid
In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...
and the identity element
Identity element
In mathematics, an identity element is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them...
of the monoid acts as the identity transformation of a set. From a category theoretic point of view, a monoid is a category
Category (mathematics)
In mathematics, a category is an algebraic structure that comprises "objects" that are linked by "arrows". A category has two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow for each object. A simple example is the category of sets, whose...
with one object, and an act is a functor from that category to the category of sets
Category of sets
In the mathematical field of category theory, the category of sets, denoted as Set, is the category whose objects are sets. The arrows or morphisms between sets A and B are all functions from A to B...
. 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
Transformation semigroup
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 is associated with the composite of the two corresponding...
. This is a semigroup of transformations of a set, and hence it has a tautological action of on that set. This concept is linked to the more general notion of a semigroup by an analogue of Cayley's theorem
Cayley's theorem
In group theory, Cayley's theorem, named in honor of Arthur Cayley, states that every group G is isomorphic to a subgroup of the symmetric group acting on G...
.
(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
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 operationBinary operation
In mathematics, a binary operation is a calculation involving two operands, in other words, an operation whose arity is two. Examples include the familiar arithmetic operations of addition, subtraction, multiplication and division....
* 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
Group action
In algebra and geometry, a group action is a way of describing symmetries of objects using groups. The essential elements of the object are described by a set, and the symmetries of the object are described by the symmetry group of this set, which consists of bijective transformations of the set...
, 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).
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: e • x = 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
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 (e • x = x) as empty when there is no identity element, or by using the term unitary S-act for an S-act with an identity. Furthermore, since a monoid is a semigroup, one can consider semigroup actions of monoids.The defining property of an act is analogous to the associativity
Associativity
In mathematics, associativity is a property of some binary operations. It means that, within an expression containing two or more occurrences in a row of the same associative operator, the order in which the operations are performed does not matter as long as the sequence of the operands is not...
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
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
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. However, every right S-act can be interpreted as a left act over the opposite monoid, which has the same elements as S, but where multiplication is defined by reversing the factors, s•t = t•s, so the two notions are essentially equivalent. Here we primarily adopt the point of view of left acts.
Acts and transformations
It is often convenient (for instance if there is more than one act under consideration) to use a letter, such as, to denote the functiondefining the
-action and hence write in place of . Then for any in , we denote bythe transformation of
defined byBy the defining property of an
-act, satisfiesFurther, consider a function
. It is the same as (see curryingCurrying
In mathematics and computer science, currying is the technique of transforming a function that takes multiple arguments in such a way that it can be called as a chain of functions each with a single argument...
). Because
is a bijection, semigroup actions can be defined as functions which satisfiesI.e.
is a semigroup action of on iff is a semigroup homomorphism from to the full transformation monoid of .S-homomorphisms
Let X and X′ be S-acts. Then an S-homomorphism from X to X′ is a mapsuch 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 modulesModule (mathematics)
In abstract algebra, the concept of a module over a ring is a generalization of the notion of vector space, wherein the corresponding scalars are allowed to lie in an arbitrary ring...
over a ring
Ring (mathematics)
In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...
.)
For a monoid M, the categories M-Act and Act-M are defined in the same way.
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 imageImage (mathematics)
In mathematics, an image is the subset of a function's codomain which is the output of the function on a subset of its domain. Precisely, evaluating the function at each element of a subset X of the domain produces a set called the image of X under or through the function...
of
. Lets denote as for brevity. If is injective, then is a semigroup isomorphismIsomorphism
In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations. If there exists an isomorphism between two structures, the two structures are said to be isomorphic. In a certain sense, isomorphic structures are...
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.Semiautomata
Transformation semigroups are of essential importance for the structure theory of finite state machineFinite state machine
A finite-state machine or finite-state automaton , or simply a state machine, is a mathematical model used to design computer programs and digital logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states...
s in automata theory
Automata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
. 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
Deterministic finite state machine
In the theory of computation and automata theory, a deterministic finite state machine—also known as deterministic finite automaton —is a finite state machine accepting finite strings of symbols. For each state, there is a transition arrow leading out to a next state for each symbol...
by ignoring the initial state and the set of accept states.
Given a semiautomaton, let Ta: X → X, for a ∈ Σ, denote the transformation of X defined by Ta(x) = T(a,x). Then semigroup of transformations of X generated by {Ta : a ∈ Σ} is called the characteristic semigroup or transition system of (Σ,X,T). The corresponding monoid is called the characteristic or transition monoid. It is also sometimes viewed as an Σ∗-act on X, where Σ∗ is the free monoid of strings generated by the alphabet Σ and the action of strings extends the action of Σ via the property