{"id":198,"date":"2015-04-23T12:14:02","date_gmt":"2015-04-23T10:14:02","guid":{"rendered":"http:\/\/duch.mimuw.edu.pl\/~bojan\/podpunkt\/?page_id=198"},"modified":"2015-09-22T16:27:02","modified_gmt":"2015-09-22T14:27:02","slug":"1-introduction-to-monoids","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20142015-2\/alg\/1-introduction-to-monoids","title":{"rendered":"1. Introduction to monoids"},"content":{"rendered":"

A monoid is a set with an empty element, and an associative multiplication\u00a0operation. We present two formal definitions of this concept, namely the classical one in Definition 1, and a slightly nonstandard one in Definition 2.<\/p>\n

Definition 1.\u00a0<\/strong>A monoid consists of a universe \"M\" together with an identity element \"1 \in M\" and a multiplication\u00a0operation, denoted multiplicatively, which is associative in the sense that <\/p>\n

  <\/span>   <\/span>\"\[(m \cdot n) \cdot k = m \cdot (n \cdot k)\]\"<\/p>\n

holds for every \"m,n,k \in M\". \"\Box\"<\/p>\n

The definition says that the order of evaluation in a monoid is not important, i.e. that different ways of parenthesising a sequence of elements in the monoid will yield the same result as far as monoid multiplication is concerned. This is made explicit in the following fact, which is implicitly presented to students already in primary school (at least this was the case for me).<\/p>\n

Fact 1.\u00a0<\/strong>Let \"M\" be a monoid, and let \"m_1,\ldots,m_k\" be a sequence of elements in \u00a0\"M\". For any possible way of parenthesising the sequence and multiplying it in the monoid, the result is the same.<\/p>\n

Proof. <\/strong>A parenthesisation can be viewed as a binary tree, where the leaves are labelled by \"m_1,\ldots,m_k\" when read from left to right. The associativity equation in Definition 1 says that doing a rotation does not affect the value of a tree. Every two trees that have the same sequence of leaves can be transformed into each other using a finite sequence of rotations. \"\Box\"<\/p>\n

In light of the above proof, the definition of associativity in Definition 1 might seem a little bit of a hack. An alternative definition is presented below. The key is that the multiplication\u00a0operation is no longer binary, but takes in an arbitrary word. This allows a new statement of the associativity condition, in the form of a commuting diagram. The new statement, easily seen to be equivalent with the classical definition in Definition 1, will be a basis for further generalisations later in the lecture<\/a>. Also because of these later generalisations, we write some of the subsequence definitions, like homomorphisms, in terms of commuting diagrams.<\/p>\n

Definition 2<\/strong>. A monoid consists of a universe \"M\" together with a\u00a0multiplication\u00a0operation <\/p>\n

  <\/span>   <\/span>\"\[\multnoarg : M^* \to M\]\"<\/p>\n

which maps each one letter word \"m\" \u00a0to \"m\", and which is associative in the sense that the following diagram commutes <\/p>\n

  <\/span>   <\/span>\"\[\xymatrix{(M^*)^* \ar[r]^{\flattnoarg} \ar[d]_{\multnoarg^*} & M^* \ar[d]^{\multnoarg} \\ M^* \ar[r]_{\multnoarg} & M}\]\"<\/p>\n

where \"\flattnoarg\" flattens a word of words into a word in the obvious way, while \"\multnoarg^*\" applies the\u00a0multiplication\u00a0operation to every word in a word of words.<\/p>\n

Fact.\u00a0<\/strong>The two definitions are the same.<\/p>\n

Proof.\u00a0<\/b>Using Fact 1. \"\Box\"<\/p>\n

Example 1.<\/strong>\u00a0If \"\Sigma\" is a set, then \"\Sigma^*\" is a monoid, where the identity is the empty words, and concatenation is the monoid operation.\u00a0\"\Box\"<\/p>\n

\n

Monoid homomorphisms<\/strong><\/p>\n

A monoid homomorphism if a function between monoids that preserves the structure of monoids, i.e.\u00a0a\u00a0monoid homomorphism<\/em> between monoids \"M\" and \"N\" \u00a0is a function <\/p>\n

  <\/span>   <\/span>\"\[h : M \to N\]\"<\/p>\n

\u00a0which preserves the identity element\u00a0and which is consistent with the multiplication\u00a0operation in the sense that <\/p>\n

  <\/span>   <\/span>\"\[h(m \cdot n) = h(m) \cdot h(n)\]\"<\/p>\n

An alternative definition of a homomorphism would be that the following diagram commutes<\/p>\n

  <\/span>   <\/span>\"\[\xymatrix{M^* \ar[r]^{h^*} \ar[d]_{\mult M} & N^* \ar[d]^{\mult N} \\ M \ar[r]_h & N}\]\"<\/p>\n

with the two downward arrows representing the multiplication operations\u00a0in the respective monoids.<\/p>\n

Using monoid homomorphisms, we can express the following universal property of the monoid \"\Sigma^*\". It is generated by \"\Sigma\", and it is the biggest monoid generated by \"\Sigma\" \u00a0in the following sense. For every monoid \"N\" that is generated by \"\Sigma\", there exists a surjective monoid homomorphism <\/p>\n

  <\/span>   <\/span>\"\[h : \Sigma^* \to M\]\"<\/p>\n

which is the identity on the \"\Sigma\" generators. \u00a0This is property goes under the name “\"\Sigma^*\" is the free monoid with generators \"\Sigma\"“.<\/p>\n

Monoid homomorphisms are closely related with functions that are compositional in the sense defined below. Let \"M\" be a monoid, and let \"X\" be a set. A function <\/p>\n

  <\/span>   <\/span>\"\[h : M \to X\]\"<\/p>\n

is called compositional<\/em>\u00a0if for every \"m, n \in M\", the value \"h(m \cdot n)\" is uniquely determined by the values \"h(m)\" and \"h(n)\". Again, compositionality can be stated in terms of terms of a commuting diagram: \u00a0\"h\" is compositional if there is some function \"\mult X\" such that the following diagram commutes:\u00a0<\/p>\n

  <\/span>   <\/span>\"\[\xymatrix{M^* \ar[r]^{h^*} \ar[d]_{\mult M} & X^* \ar[d]^{\mult X} \\ M \ar[r]_h & X}\]\"<\/p>\n

Lemma.<\/strong> Let \"M\" be a monoid, and let \"h : M \to X\" be a sujrective compositional function. Then there exists (a unique) monoid structure on \"X\" which makes \"h\" into a monoid homomorphism.<\/p>\n

Proof.<\/strong>\u00a0 Saying that \"h(m \cdot n)\" is uniquely determined by \"h(m)\" and \"h(n)\", as in the definition of compositionally, means that there is a function <\/p>\n

  <\/span>   <\/span>\"\[f : X \times X \to X\]\"<\/p>\n

such that every \"m,n \in M\" satisfy <\/p>\n

  <\/span>   <\/span>\"\[h(m \cdot n) = f(h(m),h(n)).\]\"<\/p>\n

One uses \"f\" to be the product operation in \"X\", and takes the identity to be the image under \"h\" of the identity. \"\Box\"<\/p>\n

\n

Recognising languages<\/strong><\/p>\n

In this lecture, we will be interested in monoid as an alternative to finite automata, i.e. we will use monoids to recognise languages.<\/p>\n

Definition<\/strong>. A language \"L \subseteq A^*\" is said to be recognised<\/em> by a monoid homomorphism <\/p>\n

  <\/span>   <\/span>\"\[h : A^* \to M\]\"<\/p>\n

if membership in \"w \in L\" is determined uniquely by \"h(w)\". In other words, there exists a subset \"F \subseteq M\" such that <\/p>\n

  <\/span>   <\/span>\"\[w \in L \qquad\text{iff} \qquad h(w) \in F\]\"<\/p>\n

holds for every word \"w \in A^*\". \"\Box\"<\/p>\n

The following theorem shows that, as far as recognising languages is concerned, finite monoids and finite automata are equivalent.<\/p>\n

Theorem 1. <\/strong>The following conditions are equivalent for every language \"L \subseteq A^*\":
\n\u2022 \"L\" is recognised by a finite automaton;
\n\u2022 \"L\" is recognised by a monoid homomorphism into a finite monoid.<\/p>\n

Proof.<\/strong>\u00a0From a monoid one creates a deterministic automaton, whose states are elements of the monoid, and where the transition relation is obtained from the monoid operation in the obvious way. This proves the bottom-up implication. For the top-down implication, let us transform a nondeterministic automaton into a monoid.\u00a0\u00a0<\/strong>\u00a0Let \"\mathcal A\" be a nondeterministic automaton with input alphabet \"A\" and states \"Q\". Define the function \u00a0<\/p>\n

  <\/span>   <\/span>\"\[\delta : A^* \to P(Q \times Q)\]\"<\/p>\n

which sends a word \"w\" to the set of pairs \"(p,q)\" such that there exists a run of the automaton which begins in \"p\", reads the word \"w\", and ends in \"q\". One can show that \"\delta\" is compositional, and therefore there is a monoid structure on its image which makes it into a monoid homomorphism. The appropriate multiplication\u00a0operation is simply composition of relations, while the identity is the identity relation. \"\Box\"<\/p>\n

Note how the transformation from a nondeterministic finite automaton\u00a0to a monoid incurs an exponential blowup. Note also that the transformation from nondeterministic finite automaton\u00a0to a deterministic finite automaton\u00a0is exponential, but going directly from a nondeterministic finite automaton\u00a0to monoids is not doubly exponential.<\/p>\n

\n

The syntactic monoid<\/strong><\/p>\n

Deterministic finite automaton have minimisation, i.e. there is always a minimal deterministic automaton that can be obtained from any other automaton by quotienting. The same holds for monoids, as proved in the following theorem.<\/p>\n

Theorem 2.\u00a0<\/strong>For every language \"L \subseteq A^*\" there exists a monoid homomorphism <\/p>\n

  <\/span>   <\/span>\"\[h : A^* \to M,\]\"<\/p>\n

called the syntactic homomorphism of \"L\",\u00a0<\/em>which recognises it and \u00a0is minimal in the sense that for every surjective monoid \u00a0homomorphism <\/p>\n

  <\/span>   <\/span>\"\[g : A^* \to N\]\"<\/p>\n

which also recognises \"L\", there exists a unique monoid homomorphism which makes the following diagram commute <\/p>\n

  <\/span>   <\/span>\"\[\xymatrix{ A^* \ar[r]^h \ar[dr] _g& M \\ & N\ar[u]_f }\]\"<\/p>\n

Proof.\u00a0<\/strong>Define the\u00a0syntactic equivalence of \"L\"\u00a0<\/em>to be the equivalence relation on \"A^*\" which identifies two words \"w,w' \in A^*\" if \u00a0<\/p>\n

  <\/span>   <\/span>\"\[wuv \in L \qquad\text{iff} \qquad wu'v \in L\]\"<\/p>\n

holds for every \"u,v \in A^*\". One can show that the function, call it \"h\", \u00a0that maps a word to its equivalence class is compositional, and therefore by Lemma 1, the set of equivalence classes is equipped with a monoid structure that makes \"h\" into a monoid homomorphism. It is not difficult to check that \"h\" is minimal as required in the theorem. \"\Box\"<\/p>\n

Exercise.\u00a0<\/strong>Prove that surjectivity is important in the above theorem.<\/p>\n","protected":false},"excerpt":{"rendered":"

A monoid is a set with an empty element, and an associative multiplication\u00a0operation. We present two formal definitions of this concept, namely the classical one in Definition 1, and a slightly nonstandard one in Definition 2. Definition 1.\u00a0A monoid consists of a universe together with an identity element and a multiplication\u00a0operation, denoted multiplicatively, which is […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":42,"menu_order":0,"comment_status":"open","ping_status":"closed","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-198","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/198"}],"collection":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/comments?post=198"}],"version-history":[{"count":6,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/198\/revisions"}],"predecessor-version":[{"id":527,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/198\/revisions\/527"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/42"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=198"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}