A Collapse of the Parity Index Hierarchy of Tree Automata, Based on Cantor-Bendixson Ranks

If a parity graph $G$, of maximal priority at most some even $h$, is even, we can construct a greedy attractor decomposition recursively for it as follows. Let $H$ be the set of edges of priority $h$ and $A_0$ the attractor of $H$.

Then, we define each $S_i$ and $A_i$ for $i>0$ inductively. First let for $i$ an ordinal. $V_i$ is either empty, or $G_i=(G\setminus H)\upharpoonright V_i$ is an even parity graph with maximal priority no larger than $h-1$. Let $S_i$ consist of all positions of $G_i$ from where $h-1$ can not be reached. If $V_i$ is non-empty, there must be such positions, since otherwise one could build a path which sees infinitely many $h-1$, contradicting that $G_i$ is an even graph. Let $A_i$ be the attractor of $S_i$ in $G_i$ and let $D_i$ be an $h-2$-attractor decomposition of $S_i$.

Let us assume $V_i$ is non-empty for all countable ordinals $i$. Since all the $V_i$s are disjoint, their union is uncountable, since there are uncountably many ordinals smaller than ${\omega }_1$. However we only work with countable graphs, which gives a contradiction. Thus $V_i$ must be empty for some countable ordinal $i$. Hence .

Observe that this attractor decomposition is, by construction, greedy.

For the other direction, assume that a parity graph has an attractor decomposition of height $h$. We proceed by induction on the height of the attractor decomposition, that is, the number of priorities in $G$. The base case of the unique priority $0$ is trivial since all paths are even.

For the induction step, we observe that any infinite path of $G$ must either eventually remain in some $(G\setminus H)\upharpoonright S_{\mathrm{\ell }}$ for or reach $H$ infinitely often, due to Lemma 3. In the latter case, the path is even since all edges in $H$ are of the highest possible priority. In the former case, since each $S_{\mathrm{\ell }}$ has an attractor decomposition of height $h-2$, by the induction hypothesis, we are done. $◀$

Let $G$ be an even parity graph of maximal priority an even $h$ or an odd $h-1$ with vertices $V$. Since $G$ is an even parity graph of maximal priority at most $h$, it has by Proposition 4 an $h$-height attractor decomposition. Let $D$ be a greedy such decomposition of width $\mathrm{\ell }$ and not of any width (that is, the whole width $\mathrm{\ell }$ is used somewhere). We will argue that $G$ has an $\mathrm{\ell }-1$-pattern.

Since $D$ indeed uses somewhere the whole width $\mathrm{\ell }$, some induced subgraph has a decomposition .

We show by induction that for all finite , the graph $G^{\prime }\upharpoonright (A_1\cup \mathrm{\dots }\cup A_i)$, rooted at any vertex in $A_i$, has an $i$-pattern. $G^{\prime }$ therefore has an $\mathrm{\ell }-1$-pattern if $\mathrm{\ell }$ is finite, and an $i$-pattern for all finite $i$ otherwise.

First, we consider the base case $i=1$. Observe that $S_1$ has no terminal vertices as $A_0$ is an attractor and $G^{\prime }$ has no terminal vertices. It follows that every vertex in $S_1$ is on an infinite path. Then, as every vertex of $A_1$ is in the attractor of $S_1$, from any vertex of $A_1$ there is a path in $A_1$ to an infinite path in $S_1$. It follows that in the graph $G^{\prime }\upharpoonright A_1$, a $1$-pattern is accessible from every position of $A_1$.

For the induction step, we similarly observe that as $S_i$ has no terminal vertices, every vertex of $S_i$ is on an infinite path in $S_i$. From greediness of $D^{\prime }$, each vertex of $S_i$ also has a path into $A_{i-1}$ in $G^{\prime }$; indeed, a vertex without such a path could be in $S_{i-1}$, contradicting greediness. Then, a $i-1$-pattern in $A_{i-1}$ is accessible infinitely often on every path in $S_i$; it follows that there is an $i$-pattern from every position in $S_i$, and by extension in $A_i$. Thus a greedy $\mathrm{\ell }$-width attractor decomposition witnesses that the rank of the graph is at least $\mathrm{\ell }-1$.

Then, if an even parity graph is of rank $k$, it must have a greedy attractor decomposition, from Proposition 4, but this greedy attractor decomposition can have width at most $k+1$. $◀$

