Basis (universal Algebra) - Examples - Word Monoid

Word Monoid

Let be an "alphabet", namely a (usually finite) set of objects called "letters". Let W denote the corresponding set of words or "strings", which will be denoted as in strings, namely either by writing their letters in sequence or by in case of the empty word (Formal Language notation). Accordingly, the juxtaposition will denote the concatenation of two words v and w, namely the word that begins with v and is followed by w.

Concatenation is a binary operation on W that together with the empty word defines a free monoid, the monoid of the words on, which is one of the simplest universal algebras. Then, the inner condition will immediately prove that one of its bases is the function b that makes a single-letter word of each letter, .

(Depending on the set-theoretical implementation of sequences, b may not be an identity function, namely may not be, rather an object like, namely a singleton function, or a pair like or .)

In fact, in the theory of D0L systems (Rozemberg & Salomaa 1980) such are the tables of "productions", which such systems use to define the simultaneous substitutions of every by a single word in any word u in W: if, then . Then, b satisfies the inner condition, since the function is the well-known bijection that identifies every word endomorphism with any such table. (The repeated applications of such an endomorphism starting from a given "seed" word are able to model many growth processes, where words and concatenation serve to build fairly heterogeneous structures as in L-system, not just "sequences".)

Read more about this topic:  Basis (universal Algebra), Examples

Famous quotes containing the word word:

    One thinking it is right to speak all things, whether the word is fit for speech or unutterable.
    Sophocles (497–406/5 B.C.)