Solving parity games in big steps

详细信息    查看全文

• 作者：Sven Schewe ^{sven.schewe@liverpool.ac.uk" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Parity games ; Finite games of infinite duration
• 刊名：Journal of Computer and System Sciences
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：84
• 期：Complete
• 页码：243-262
• 全文大小：650 K

文摘

This article proposes a new algorithm that improves the complexity bound for solving parity games. Our approach combines McNaughton's iterated fixed point algorithm with a preprocessing step, which is called prior to every recursive call. The preprocessing uses ranking functions similar to Jurdziński's, but with a restricted co-domain, to determine all winning regions smaller than a predefined parameter. The combination of the preprocessing step with the recursive call guarantees that McNaughton's algorithm proceeds in big steps, whose size is bounded from below by the chosen parameter. Higher parameters lead to smaller call trees, but they also result in an expensive preprocessing step. An optimal parameter balances the cost of the recursive call and the preprocessing step, resulting in an improvement of the known upper bound for solving parity games from class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022000016300952&_mathId=si1.gif&_user=111111111&_pii=S0022000016300952&_rdoc=1&_issn=00220000&md5=fed7bd4024df0d1995afaa64eea26793">class="imgLazyJSB inlineImage" height="28" width="79" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0022000016300952-si1.gif">class="mathContainer hidden">class="mathCode">$O\left(m{\left(\frac{2n}{c}\right)}^{\frac{1}{2}c}\right)$ to approximately class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022000016300952&_mathId=si2.gif&_user=111111111&_pii=S0022000016300952&_rdoc=1&_issn=00220000&md5=1d277c555c7d60408748fda5ca987139">class="imgLazyJSB inlineImage" height="28" width="96" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0022000016300952-si2.gif">class="mathContainer hidden">class="mathCode">$O\left(m{\left(\frac{6e^{1.\bar{6}}n}{c^2}\right)}^{\frac{1}{3}c}\right)$.