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 elements, often called the empty string and denoted by ε or λ, as the identity element.

The free semigroup on A is the subsemigroup of A∗ containing all elements except the empty string.

[3] As the name implies, free monoids and semigroups are those objects which satisfy the usual universal property defining free objects, in the respective categories of monoids and semigroups.

The monoid (N0,+) of natural numbers (including zero) under addition is a free monoid on a singleton free generator, in this case, the natural number 1.

In formal language theory, usually a finite set of "symbols" A (sometimes called the alphabet) is considered.

For example, assuming an alphabet A = {a, b, c}, its Kleene star A∗ contains all concatenations of a, b, and c: If A is any set, the word length function on A∗ is the unique monoid homomorphism from A∗ to (N0,+) that maps each element of A to 1.

because, in general, set unions might not be monoids, and so a distinct symbol is used.

For the case of a regular language, that monoid is isomorphic to the transition monoid associated to the semiautomaton of some deterministic finite automaton that recognizes that language.

The regular languages over an alphabet A are the closure of the finite subsets of A*, the free monoid over A, under union, product, and generation of submonoid.

[6] For the case of concurrent computation, that is, systems with locks, mutexes or thread joins, the computation can be described with history monoids and trace monoids.

Roughly speaking, elements of the monoid can commute, (e.g. different threads can execute in any order), but only up to a lock or mutex, which prevent further commutation (e.g. serialize thread access to some object).

[8] A free monoid is equidivisible: if the equation mn = pq holds, then there exists an s such that either m = ps, sn = q (example see image) or ms = p, n = sq.

[10] A monoid is free if and only if it is graded (in the strong sense that only the identity has gradation 0) and equidivisible.

More generally, if S is an abstract free monoid (semigroup), then a set of elements which maps onto the set of single-letter words under an isomorphism to a monoid A∗ (semigroup A+) is called a set of free generators for S. Each free monoid (or semigroup) S has exactly one set of free generators, the cardinality of which is called the rank of S. Two free monoids or semigroups are isomorphic if and only if they have the same rank.

[14] A factorization of a free monoid is a sequence of subsets of words with the property that every word in the free monoid can be written as a concatenation of elements drawn from the subsets.

The Chen–Fox–Lyndon theorem states that the Lyndon words furnish a factorization.

The defect theorem[15][16][17] states that if X is finite and C is the basis of the free hull of X, then either X is a code and C = X, or A monoid morphism f from a free monoid B∗ to a monoid M is a map such that f(xy) = f(x)⋅f(y) for words x,y and f(ε) = ι, where ε and ι denote the identity elements of B∗ and M, respectively.

[20] A morphism f from a free monoid B∗ to a free monoid A∗ is total if every letter of A occurs in some word in the image of f; cyclic[20] or periodic[21] if the image of f is contained in {w}∗ for some word w of A∗.

[25] For L a subset of B∗, a finite subset T of L is a test set for L if morphisms f and g on B∗ agree on L if and only if they agree on T. The Ehrenfeucht conjecture is that any subset L has a test set:[26] it has been proved[27] independently by Albert and Lawrence; McNaughton; and Guba.

[28] The computational embodiment of a monoid morphism is a map followed by a fold.

A monoid homomorphism from the free monoid to any other monoid (M,•) is a function f such that where e is the identity on M. Computationally, every such homomorphism corresponds to a map operation applying f to all the elements of a list, followed by a fold operation which combines the results using the binary operator •.

This computational paradigm (which can be generalized to non-associative binary operators) has inspired the MapReduce software framework.

String projection is a morphism in the category of free monoids, so that where

is understood to be the free monoid of all finite strings that don't contain the letter a.

String projection is idempotent, as for all strings s. Thus, projection is an idempotent, commutative operation, and so it forms a bounded semilattice or a commutative band.

For example, if A = {a, b, c}, elements of the free commutative monoid on A are of the form The fundamental theorem of arithmetic states that the monoid of positive integers under multiplication is a free commutative monoid on an infinite set of generators, the prime numbers.

The free commutative semigroup is the subset of the free commutative monoid that contains all multisets with elements drawn from A except the empty multiset.

This generalization finds applications in combinatorics and in the study of parallelism in computer science.