aperiodic semigroup
   HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, an aperiodic semigroup is a
semigroup In mathematics, a semigroup is an algebraic structure In mathematics, an algebraic structure consists of a nonempty Set (mathematics), set ''A'' (called the underlying set, carrier set or domain), a collection of operation (mathematics), opera ...
''S'' such that every element ''x'' ∈ ''S'' is aperiodic, that is, for each ''x'' there exists a
positive integer In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...
''n'' such that ''x''''n'' = ''x''''n'' + 1. An aperiodic monoid is an aperiodic semigroup which 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 ar ...
.


Finite aperiodic semigroups

A finite semigroup is aperiodic if and only if it contains no nontrivial
subgroup In group theory, a branch of mathematics, given a group (mathematics), group ''G'' under a binary operation ∗, a subset ''H'' of ''G'' is called a subgroup of ''G'' if ''H'' also forms a group under the operation ∗. More precisely, ...
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 automaton, 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 αὐτ ...
due to Marcel-Paul Schützenberger asserts that a language is star-free if and only if its
syntactic monoid In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in mode ...
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 Group (mathematics), groups based on the semidirect product. It is formed by the Action (group theory), action of one group on many copies of another group, somewhat analogous to ...
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 In mathematics, a semigroup is a nonempty set together with an associative binary operation. A special class of semigroups is a Class (set theory), class of semigroups satisfying additional property (philosophy), properties or conditions. Thus the ...


References

* Semigroup theory {{Abstract-algebra-stub