{"id":193,"date":"2015-04-23T10:49:17","date_gmt":"2015-04-23T08:49:17","guid":{"rendered":"http:\/\/duch.mimuw.edu.pl\/~bojan\/podpunkt\/?page_id=193"},"modified":"2015-04-23T13:50:16","modified_gmt":"2015-04-23T11:50:16","slug":"algebra-for-infinite-words","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20142015-2\/alg\/algebra-for-infinite-words","title":{"rendered":"7. Algebra for infinite words"},"content":{"rendered":"

Recall that a monoid\u00a0consists of a universe \"M\" together with a product operation <\/p>\n

  <\/span>   <\/span>\"\[\pi : 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]^{flat} \ar[d]_{\pi^*} & M^* \ar[d]^\pi \\ M^* \ar[r]_\pi & M}\]\"<\/p>\n

where \"flat\" flattens a word of words into a word in the obvious way, while \"\pi^*\" applies the product operation to every word in a word of words.<\/p>\n

To define monoids for infinite words, we use the same definition, only \"*\" is replaced by \"\infty\". This requires a new flattening operation <\/p>\n

  <\/span>   <\/span>\"\[\mathrm{flat} : (M^\infty)^\infty \to M^\infty\]\"<\/p>\n

which we\u00a0illustrate on three\u00a0examples:<\/p>\n

  <\/span>   <\/span>\"\begin{eqnarray*}<\/p>\n

Note how in the second example above, the first infinite word causes the rest of the input to be ignored. This ignoring is a little bit of a hack, which could be avoided by either using two sorts (finite and infinite word), or by considering a richer notion of words which is closed under substitution, e.g. words where the positions form a countable well-ordering.<\/p>\n

Summing up, \"\infty\"-monoids are defined below.<\/p>\n

Definition.\u00a0<\/strong>\u00a0An \"\infty\"-monoid consists of a unierse \"M\" together with a product operation <\/p>\n

  <\/span>   <\/span>\"\[\pi : M^\infty \to M\]\"<\/p>\n

which is the identity on one letter words and which is associative in the sense that the following diagram commutes\u00a0<\/p>\n

  <\/span>   <\/span>\"\[\xymatrix{(M^\infty)^\infty \ar[r]^{flat} \ar[d]_{\pi^\infty} & M^\infty \ar[d]^\pi \\ M^\infty \ar[r]_\pi & M}\]\"<\/p>\n

 <\/p>\n

It is not difficult to see that \"\Sigma^\infty\", with flattening as the monoid operation, is an \"\infty\"-monoid. Here is an example of an \"\infty\"-monoid with a finite universe.<\/p>\n

 <\/p>\n

Example.\u00a0<\/strong>This \"\infty\"-monoid is going to recognize the \"\infty\"-words over alphabet \"\set{a,b}\" which contain infinitely many \"a\"‘s. The \u00a0universe is\u00a0<\/p>\n

  <\/span>   <\/span>\"\[M = \set{\epsilon, a, b, a^\omega, b^\omega}\]\"<\/p>\n

\u00a0The product operation is defined as follows.\u00a0To define \"\pi(w)\" with \"w \in M^\infty\", we do the following. First, remove all \"\epsilon\" letters from \"w\". If the result is empty, return \"\epsilon\". \u00a0If there is a letter of the form \u00a0\"a^\omega\" or \"b^\omega\", then return the \"a^\omega\" or \"b^\omega\", whichever comes first in \"w\". Otherwise, if the result is an infinite word, then return \"a^\omega\" if there are infinitely many \"a\"‘s and \"b^\omega\" otherwise. Otherwise, return \"a\" if there is at least one \"a\" and \"b\" otherwise. \"\Box\"<\/span><\/p>\n

 <\/p>\n

Homomorphism. <\/strong>Define a homomorphism of \"\infty\"-monoids \"M\" and \"N\" to be a function \"h\" between their universes which respects the structure of \"\infty\"-morphisms in the sense that the following diagram commutes<\/p>\n

  <\/span>   <\/span>\"\[\xymatrix{M^\infty \ar[r]^{h^\infty} \ar[d]_{\pi_M} & N^\infty \ar[d]^{\pi_N} \\ M \ar[r]^h & N}\]\"<\/p>\n

\n

 <\/p>\n

Compositional functions. <\/strong>As with normal monoids, instead of defining an associative product operation on a universe \"N\", it is sometimes easier to give a compositional function from an existing \"\infty\"-monoid to \"N\", and get the \"\infty\"-monoid structure on \"N\" automatically from that. We describe this now.\u00a0Suppose that \"M\" is an \"\infty\"-monoid and \"N\" is a set. A\u00a0function <\/p>\n

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

is called compositional<\/em> if every words \"w,v \in M^\infty\" satisfy<\/p>\n

  <\/span>   <\/span>\"\[h^\infty(w) = h^\infty(v) \qquad \text{implies} \qquad h(\pi(w)) = h(\pi(v))\]\"<\/p>\n

 <\/p>\n

Lemma.\u00a0<\/strong>If \"h : M \to N\" is compositional, then there is a multiplication operation on \"N\" which turns it into an \"\infty\"-monoid, and which turns \"h\" into a homomorphism of \"\infty\"-monoids.<\/em><\/p>\n

Proof.\u00a0<\/strong>Compositionality can be rephrased as saying that there is some function \"\sigma\" which makes the following diagram commute<\/p>\n

  <\/span>   <\/span>\"\[\xymatrix{M^\infty \ar[r]^{h^\infty} \ar[d]_{\pi} & N^\infty \ar[d]^\sigma \\ M \ar[r]^h & N}\]\"<\/p>\n

The above diagram then shows that \"h\" is a homomorphism, assuming that \"\sigma\" yields a structure of an \"\infty\"-monoid on \"N\", i.e. it is associative. Associativity is not difficult to show. \"\Box\"<\/p>\n

 <\/p>\n

 <\/p>\n","protected":false},"excerpt":{"rendered":"

Recall that a monoid\u00a0consists of a universe together with a product operation     which maps each one letter word \u00a0to , and which is associative in the sense that the following diagram commutes     where flattens a word of words into a word in the obvious way, while applies the product operation to […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":42,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-193","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/193"}],"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=193"}],"version-history":[{"count":5,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/193\/revisions"}],"predecessor-version":[{"id":247,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/193\/revisions\/247"}],"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=193"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}