{"id":204,"date":"2015-04-23T12:20:47","date_gmt":"2015-04-23T10:20:47","guid":{"rendered":"http:\/\/duch.mimuw.edu.pl\/~bojan\/podpunkt\/?page_id=204"},"modified":"2015-06-22T16:12:25","modified_gmt":"2015-06-22T14:12:25","slug":"from-aperiodic-to-star-free","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20142015-2\/alg\/3-the-schutzenberger-theorem\/from-aperiodic-to-star-free","title":{"rendered":"From aperiodic to star-free"},"content":{"rendered":"

In this page, we show the implication from aperiodic monoids to star-free expressions in the Sch\u00fctzenberger theorem. The implication is stated in the following lemma.<\/p>\n

Lemma 0.\u00a0<\/strong>Let \"h : A^* \to M\" be a morphism into a finite aperiodic monoid. Then for every \"m \in M\", the inverse image \"h^{-1}(m)\" is definable by a star-free expression.<\/p>\n

The rest of this page is devoted to proving the above lemma. Fix the morphism \"h\" as in the lemma. Let us use the name type of \"w\"\u00a0<\/em>for the image \"h(w)\". \u00a0Stated in this terminology, we need to show that for every \"m\" in the monoid, the set of words of type \"m\" is definable by a star-free expression. \u00a0The proof is by induction on the position of \"m\" in the \"\Jj\"-ordering, with simpler \"\Jj\"-classes coming first in the induction. (Recall that simpler \"\Jj\"-classes are those of infixes, in particular the simplest \"\Jj\"-class is the one that contains the monoid identity.)\u00a0<\/em><\/p>\n

\n

Induction base.\u00a0<\/strong>The induction base is the case when \"m\" belongs to the simplest\u00a0\"\Jj\"-class, namely the one which contains the identity. By Lemma 4 in the section on Green’s relations<\/a>, the \"\Jj\"-class of the identity is a group. Since aperiodic monoids cannot contain non-trivial groups, it follows that the \"\Jj\"-class of the identity consists only of the identity. \u00a0This means that the type of a word is the identity if and only if every letter used by that word has the identity type. In other words, the words whose type is the identity are defined by the star-free expression <\/p>\n

  <\/span>   <\/span>\"\[\neg (\neg \emptyset \cdot B \cdot \neg \emptyset)\]\"<\/p>\n

where\u00a0\u00a0\"B\" is those letters in the alphabet that have non-identity type.<\/span><\/p>\n

\n

Induction step.\u00a0<\/strong>\u00a0Fix\u00a0some \"\Jj\"-class \"J\" in the monoid, and assume that the inverse image \"h^{-1}(m)\" is star-free for every \"m\" which has a \"\Jj\"-class strictly simpler\u00a0than \"J\". We will now prove that the same holds for every \"m \in J\".<\/p>\n

Recall that an \"\Hh\"-class is an intersection of an \"\Ll\"-class and an \"\Rr\"-class.<\/p>\n

Lemma 2.\u00a0<\/strong>In an aperiodic monoid, every \"\Hh\"-class has one element.<\/p>\n

Proof. <\/strong>Stated differently, the lemma says that if \"m,n\" are both \"\Rr\"– and \"\Ll\"-equivalent, then they are equal. Let \"m,n\" be such elements, i.e.\u00a0there exist some \"x,y\" in the monoid such that <\/p>\n

  <\/span>   <\/span>\"\[mx = n \qquad yn =m\]\"<\/p>\n

Therefore \"x^i m y^j\" is \"m\" when \"j=i\" and is \"n\" when \"j=i+1\". If \"i\" is large enough, then aperiodicity says that \"y^i = y^{i+1}\" and therefore\u00a0\"m=n\". \"\Box\"<\/p>\n

Define\u00a0\"R_m \subseteq A^*\" to\u00a0be the set of\u00a0\u00a0words which have a prefix whose type\u00a0is \"\Rr\"-equivalent to \"m\". Likewise define\u00a0\"L_m\" to be the set of words which have a suffix whose type is \"\Ll\"-equivalent to \"m\". Clearly every word with type \"m\" belongs to both \"R_m\" and \"L_m\".<\/p>\n

Lemma 3. <\/strong>For every \"m\in J\", the languages \"R_m\" and \"L_m\" are star-free.<\/p>\n

Proof.\u00a0<\/strong>\u00a0We only do the proof for \"R_m\". \u00a0For a word \"w \in R_m\", consider the shortest prefix that has the same \"\Jj\"-class as \"m\". This prefix exists by membership in \"R_m\", and because the \"\Rr\"-class of a monoid element is included in its \"\Jj\"-class. The shortest prefix is nonempty, because \"m\" is not \"\Jj\"-equivalent to the identity, and therefore this prefix has to be of the form \"ua\" with \"u\" having a type that is strictly \"\Jj\"-simpler than \"m\". From the Eggbox Lemma in the section on Green’s relations<\/a> it follows that the type of \"ua\" is \"\Rr\"-equivalent to \"m\". From these observations, it follows that\u00a0<\/p>\n

  <\/span>   <\/span>\"\[R_m = \bigcup_{n,a} h^{-1}(n) \cdot a \cdot \neg \emptyset\]\"<\/p>\n

where the union ranges over \"n\" that are strictly \"\Jj\"-simpler than \"m\" and letters \"a \in A\" such that \"na\" is \"\Rr\"-equivalent to \"m\". The above is definable by a star-free expression, since the induction assumption can be applied to yield star-free expressions for the languages \"h^{-1}(n)\". \u00a0\"\Box\"<\/span><\/p>\n

The following lemma completes the induction step in the proof of Lemma 0.<\/p>\n

Lemma 4.\u00a0<\/strong>For every \"m \in J\",\u00a0the set of words with type \"m\" is equal to <\/p>\n

  <\/span>   <\/span>\"\[L_m \cap R_m - \bigcup_{\substack{n \in M\\a \in A}} L_n \cdot a \cdot (\neg \emptyset)\]\"<\/p>\n

where\u00a0\u00a0the union ranges over \"n,a\" such that \"n\" is \"\Jj\"-equivalent to \"m\" but \"na\" is not.<\/p>\n

Proof. <\/strong>Let us begin with the left-to-right inclusion. If \"w\" has type \"m\", then it clearly belongs to both \"L_m\" and \"R_m\". We need to show that \"w\" does not belong to the union in the expression from the statement of the lemma. In other words, we need to show that there is no infix of \"w\" which is of the form \"va\" such that the type of \"v\" is \"\Ll\"-equivalent to some \"n\" such that \u00a0 \"n\" is \"\Jj\"-equivalent to \"m\" but \"na\" is not. If there was such an infix, then the type of \"v\" could be decomposed as \"xn\" for some \"x\" in the monoid, and therefore \"J\" would be strictly \"\Jj\"-simpler than the type of \"va\", and therefore the type of \"w\" would be in a different \"\Jj\"-class than \"m\". \u00a0This completes the proof of the left-to-right inclusion in the lemma.<\/p>\n

Let us do the right-to-left inclusion. Suppose that \"w\" belongs to the expression in the statement of the lemma. \u00a0Membership of \"w\" in \"L_m\" and \"R_m\" says that the type of \"w\" is a prefix and suffix of \"m\". Therefore, by the Eggbox Lemma, if we prove that the type of \"w\" of is \"\Jj\"-equivalent to \"m\", we will know that the type of \"w\" is in the same \"\Hh\"-class as \"m\", and therefore it must be equal to \"m\" by Lemma 2. \u00a0So it remains to show that the type of \"w\" is in \"J\". But if \"m\" were strictly \"\Jj\"-simpler than the type of \"w\", then the shortest prefix with type not \"\Jj\"-simpler than \"m\" would belong to \"L_n a\" as in the statement of the lemma. \"\Box\"<\/p>\n

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

In this page, we show the implication from aperiodic monoids to star-free expressions in the Sch\u00fctzenberger theorem. The implication is stated in the following lemma. Lemma 0.\u00a0Let be a morphism into a finite aperiodic monoid. Then for every , the inverse image is definable by a star-free expression. The rest of this page is devoted […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":202,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-204","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/204"}],"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=204"}],"version-history":[{"count":3,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/204\/revisions"}],"predecessor-version":[{"id":460,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/204\/revisions\/460"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/202"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=204"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}