Let $t=(V,E)$, and let $\pi :V\times \{1,\mathrm{\dots },n\}\to V$ be the projection of vertices of $t\times K_n$ to their $t$ coordinate. Let us assume that $(V_0,\mathrm{\dots },V_{k-1})$ is a tree-like pattern of $t\times K_n$. We show that two distinct vertices of the pattern must have different $t$ coordinates. This is enough to ensure that $(\pi (V_0),\mathrm{\dots },\pi (V_{k-1}))$ is a $k$-pattern of $t$. We first show that two vertices in different components of the pattern have different $t$ coordinates, then we show that it also holds for two vertices in the same component of the pattern.

Two vertices that have the same $t$ coordinate can reach the same vertices in $t\times K_n$. Then, two vertices in different components of the pattern cannot have the same $t$ coordinate, since the pattern is tree-like.

Let $i\in \{0,\mathrm{\dots },k-1\}$, let $V_i={⨄}_{\mathrm{\ell }\in \mathbb{N}}{V}_i^{\mathrm{\ell }}$ such that the $V_i^{\mathrm{\ell }}$s are paths with disjoint reachability sets. If two distinct vertices have the same $t$ coordinate, they have to lie in the same $V_i^{\mathrm{\ell }}$, for some $\mathrm{\ell }\in \mathbb{N}$. However given two vertices of $V_i^{\mathrm{\ell }}$, one can reach the other as $V_i^{\mathrm{\ell }}$ is a path, which means that the vertices have different $t$ coordinate. $◀$

We have that $V_{n+1}$ is an infinite path $p$ in $t\times K_n$. We construct a sequence $W_1^0,W_1^1,\mathrm{\dots }$ and define $W_1={\bigcup }_i{W}_1^i$. We will show that we can construct this sequence inductively with the following properties for $i,j\ge 0$:

• $\mathrm{■}$

  there is a path in $t\times K_n$ from $p[i]$ to any vertex of $W_1^i$,

• $\mathrm{■}$

  $W_1^i$ is an infinite path which goes near $V_0$ infinitely often,

• $\mathrm{■}$

  if $v$ is reachable in $t\times K_n$ from $W_1^i$ and $W_1^j$ then $i=j$

• $\mathrm{■}$

  there is no path in $t\times K_n$ from any vertex of $W_1^i$ to $V_{n+1}$.

The first condition ensures that $(W_1,V_{n+1})$ is a pattern and the second that $(V_0,W_1)$ is a pattern. The last two conditions ensure that $(W_1,V_{n+1})$ is tree-like. Thus we only have left to construct the sequence $W_1^0,W_1^1,\mathrm{\dots }$.

Initial case: Let $w\in V_{n+1}$ and let $w{q}_{n+1}{w}_n{q}_n\mathrm{\cdots }{q}_1{w}_1$ be a path such that $q_i\in V_i^{\ast },w_i\in V_i$ for $i\in [1,n+1]$. Let us consider infinite paths $w_i{r}_i\in V_i^{\omega }$ for $i\in [1,n]$. Then, the projections $\pi (p),\pi (r_1),\mathrm{\dots },\pi (r_n)$ on $t$ of these paths cannot all be eventually equal since the $V_i$s are disjoint and there are only $n$ copies of each vertex of $t$ in $t\times K_n$. Let $i$ be an index such that $\pi (r_i)$ and $\pi (p)$ are eventually disjoint, meaning they end up in different branches of $t$. Let $u$ be the first vertex of $w{q}_{n+1}\mathrm{\cdots }{q}_{i+1}{w}_i{r}_i$ such that $\pi (u)$ is not on the branch $\pi (p)$. Note that there is an edge from a vertex of $p$ to $u$ but there is no path from $u$ to any vertex of $p$. From $u$ we choose a path $uq$ in $V_n^{\ast }\mathrm{\cdots }{V}_2^{\ast }{V}_1^{\omega }$ which goes near $V_0$ infinitely often, which is possible by the definition of pattern. The set $W_1^0$ is defined as the set of vertices of $uq$.

Assume we have constructed $W_1^0,\mathrm{\dots },W_1^i$, with the desired properties. We choose a vertex $w\in V_{n+1}$ such that $w$ cannot reach any of the $W_1^j$s, for $j\in [0,i]$. Such a $w$ has to exist, since the projections of the $W_1^j$s are ultimately disjoint from $\pi (p)$.

