论文标题
平均游戏的Strahler数字
The Strahler number of a parity game
论文作者
论文摘要
根树的strahler数量是其次要的完美二进制树的最大高度。提议平价游戏的Strahler数字被定义为其任何吸引子分解的树的最小的Strahler数量。事实证明，平价游戏可以在准线性空间中求解，并且及时可以在顶点〜$ n $的数量和$（{d}/{2k}）^k $中进行多项式解决，其中$ d $是优先级的数量，$ k $是strahler的数量。这种复杂性是准多项式的，因为Strahler数量最多是对数的顶点。证明是基于新的Strahler-宇宙树的新结构。 结果表明，奇偶校验游戏的Strahler数量是一个强大的参数：它与基于进度度量的树和Lehtinen〜（2018）定义的寄存器编号相吻合。因此，可以在准线性空间中求解奇偶校验游戏，并且在$（{d}/{2k}）^k $中的顶点和线性中是多项式的，其中$ k $是寄存器号。这大大改善了Lehtinen（2018）和Parys（2020）的有限寄存器号码的平等游戏的运行时间和空间。 基于小的strahler-通用树的算法的运行时间产生了一种新颖的折衷$ k \ cdot \ lg（d/k）= o（\ log n）$之间的两个自然参数，这些自然参数衡量了平等游戏的结构复杂性，可以在多项元素时间内解决平等游戏。这包括特殊情况，例如Calude，Jain Kussainov，Li和Stephan（2017），Jurdziński和Lazić（2017）和Lehtinen（2018）的结果所涵盖的这些参数的渐近设置（2017年），并大大扩展了这些环境的范围，例如$ d = 2^^^^^s. n} \ right）} $和$ k = o \！\ left（\ sqrt {\ lg n} \ right）$。
The Strahler number of a rooted tree is the largest height of a perfect binary tree that is its minor. The Strahler number of a parity game is proposed to be defined as the smallest Strahler number of the tree of any of its attractor decompositions. It is proved that parity games can be solved in quasi-linear space and in time that is polynomial in the number of vertices~$n$ and linear in $({d}/{2k})^k$, where $d$ is the number of priorities and $k$ is the Strahler number. This complexity is quasi-polynomial because the Strahler number is at most logarithmic in the number of vertices. The proof is based on a new construction of small Strahler-universal trees. It is shown that the Strahler number of a parity game is a robust parameter: it coincides with its alternative version based on trees of progress measures and with the register number defined by Lehtinen~(2018). It follows that parity games can be solved in quasi-linear space and in time that is polynomial in the number of vertices and linear in $({d}/{2k})^k$, where $k$ is the register number. This significantly improves the running times and space achieved for parity games of bounded register number by Lehtinen (2018) and by Parys (2020). The running time of the algorithm based on small Strahler-universal trees yields a novel trade-off $k \cdot \lg(d/k) = O(\log n)$ between the two natural parameters that measure the structural complexity of a parity game, which allows solving parity games in polynomial time. This includes as special cases the asymptotic settings of those parameters covered by the results of Calude, Jain Khoussainov, Li, and Stephan (2017), of Jurdziński and Lazić (2017), and of Lehtinen (2018), and it significantly extends the range of such settings, for example to $d = 2^{O\left(\sqrt{\lg n}\right)}$ and $k = O\!\left(\sqrt{\lg n}\right)$.
