In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, an aperiodic semigroup is 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 (just notation, not necessarily th ...
''S'' such that every element is aperiodic, that is, for each ''x'' in ''S'' there exists a positive
integer
An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
''n'' such that ''x
n'' = ''x''
''n''+1.
An aperiodic monoid is an aperiodic semigroup which is a
monoid
In abstract algebra, 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 .
Monoids are semigroups with identity ...
.
Finite aperiodic semigroups
A finite semigroup is aperiodic
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
it contains no nontrivial
subgroup
In group theory, a branch of mathematics, a subset of a group G is a subgroup of G if the members of that subset form a group with respect to the group operation in G.
Formally, given a group (mathematics), group under a binary operation ...
s, so a synonym used (only?) in such contexts is group-free semigroup. In terms of
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 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 with close connections to cognitive science and mathematical l ...
due to
Marcel-Paul Schützenberger asserts that a language is
star-free if and only if its
syntactic monoid
In mathematics and computer science, the syntactic monoid M(L) of a formal language L is the minimal monoid that recognizes the language L. By the Myhill–Nerode theorem, the syntactic monoid is unique up to unique isomorphism.
Syntactic quot ...
is finite and aperiodic.
[Schützenberger, Marcel-Paul, "On finite monoids having only trivial subgroups," ''Information and Control'', Vol 8 No. 2, pp. 190–194, 1965.]
A consequence of the
Krohn–Rhodes theorem is that every finite aperiodic monoid divides a
wreath product
In group theory, the wreath product is a special combination of two groups based on the semidirect product. It is formed by the action of one group on many copies of another group, somewhat analogous to exponentiation. Wreath products are used ...
of copies of the
three-element flip-flop monoid, consisting of an identity element and two right zeros. The two-sided Krohn–Rhodes theorem alternatively characterizes finite aperiodic monoids as divisors of iterated block products of copies of the
two-element semilattice.
See also
*
Monogenic semigroup
*
Special classes of semigroups
References
*
Semigroup theory
{{Abstract-algebra-stub