Similarly to the initial case, we can find a path $uq\in V_n^{\ast }\mathrm{\cdots }{V}_1^{\omega }$ which goes near $V_0$ infinitely often, such that there is a path in $V_{n+1}$ from $w$ to a predecessor of $u$, and there is no path from $u$ to a vertex of $V_{n+1}$. Let $W_1^{i+1}$ be the set of vertices of $uq$. Since $w$ cannot reach $W_1^j$s, the vertices of $W_1^{i+1}$ cannot reach $W_1^j$s, a fortiori. It remains to show that there is no path from $W_1^j$ to $W_1^{i+1}$ for $j\in [0,i]$. Assume the contrary, then there is a vertex $v$ in $W_1^{i+1}$ and path from $p[0]$ which does not go through $w$ to $v$, by going through $W_1^j$. Furthermore, there is also a path which goes through $w$. Let $w^{\prime }\in V_{n+1}\cup {\bigcup }_{0\le j\le i+1}{W}_1^j$ be a vertex distinct from $w$. If $w^{\prime }\in V_{n+1}$, then $\pi (w)\ne \pi (w^{\prime })$, since $V_{n+1}$ is a path. If $w^{\prime }\notin V_{n+1}$, since from the induction assumption there is no path from ${\bigcup }_{0\le j\le i+1}{W}_1^j$ to $V_{n+1}$, we have $\pi (w)\ne \pi (w^{\prime })$. Then there are two distinct paths in $t$ from the same vertex to $\pi (v)$, a contradiction. $◀$

From a graph $G$ of rank $k$, the product $G\times K_n$ with the clique over $n$ vertices, has rank at least $kn$. We show below that this is optimal for trees, and leave open the question whether this holds in general.

The statement is trivially true for $n\le 1$, so assume $n\ge 2$ in the following.

We show by induction on $k$ that given $(V_0,\mathrm{\dots },V_{kn})$ a $kn+1$-pattern of $t\times K_n$, such that $V_{kn}$ is a path, one can obtain a tree-like $k+1$ pattern $(W_0,\mathrm{\dots },V_{kn})$. From Proposition 14, this is enough to obtain the result.

Clearly this holds for $k=0$. Let us assume it holds for some $k\ge 0$.

Let $(V_0,\mathrm{\dots },V_{(k+1)n})$ be a $(k+1)n+1$-pattern of $t\times K_n$ We use Proposition 16 on the pattern $(V_{kn-1},\mathrm{\dots },V_{(k+1)n})$ and obtain $(V_{kn-1},W_2,V_{(k+1)n})$, an almost tree-like pattern. We have that $W_2$ is a union of disjoint paths $W_2^i$, $i\ge 0$, with the property that no vertex can be reached from two distinct paths. For each $i\in \mathbb{N}$, $(V_0,\mathrm{\dots },V_{kn-1},W_2^i)$ is a $kn+1$-pattern with $W_2^i$ an infinite path. From the induction assumption, we can obtain a tree-like $k$-pattern $(W_0^i,\mathrm{\dots },W_{k-1}^i,W_2^i)$. Since $(W_2,V_{(k+1)n})$ is tree-like, from the Glueing Lemma we obtain a tree-like $k+1$ pattern, which concludes the induction.

To finish the proof, we only need to show that given $(V_0,\mathrm{\dots },V_{kn})$ a $kn+1$-pattern of $t\times K_n$ we can assume without loss of generality that $V_{kn}$ is a path. To do this we only need to restrict $V_{kn}$ to a path which goes near $V_{kn-1}$ infinitely often, which can easily be done. $◀$

Now that we have proved the Product Lemma, we need another simpler lemma dealing with the rank of trees obtained by what we call subdivision of vertices.

We prove the statement for even $p$ by induction on $p$; the statement for odd $p$ follows easily. In the base case, where $p=0$, for every $k\in \mathbb{N}$, all parity graphs have a $k$-width attractor decomposition, and indeed by the construction of ${ℬ}_{0,k}$, it accepts everything.

