In
algebra
Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics.
Elementary a ...
and
theoretical computer science
computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumscribe the ...
, an action or act of a
semigroup
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.
The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'' ...
on a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
is a rule which associates to each element of the semigroup a
transformation
Transformation may refer to:
Science and mathematics
In biology and medicine
* Metamorphosis, the biological process of changing physical form after birth or hatching
* Malignant transformation, the process of cells becoming cancerous
* Trans ...
of the set in such a way that the product of two elements of the semigroup (using the semigroup
operation
Operation or Operations may refer to:
Arts, entertainment and media
* ''Operation'' (game), a battery-operated board game that challenges dexterity
* Operation (music), a term used in musical set theory
* ''Operations'' (magazine), Multi-Man ...
) is associated with the
composite
Composite or compositing may refer to:
Materials
* Composite material, a material that is made from several different substances
** Metal matrix composite, composed of metal and other parts
** Cermet, a composite of ceramic and metallic materials ...
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
In abstract algebra, group theory studies the algebraic structures known as groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces, can all be seen as ...
. From the computer science point of view, semigroup actions are closely related to
automata
An automaton (; plural: automata or automatons) is a relatively self-operating machine, or control mechanism designed to automatically follow a sequence of operations, or respond to predetermined instructions.Automaton – Definition and More ...
: 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
In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.
Monoids a ...
and the
identity element
In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures ...
of the monoid acts as the
identity transformation
Graph of the identity function on the real numbers
In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, unc ...
of a set. From a
category theoretic
Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, categ ...
point of view, a monoid is a
category
Category, plural categories, may refer to:
Philosophy and general uses
*Categorization, categories in cognitive science, information science and generally
*Category of being
* ''Categories'' (Aristotle)
*Category (Kant)
*Categories (Peirce)
*C ...
with one object, and an act is a functor from that category to the
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 the total functions from ''A'' to ''B'', and the composition of ...
. 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
In group theory, Cayley's theorem, named in honour of Arthur Cayley, states that every group is isomorphic to a subgroup of a symmetric group.
More specifically, is isomorphic to a subgroup of the symmetric group \operatorname(G) whose element ...
.
''(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 which is compatible with the semigroup
operation
Operation or Operations may refer to:
Arts, entertainment and media
* ''Operation'' (game), a battery-operated board game that challenges dexterity
* Operation (music), a term used in musical set theory
* ''Operations'' (magazine), Multi-Man ...
∗ as follows:
* for all ''s'', ''t'' in ''S'' and ''x'' in ''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 satisfying .
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 () as empty when there is no identity element, or by using the term unitary ''S''-act for an ''S''-act with an identity.
The defining property of an act is analogous to the
associativity
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement ...
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 semigroup, which has the same elements as S, but where multiplication is defined by reversing the factors, , 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 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
In mathematics and computer science, currying is the technique of translating the evaluation of a function that takes multiple arguments into evaluating a sequence of functions, each with a single argument. For example, currying a function f th ...
''). 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
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
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
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
.)
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
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
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
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματ� ...
. 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 ''T''
''a'': ''X'' → ''X'', for ''a'' ∈ Σ, denote the transformation of ''X'' defined by ''T''
''a''(''x'') = ''T''(''a'',''x''). Then the semigroup of transformations of ''X'' generated by 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 In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero elem ...
of strings generated by the alphabet Σ,
[The monoid operation is concatenation; the identity element is the empty string.] and the action of strings extends the action of Σ via the property
:
Krohn–Rhodes theory
Krohn–Rhodes theory, sometimes also called ''algebraic automata theory'', gives powerful decomposition results for finite transformation semigroups by cascading simpler components.
Notes
References
*
A. H. Clifford and
G. B. Preston
Gordon Bamford Preston (28 April 1925 – 14 April 2015) was an English mathematician best known for his work on semigroups. He received his D.Phil. in mathematics in 1954 from Magdalen College, Oxford.
He was born in Workington and brough ...
(1961), ''The Algebraic Theory of Semigroups'', volume 1. American Mathematical Society, .
* A. H. Clifford and G. B. Preston (1967), ''The Algebraic Theory of Semigroups'', volume 2. American Mathematical Society, .
* 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, .
* Rudolf Lidl and Günter Pilz, ''Applied Abstract Algebra'' (1998), Springer, {{isbn, 978-0-387-98290-8
Semigroup theory
Theoretical computer science