We consider parity games played on special pushdown graphs, namely those generated by one-counter processes. For parity games on pushdown graphs, it is known from [22] that deciding the winner is an ExpTime-complete problem. An important corollary of this result is that the µ-calculus model checking problem for pushdown processes is Exp-Time-complete. As one-counter processes are special cases of pushdown processes, it follows that deciding the winner in a parity game played on the transition graph of a one-counter process can be achieved in Ex-pTime. Nevertheless the proof for the ExpTime-hardness lower bound of [22] cannot be adapted to that case. Therefore, a natural question is whether the ExpTime upper bound can be improved in this special case. In this paper, we adapt techniques from [11, 4] and provide a PSpace upper bound and a DP-hard lower bound for this problem. We also give two important consequences of this result. First, we improve the best upper bound known for model-checking one-counter processes against µ-calculus. Second, we show how these games can be used to solve pushdown games with winning conditions that are Boolean combinations of a parity condition on the control states with conditions on the stack height. ⋆
In REF it was shown that deciding the winner in one-counter parity games is in PSpace.
Parity games played on transition graphs of one-counter processes
FoSSaCS
Computer Science