Reduction to trees

Mikołaj Bojańczyk

zajęcia / courses

The goal of this page is proving the following lemma.

Lemma 1. There exists a deterministic transducer

$\begin{align*} f : [Q]^\omega \to [Q]^\omega \end{align*}$

which outputs only trees and is invariant with respect to the universal Büchi language, i.e. if the input contains a path with infinitely many accepting edges, then so does the output and vice versa.

Consider a $Q$ -dag. To make notation easier, we assume that there is a root, i.e. a vertex from which all others are reachable. This assumption can be made without loss of generality, because one can 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üchi automaton.

Profiles. For a path $\pi$ in a $Q$ -dag, define its profile 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 “accepting” is smaller than “non-accepting”. Call a finite path $\pi$ in $w$ optimal if it has lexicographically least profile among paths in $w$ that have the same source and target.

Claim 1. There is a transducer

$f : [Q]^\omega \to [Q]^\omega$

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$ .

Proof. 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$

To complete the proof of Lemma 1, we show the following claim.

Claim 2. 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.

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 invariant that each path 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 path that begins and ends in the root of the tree $f(w)$ . This 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 at least one more accepting edge. Define $\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.

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 \stackrel {n \to \infty} \to P \in \set{\text{accepting, non-accepting}}^\omega.$

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_1 [1..i], P_2[1..i], P_3[1..i], \ldots \in \set{\text{accepting, non-accepting}}^i$

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 “non-accepting” appears in $P$ . Choose $n$ so that $\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 accepting letter on some position after $i$ , and 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$ .

Consider the set of finite paths in 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 arbitrary finite length (suitable prefixes of the paths $\pi_1,\pi_2,\ldots$ ). Therefore, by the Köning lemma, this tree contains an infinite path. The profile of this path $P$ , and therefore contains infinitely many accepting edges. $\Box$

zajęcia / courses

Reduction to trees

Reduction to trees

Leave a Reply