{"id":248,"date":"2015-04-23T14:36:06","date_gmt":"2015-04-23T12:36:06","guid":{"rendered":"http:\/\/duch.mimuw.edu.pl\/~bojan\/podpunkt\/?page_id=248"},"modified":"2015-04-23T14:37:33","modified_gmt":"2015-04-23T12:37:33","slug":"equivalence-with-%cf%89-regular-languages","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20142015-2\/alg\/algebra-for-infinite-words\/equivalence-with-%cf%89-regular-languages","title":{"rendered":"Equivalence with \u03c9-regular languages"},"content":{"rendered":"

 <\/p>\n

Monoids are equivalent to automata<\/strong><\/p>\n

A\u00a0language \"L \subseteq \Sigma^\infty\" is called \"\infty\"-recognisable<\/em> if there is some homomorphism of \"\infty\"-monoids <\/p>\n

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

such that \"M\" has finite universe, and which recognizes \"L\" in the sense that membership \"w \in L\" is uniquely determined by \"h(w)\". \u00a0The following theorem shows that in the special (but not all that special) case of languages that contain only\u00a0\"\omega\"-words, this notion coincides with the notion of \"\omega\"-regularity.<\/p>\n

Theorem. <\/strong>A\u00a0language \"L \subseteq \Sigma^\omega\" is \"\infty\"-recognisable if and only if it is \"\omega\"-regular<\/em>.<\/p>\n

Proof.\u00a0<\/strong>For \"m \in M\" define \"L_{m,+}\" to be the finite nonempty words that are mapped by \"h\" to \"m\", and define \"L_{m,\omega}\" to be the \"\omega\"-words that are mapped by \"h\" to \"m\". It is easy to see that each language\u00a0\"L_{m,+}\" is a regular language of finite words, because it is recognised by a finite monoid, namely the monoid obtained from \"M\" by ignoring products for infinite words. Furthermore, using the Ramsey theorem in the same way as in the previous lemma, we conclude that \"L_{m,\omega}\" is equal to the \"\omega\"-regular language <\/p>\n

  <\/span>   <\/span>\"\[\bigcup_{s,t} L_{s,+} \cdot (L_{t,+})^\omega\]\"<\/p>\n

with the union ranging over elements \"s,t \in M\" which satisfy \"st^\omega = m\". Every set of \"\omega\"-words recognised by \"h\" is a finite union of languages of the form \"L_{m,\omega}\", and therefore the left-to-right implication follows by closure of \"\omega\"-regular languages under finite union.<\/p>\n

For the right-to-left implication, suppose that \"L\" is recongised by a nondeterministic B\u00fcchi automaton with states \"Q\". Define <\/p>\n

  <\/span>   <\/span>\"\[h : \Sigma^\infty \to P(Q) \cup P(Q \times \set{0,1} \times Q) \cup \set \epsilon\]\"<\/p>\n

defined as follows. The empty word gets mapped to \"\epsilon\". Infinite words\u00a0are\u00a0mapped to \"P(Q)\", namely an infinite word is mapped to the set of those states \"p\" such that the word admits an accepting run that begins with \"p\". Finite words are mapped to \"P(Q \times \set{0,1} \times Q)\" in the same way as in the proof of complementation for B\u00fcchi automata. It is not difficult to see that this mapping is compositional, and therefore its image can be equipped with the structure of an \"\infty\"-monoid which makes it into a homomorphism. \"\Box\"<\/p>\n

 <\/p>\n

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

  Monoids are equivalent to automata A\u00a0language is called -recognisable if there is some homomorphism of -monoids     such that has finite universe, and which recognizes in the sense that membership is uniquely determined by . \u00a0The following theorem shows that in the special (but not all that special) case of languages that contain […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":193,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-248","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/248"}],"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=248"}],"version-history":[{"count":19,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/248\/revisions"}],"predecessor-version":[{"id":267,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/248\/revisions\/267"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/193"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=248"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}