Aperiodic monoid
Encyclopedia
In mathematics
, an aperiodic semigroup is a semigroup
S such that for every x ∈ S, there exists a nonnegative integer n such that
xn = xn + 1.
An aperiodic monoid is an aperiodic semigroup which is a monoid
. This notion is in some sense orthogonal to that of group
.
Recall that a subsemigroup
G of a semigroup S is a subgroup of S (also called sometimes a group in S) if there exists an idempotent e such that G is a group with identity element e. A semigroup S is group-bound if some power of each element of S lies in some subgroup
of S. Every finite semigroup is group-bound, but a group-bound semigroup might be infinite.
A finite semigroup is aperiodic if and only if it contains no nontrivial subgroups
. In terms of Green's relations
, a finite semigroup is aperiodic if and only if its H-relation is trivial. These two characterizations extend to group-bound semigroups.
A celebrated result of algebraic automata theory
due to Marcel-Paul Schützenberger
asserts that a language is star-free
if and only if its syntactic monoid
is finite and aperiodic.
A consequence of the Krohn-Rhodes theorem
is that every finite aperiodic monoid divides a wreath product
of copies of the three element monoid containing an identity element and two right zeros.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, an aperiodic semigroup is 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...
S such that for every x ∈ S, there exists a nonnegative integer n such that
xn = xn + 1.
An aperiodic monoid is an aperiodic semigroup which 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...
. This notion is in some sense orthogonal to that of group
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...
.
Recall that a subsemigroup
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...
G of a semigroup S is a subgroup of S (also called sometimes a group in S) if there exists an idempotent e such that G is a group with identity element e. A semigroup S is group-bound if some power of each element of S lies in some subgroup
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...
of S. Every finite semigroup is group-bound, but a group-bound semigroup might be infinite.
A finite semigroup is aperiodic if and only if it contains no nontrivial subgroups
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...
. In terms of Green's relations
Green's relations
In mathematics, Green's relations are five equivalence relations that characterise the elements of a semigroup in terms of the principal ideals they generate. The relations are named for James Alexander Green, who introduced them in a paper of 1951...
, a finite semigroup is aperiodic if and only if its H-relation is trivial. These two characterizations extend to group-bound semigroups.
A celebrated result of algebraic 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...
due to Marcel-Paul Schützenberger
Marcel-Paul Schützenberger
Marcel-Paul "Marco" Schützenberger was a French mathematician and Doctor of Medicine. His work had impact across the fields of formal language, combinatorics, and information theory...
asserts that a language is star-free
Star-free language
A regular language is said to be star-free if it can be described by a regular expression constructed from the letters of the alphabet, the empty set symbol, all boolean operators – including complementation – and concatenation but no Kleene star...
if and only if its syntactic monoid
Syntactic monoid
In mathematics and computer science, the syntactic monoid M of a formal language L is the smallest monoid that recognizes the language L.-Syntactic quotient:...
is finite and aperiodic.
A consequence of the Krohn-Rhodes theorem
Krohn-Rhodes theory
In mathematics and computer science, the Krohn–Rhodes theory is an approach to the study of finite semigroups and automata that seeks to decompose them in terms of elementary components...
is that every finite aperiodic monoid divides a wreath product
Wreath product
In mathematics, the wreath product of group theory is a specialized product of two groups, based on a semidirect product. Wreath products are an important tool in the classification of permutation groups and also provide a way of constructing interesting examples of groups.Given two groups A and H...
of copies of the three element monoid containing an identity element and two right zeros.