In the induction step, we assume the claim for $p$, and prove it for $p+2$. If a parity graph $G$ with priorities up to $p+2$ has a $k$-width attractor decomposition , then Eve can use the following strategy in the acceptance game $𝒢(G,{ℬ}_{p+2,k})$: At a position $(v,q_i)$ with $v\in A_0\cup \mathrm{\dots }\cup A_i$, Eve remains in $q_i$ until she reaches a position $(v^{\prime },q_i)$ where $v^{\prime }\in S_{\mathrm{\ell }}$ for some $\mathrm{\ell }\le i$; from there, she moves to ${\iota }_i$ and follows a strategy that is winning in the acceptance game of ${ℬ}_{\mathrm{\ell }}$ and the tree rooted at $v^{\prime }$ and restricted to priorities up to $p$, from the IH. Then, if no priority equal or larger than $p+1$ occurs, the play will remains within in ${ℬ}_{\mathrm{\ell }}$, and is winning by IH. If priority $p+2$ occurs, the game moves to some $(v^{\prime \prime },q_b)$, of priority $2$; if $p+1$ occurs, the game moves to some $(v^{\prime \prime },q_{i-1})$ where $v^{\prime \prime }\in A_0\cup \mathrm{\cdots }\cup A_{i-1}$. This is the case since $S_{\mathrm{\ell }}$ does not contain priority $p+1$ and any path from $S_{\mathrm{\ell }}$ that does not contain $p+2$ but contains $p+1$ progresses to some $A_j$ with (Lemma 3). If $v^{\prime \prime }\in A_0$, then the priority $p+2$ will eventually occur, and the game moves to some $(v^{\prime \prime },q_b)$, of priority $2$.

We now argue that this strategy is winning for Eve. Indeed, a play can either eventually remain in some ${ℬ}_{\mathrm{\ell }}$ component, in which case it is winning by induction hypothesis, or eventually exits every ${ℬ}_{\mathrm{\ell }}$. In the latter case, the only way for Eve to lose would be to get stuck in $q_0$ and never see the priority $p+2$. However, since the $G$-component of the play moves to some $A_j$ with whenever it exists a component ${ℬ}_{\mathrm{\ell }}$, the play can only reach $(v,q_0)$ where $v\in A_0$, in which case $p+2$ will eventually occur.

Furthermore, if Eve has a winning strategy in the acceptance game, then the highest priority on all infinite paths of $G$ is even because all accepting cycles in ${ℬ}_{p,k}$ read words of which the highest priority is even; hence ${ℬ}_{p+2,k}$ does not accept any odd graphs.

The statement for odd $p$ follows as ${ℬ}_{p,k}$ is then as ${ℬ}_{p+1,k}$ without any $p+1$ transitions. $◀$

We now build, from any APT $𝒜$ of priorities up to $p$ an ABT $ℬ$ that agrees with $𝒜$ over trees of rank at most $k$ by composing it with ${ℬ}_{p,k^{\prime }}$ where $k^{\prime }$ only depends on $k$ and $𝒜$.

Consider an APT $𝒜$ with priorities up to $p$. Let $k^{\prime }=kc+1$ for the constant $c$ in Corollary 20; then we know that the game $𝒢(t,𝒜)$ has rank strictly less than $k^{\prime }$ for all trees $t$ of rank up to $k$.

By Lemma 22, the ABT ${ℬ}_{p,k^{\prime }}$ accepts all parity graphs with priorities up to $p$ with a $k^{\prime }$-width attractor decomposition, and rejects odd parity graphs. By construction, ${ℬ}_{p,k^{\prime }}$ only has $\mathrm{\square }$ modalities. Then, we build the required ABT $ℬ$ by taking the synchronous composition $𝒜\times {ℬ}_{p,k^{\prime }}$ of $𝒜$ and ${ℬ}_{p,k^{\prime }}$. This is an ABT that accepts a tree $t$ if and only if ${ℬ}_{p,k^{\prime }}$ accepts some tree induced by a strategy for Eve in $𝒢(t,𝒜)$. The details of this composition are as expected, detailed in Appendix B.

In words, $ℬ$ is an automaton that uses $𝒜$ to process the input tree, and at each step, ${ℬ}_{p,k^{\prime }}$ processes the priority that $𝒜$ would produce, which adds some nondeterministic choices. We argue $ℬ$ accepts any tree $t$ such that in $𝒢(t,𝒜)$ Eve has a winning strategy that induces a graph with a $k^{\prime }$-width attractor decomposition, and rejects $t\notin L(𝒜)$.

