{"id":202,"date":"2015-04-23T12:18:45","date_gmt":"2015-04-23T10:18:45","guid":{"rendered":"http:\/\/duch.mimuw.edu.pl\/~bojan\/podpunkt\/?page_id=202"},"modified":"2017-10-31T12:56:07","modified_gmt":"2017-10-31T11:56:07","slug":"3-the-schutzenberger-theorem","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20142015-2\/alg\/3-the-schutzenberger-theorem","title":{"rendered":"3. The Sch\u00fctzenberger Theorem"},"content":{"rendered":"

The theorem is part of a bigger picture, which is the\u00a0strong connection between automata, monoids and logic. It turns out that, when studying regular languages, the most natural logic is not the classical first-order logic, but a\u00a0more expressive logic called\u00a0monadic second-order logic<\/em>,\u00a0which has the same expressive power as regular languages.\u00a0<\/em>The Sch\u00fctzenberger theorem in this logic is best understood as part of this bigger picture: it explains the expressive power of first-order logic as a fragment of monadic-second order logic. Since monadic second-order logic is outside the scope of this lecture, we do not talk about\u00a0it below, and we define only the minimal amount of logical material that is necessary to state and prove the theorem.<\/p>\n

\n

 <\/p>\n

First-order logic<\/strong><\/p>\n

Consider the\u00a0property “for every position that has label\u00a0a,\u00a0<\/em>there is a later position that has label\u00a0b”.\u00a0<\/em>This property can be formalized in the language of logic as <\/p>\n

  <\/span>   <\/span>\"\[\forall x a(x) \Rightarrow \exists y (x < y \land b(y))\]\"<\/p>\n

This is the idea behind\u00a0first-order definable languages of words.\u00a0<\/em>One uses formulas, where the variables quantify over positions of the word, with a binary predicate \"x < y\" that denotes the order on positions, and with unary predicates of the form \"a(x)\" to test the labels of positions. A set of words is called\u00a0first-order\u00a0<\/em>definable\u00a0<\/em>if there is a formula of this kind that is true on words from the set and false in other words. The term “first-order” refer to the fact that the logic can only quantify over single positions, as opposed to quantification over sets of positions, or sets of sets of positions, which would be possible in higher-order logics (e.g. monadic second-order logic mentioned above is allowed to quantify over sets of positions, but not sets of pairs of positions).<\/p>\n

Example.\u00a0<\/strong>The language \"(a+b)^*b\" is definable in first-order logic, using the formula given above.<\/p>\n

\n

Star-free expressions.\u00a0<\/strong><\/p>\n

Star-free expressions are, essentially, a minor variation on first-order logic. A star-free expression<\/em> is a regular expression that does not use the star, but it can use complementation (with respect to an alphabet that is implicit in the expression). For example, if the input alphabet is \"\Sigma\", then the complement of the empty set is a star-free expression that describes \"\Sigma^*\". Using this expression, one can e.g. define the set of words that contain at least one letter \"a\", this is <\/p>\n

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

\n

Aperiodic monoids.<\/strong><\/p>\n

Call a finite monoid\u00a0aperiodic\u00a0<\/em>if for every \"m\" in the monoid, the sequence <\/p>\n

  <\/span>   <\/span>\"\[m,m^2,m^3,\ldots\]\"<\/p>\n

is ultimately constant. It is easy to see that this is equivalent to saying that every \"m\" in the monoid satisfies <\/p>\n

  <\/span>   <\/span>\"\[m^\# =m^{\#}m\]\"<\/p>\n

where \"m^\#\" is the idempotent power discussed here<\/a>.<\/p>\n

\n

 <\/p>\n

The Sch\u00fctzenberger theorem.\u00a0<\/strong><\/p>\n

We are now ready to state the Sch\u00fctzenberger theorem.<\/p>\n

Theorem. <\/strong>For a language\u00a0\"L \subseteq A^*\", the following conditions are equivalent:<\/p>\n

    \n
  1. \"L\" is definable by a star-free expression;<\/li>\n
  2. \"L\" is definable in first-order logic;<\/li>\n
  3. the syntactic monoid of \"L\" is aperiodic.<\/li>\n<\/ol>\n

     <\/p>\n

    Technically speaking, Sch\u00fctzenberger proved only the equivalence of 1 and 3, and the addition of 2 is due to McNaughton and Papert. The addition of 2 is not a big deal: the implication from 1 to 2 is done via a routine induction on the size of a star-free expression, while the implication from 2 to 3 is proved the same way as the implication from 1 to 3. Therefore, the theorem is essentially by Sch\u00fctzenberger.<\/p>\n

    As mentioned above, \u00a0the implication from 1 to 2 is straightforward. The implication from 2 to 3 is proved here<\/a>, while the implication from 3 to 1 is proved here<\/a>.<\/p>\n

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

    The theorem is part of a bigger picture, which is the\u00a0strong connection between automata, monoids and logic. It turns out that, when studying regular languages, the most natural logic is not the classical first-order logic, but a\u00a0more expressive logic called\u00a0monadic second-order logic,\u00a0which has the same expressive power as regular languages.\u00a0The Sch\u00fctzenberger theorem in this logic […]<\/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-202","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/202"}],"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=202"}],"version-history":[{"count":4,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/202\/revisions"}],"predecessor-version":[{"id":1403,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/202\/revisions\/1403"}],"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=202"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}