I&C Journal 2017 Journal Article
Visibly pushdown modular games,
- I. De Crescenzo
- S. La Torre
- Y. Velner
Recursive game graphs can be used to reason about the control flow of sequential programs with recursion. Here, the most natural notion of strategy is the modular one, i. e. , a strategy that is local to a module and is oblivious to previous module invocations. In this work, we study for the first time modular strategies with respect to winning conditions expressed as languages of pushdown automata. We show that pushdown modular games are undecidable in general, and become decidable for visibly pushdown automata specifications. Our solution relies on a reduction to modular games with finite-state winning conditions. We carefully characterize the computational complexity of this decision problem by also considering as winning conditions nondeterministic and universal Büchi or co-Büchi visibly pushdown automata, and CaRet or Nwtl temporal logic formulas. As a further contribution, we present a different synthesis algorithm that improves on known solutions for large specifications and many exits.