{"id":585,"date":"2015-10-15T13:27:11","date_gmt":"2015-10-15T11:27:11","guid":{"rendered":"http:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=585"},"modified":"2015-10-26T15:11:20","modified_gmt":"2015-10-26T14:11:20","slug":"from-muller-to-parity","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20152016-2\/jezyki-automaty-i-obliczenia-2\/games-with-%cf%89-regular-winning-conditions\/from-muller-to-parity","title":{"rendered":"From Muller to parity"},"content":{"rendered":"

Here we prove the following theorem.<\/p>\n

Theorem<\/strong>.\u00a0For every deterministic Muller automaton, there is an equivalent deterministic parity automaton.<\/p>\n

 <\/p>\n

The above theorem can be proved in two ways. One of them is to show that, by taking more care, we can actually produce a parity automaton in the determinisation construction<\/a>. Here we use an alternative construction, based on a data structure called the\u00a0latest appearance record\u00a0<\/em>that was found by McNaughton. The construction is presented in the following lemma.<\/p>\n

Lemma. <\/strong>For every finite alphabet\u00a0\"\Sigma\", there exists a deterministic automaton with input alphabet \"\Sigma\", a totally ordered state space \"Q\", and a\u00a0function\u00a0<\/p>\n

  <\/span>   <\/span>\"\[g : Q \to \powerset \Sigma\]\"<\/p>\n

with the following property. For every input word, the set of letters appearing infinitely often in the input is obtained by applying \"g\" to the smallest\u00a0state that appears infinitely often in the run.<\/p>\n

Proof. <\/strong>The state space \"Q\" consists of pairs<\/p>\n

  <\/span>   <\/span>\"\[u \in \Sigma^* \qquad n \in \set{0,\ldots,|\Sigma|}\]\"<\/p>\n

such that \"u\" is a non-repeating word, i.e. it contains each letter at most once. The initial state of the automaton is \"(\epsilon,0)\". After reading a finite input word, the state of the automaton is:
\n\u2022 The word obtained from the input by keeping only the latest appearance of each letter (call this the latest appearance record).
\n\u2022 The length of the longest common prefix of the\u00a0latest appearance records\u00a0in the current and previous states (call this the\u00a0hit\u00a0position<\/em>).<\/p>\n

It is not difficult to define the transition function of\u00a0the automaton to make the above invariant true. Here is an example run: <\/p>\n

  <\/span>   <\/span>\"\begin{eqnarray*}(\epsilon,0) \stackrel a \to (a,0) \stackrel a \to (a,1) \stackrel b \to (ab,1) \stackrel c \to (abc,2) \stackrel a \to (bca,0) \stackrel b \to \\ (cab,0) \stackrel b \to (cab,3) \stackrel a \to (cba,1) \stackrel b \to (cab,1) \stackrel a \to (cba,1) \stackrel a \to (cba,3) \end{eqnarray*}\"<\/p>\n

The key observation is this: if \"n\" is the smallest hit position that appears infinitely often, then there are exactly \"n\" letters in the input word that appear at least once but finitely often. In particular, if the smallest state that appears infinitely often is \"(u,n)\" then by removing the first \"n\" letters of \"u\" we get the set of letters that appear infinitely often in the input word.\u00a0 (To be fully precise, there is an exception: if \"|u|=n\", then the set of letters that appears infinitely often is the last letter in \"u\".)<\/p>\n

Therefore, to get the statement of the lemma, we order \"Q\" first by hit positions, and in case of equal\u00a0hit positions\u00a0we use some arbitrary total ordering on the latest appearance records. The function \"g\" is defined according to the description in the previous paragraph.\u00a0\"\Box\"<\/span><\/p>\n

The conversion of Muller to parity is a straightforward corollary of the above lemma: one applies the above lemma to the state space of the Muller automaton, and defines the\u00a0ranks\u00a0according to the Muller condition.<\/p>\n","protected":false},"excerpt":{"rendered":"

Here we prove the following theorem. Theorem.\u00a0For every deterministic Muller automaton, there is an equivalent deterministic parity automaton.   The above theorem can be proved in two ways. One of them is to show that, by taking more care, we can actually produce a parity automaton in the determinisation construction. Here we use an alternative […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":615,"menu_order":2,"comment_status":"open","ping_status":"closed","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-585","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/585"}],"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=585"}],"version-history":[{"count":33,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/585\/revisions"}],"predecessor-version":[{"id":718,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/585\/revisions\/718"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/615"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=585"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}