论文标题
较弱的穆勒条件使延迟游戏艰难
Weak Muller Conditions Make Delay Games Hard
论文作者
论文摘要
我们表明，通过确定性和非确定性弱的Muller Automata给出的获胜条件解决延迟游戏分别为2 exptime-Complete 3 Exptime-Complete。此外，双重和三重指数的lookahead是必要的，足以赢得此类游戏。这些结果首先表明用于指定获胜条件的自动机类型的简洁性会影响这些问题的复杂性。
We show that solving delay games with winning conditions given by deterministic and nondeterministic weak Muller automata is 2EXPTIME-complete respectively 3EXPTIME-complete. Furthermore, doubly and triply exponential lookahead is necessary and sufficient to win such games. These results are the first that show that the succinctness of the automata types used to specify the winning conditions has an influence on the complexity of these problems.
