Sources
Help build the largest human-edited directory on the web.
Submit a site - Become an editor
Wikipedia. Licensed under the GNU Free Documentation License.
Are you an expert in this subject? Join the discussion and share your knowledge at Wikipedia.org.
Aperiodic monoid
From Wikipedia, the free 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.
