{"id":547,"date":"2015-10-06T11:04:29","date_gmt":"2015-10-06T09:04:29","guid":{"rendered":"http:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=547"},"modified":"2017-10-03T12:11:04","modified_gmt":"2017-10-03T10:11:04","slug":"reduction-to-trees","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20152016-2\/jezyki-automaty-i-obliczenia-2\/mcnaughtons-theorem\/reduction-to-trees","title":{"rendered":"Reduction to trees"},"content":{"rendered":"

The goal of this page is proving the following lemma.<\/p>\n

Lemma 1.\u00a0<\/strong>There exists a deterministic transducer<\/p>\n

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

which outputs only trees and is invariant with respect to the universal B\u00fcchi language, i.e. if the input contains a path with infinitely many accepting edges, then so does the output and vice versa.<\/p>\n

Consider a \"Q\"-dag. To make notation easier, we assume that there is\u00a0a root, <\/em>i.e. a vertex from which all others are reachable. This assumption can be made without loss of generality, because one\u00a0can easily write a transducer which transforms every \"Q\"-dag into one that has a root, and which is invariant with respect to the universal B\u00fcchi automaton.<\/p>\n

 <\/p>\n

\n

 <\/p>\n

Profiles.\u00a0<\/strong>For a path \"\pi\" in a \"Q\"-dag, define its profile<\/em> to be the word of same length over the alphabet “accepting” and “non-accepting” which is obtained by replacing each edge with its appropriate type. We consider order profiles lexicographically, with\u00a0“accepting” is smaller than\u00a0“non-accepting”.\u00a0Call a finite path \"\pi\" in \"w\"\u00a0optimal<\/em>\u00a0<\/em>if it has lexicographically least profile among paths in \"w\" that have the same source and target.<\/p>\n

Claim 1.\u00a0<\/strong>There is a transducer <\/p>\n

  <\/span>   <\/span>\"\[f : [Q]^\omega \to [Q]^\omega\]\"<\/p>\n

such that if the input is \"w\", then \"f(w)\" is a tree with the same reachable vertices as in \"w\", and such that every path from the root in \"f(w)\" is an optimal path in \"w\".<\/p>\n

Proof. <\/strong>We use the following congruence property of optimal paths: if \"\pi\" and \"\sigma\" are optimal paths such that the target of \"\pi\" is equal to the source of \"\sigma\", then also their composition \"\pi \sigma\" is optimal. A corollary is that if we choose for every vertex in the input graph \"w\" an outgoing edge that participates in some optimal path, then the putting all of these edges together will yield a tree as in the statement of the claim. To produce such edges, after reading the first \"n\" letters, the automaton keeps in its memory the lexicographic ordering on the profiles of optimal paths lead from the root to nodes at depth \"n\". \"\Box\"<\/p>\n

To complete the proof of Lemma 1, we show the following claim.<\/p>\n

Claim 2.\u00a0<\/strong>Let \"f\" be the transducer from Claim 1. If the input to \"f\" contains a path with infinitely many accepting edges, then so does the output.<\/p>\n

Assume that the input \"w\" to the transducers contains a path with infinitely many accepting edges. Define a sequence \"\pi_0,\pi_1,\ldots\" of finite paths in \"f(w)\" as follows by induction. We want to preserve the\u00a0invariant that each \u00a0path in the sequence \"\pi_0,\pi_1,\ldots\" can be extended to an an accepting path in the graph \"w\". We begin with \"\pi_0\" being the edge-less\u00a0path that begins and ends in the root of the tree \"f(w)\". \u00a0This path \"\pi_0\" satisfies the invariant, by the assumption that the input \"w\" contains a path with infinitely many accepting edges. Suppose that \"\pi_n\" has been defined. By the invariant, we can extend \"\pi_n\" to an infinite path in the graph \"w\", and therefore we can extend \"\pi_n\" to a finite path that contains\u00a0at least one more accepting edge. \u00a0Define \"\pi_{n+1}\" to be the unique path in the tree \"f(w)\" which has the same source and target as the new path that extends \"\pi_n\" with at at leat one accepting edge.<\/p>\n

Define \"P_n\" to be the profile of the path \"\pi_n\". We claim that the sequence of profile \"P_0,P_1,P_2,\ldots\" has a well defined limit<\/p>\n

  <\/span>   <\/span>\"\[P_n \stackrel {n \to \infty} \to P \in \set{\text{accepting, non-accepting}}^\omega.\]\"<\/p>\n

This because \"P_{n+1}\" is lexicographically smaller or equal to some extension of \"P_n\". Therefore, if we take some \"i \in \set{0,1,\ldots}\", then the sequence<\/p>\n

  <\/span>   <\/span>\"\[P_1 [1..i], P_2[1..i], P_3[1..i], \ldots \in \set{\text{accepting, non-accepting}}^i\]\"<\/p>\n

gets lexicographically smaller and smaller, and thus it must stabilise (a few first terms in the sequence might be undefined). The stable value of the above sequence is the first \"i\" letters of the limit \"P\". Furthermore, the limit \"P\" must contain the letter “accepting” infinitely often. Toward a contradiction, suppose that \"P\" has the letter “accepting” finitely often, i.e. there is some \"i\" such that after \"i\", only the letter \u00a0“non-accepting” appears in \"P\". Choose \"n\" so\u00a0that \"\pi_n,\pi_{n+1},\ldots\" have profile consistent with \"P\" on the first \"i\" letters. By construction, the profile \"P_{n+1}\" has an\u00a0accepting letter on some position after \"i\",\u00a0and this property remains true for all subsequent profiles \"P_{n+2},P_{n+3}\ldots\" and therefore is also true in the limit, contradicting our assumption that \"P\" has only “non-accepting” letters after position \"i\".<\/p>\n

Consider the set of finite paths \u00a0in the tree \"f(w)\" which have profile that is a prefix of \"P\". This set of paths forms a tree (because it is prefix-closed). This tree has bounded degree (assuming the parent of a path is obtained by removing the last edge) and it contain paths of\u00a0arbitrary finite length (suitable prefixes of the paths \"\pi_1,\pi_2,\ldots\"). \u00a0\u00a0Therefore, by the K\u00f6ning lemma, this tree contains an infinite path. The profile of this path \"P\", and therefore contains \u00a0infinitely many accepting edges. \"\Box\"<\/p>\n","protected":false},"excerpt":{"rendered":"

The goal of this page is proving the following lemma. Lemma 1.\u00a0There exists a deterministic transducer     which outputs only trees and is invariant with respect to the universal B\u00fcchi language, i.e. if the input contains a path with infinitely many accepting edges, then so does the output and vice versa. Consider a -dag. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":539,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-547","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/547"}],"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=547"}],"version-history":[{"count":6,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/547\/revisions"}],"predecessor-version":[{"id":1387,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/547\/revisions\/1387"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/539"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=547"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}