Assume $t$ is such that in $𝒢(t,𝒜)$ Eve has a winning strategy $\sigma$ that induces an even graph $G_{\sigma }$ with a $k^{\prime }$-width attractor decomposition. Let ${\sigma }^{\prime }$ be Eve’s winning strategy in $𝒢(G_{\sigma },{ℬ}_{p,k^{\prime }})$. We can then compose these strategies to obtain a winning strategy in $𝒢(t,ℬ)$. Indeed, positions of $𝒢(t,ℬ)$ can be seen as a position of $𝒢(t,𝒜)$ paired with states of ${ℬ}_{p,k^{\prime }}$, to which are added, after the resolution of the boolean combinations in transition conditions of $𝒜$, the resolution of the boolean combinations in the transition condition of ${ℬ}_{p,k^{\prime }}$ corresponding to a transition on the priority of the next state in $𝒜$. In the composition strategy, $\sigma$ determines the choices between successors in $t$ at $\mathrm{◇}$-modalities and choices at disjunctions in the transition conditions of $𝒜$, while ${\sigma }^{\prime }$ determines choices at disjunctions in the transition conditions of ${ℬ}_{p,k^{\prime }}$. The existence of $\sigma$ guarantees the existence of ${\sigma }^{\prime }$, and that the composition strategy remains in the restriction of $𝒢(t,ℬ)$ to ${𝒢}_{\sigma }$ in the $𝒢(t,𝒜)$-part of the game. Since the priorities of $ℬ$ come from the priorities of ${ℬ}_{p,k^{\prime }}$, the fact that ${\sigma }^{\prime }$ is winning for Eve ensures that the composition of $\sigma$ and ${\sigma }^{\prime }$ is winning for Eve.

Conversely, if $t\notin L(𝒜)$, then Adam has a winning strategy $\tau$ in $𝒢(t,𝒜)$. He can use $\tau$ directly in $𝒢(t,ℬ)$ as $ℬ$ does not add any universal choices ($\mathrm{\square }$ or $\wedge$) beyond those of $𝒜$. Let $w$ be the sequence of priorities induced by the projection of a $\tau$-consistent play of $𝒢(t,ℬ)$ on the $𝒢(t,𝒜)$ component; the highest priority seen infinitely often on $w$ is odd. The projection of the same play on ${ℬ}_{p,k}$ is a path of ${ℬ}_{p,k}$ that processes $w$. By construction, no accepting cycle of ${ℬ}_{p,k}$ processes a word of which the highest maximal priority is odd, so this path is rejecting, and $\tau$ is a winning strategy for Adam in $𝒢(t,ℬ)$.

For all $t$ of rank up to $k$, $𝒢(t,𝒜)$ has rank strictly less than $k^{\prime }$, if $t\in L(𝒜)$ then Eve has a winning strategy that induces an even graph that also has rank less than $k^{\prime }$. From Lemma 8, it has a $k^{\prime }$-width attractor decomposition, and therefore $ℬ$ accepts $t$; if $t\notin L(𝒜)$ then $ℬ$ rejects $t$, so $ℬ$ agrees with $𝒜$ on such trees. By construction, if $𝒜$ is nondeterministic, so is $ℬ$ as $B_{p,k^{\prime }}$ only has nondeterministic choices; if $𝒜$ is coBüchi, then $ℬ$ is weak since ${ℬ}_{1,k^{\prime }}$ is weak. $◀$

Given $𝒜$, from Theorem 23 there is an alternating Büchi automaton $ℬ$ that agrees with $𝒜$ over trees of Cantor-Bendixson rank at most $k$. Let $𝒞$ be the standard syntactic coBüchi complement of $ℬ$, obtained by exchanging $\wedge$ and $\vee$, and $\mathrm{◇}$ and $\mathrm{\square }$, and replacing priority $1$ with $0$ and $2$ with $1$. Then $𝒞$ accepts a tree of rank at most $k$ if and only if $𝒜$ rejects it. Again from Theorem 23, there is an alternating weak automaton ${𝒞}^{\prime }$ that agrees with $𝒞$ on all trees of rank at most $k$. Then, the syntactic complement ${ℬ}^{\prime }$ of ${𝒞}^{\prime }$, is an alternating weak automaton that agrees with $𝒜$ on all trees of rank at most $k$. $◀$