Antichains for Inclusion Games
Lukáš Holík, Roland Meyer, Sebastian Muskalla · arXiv (Cornell University) · 2016
We study two-player games played on the infinite graph of sentential forms induced by a context-free grammar (that comes with an ownership partitioning of the non-terminals). The winning condition is inclusion in a regular language for the terminal words derived in maximal plays. Our contribution is an algorithm to compute a finite representation of all plays starting in a non-terminal. The representation is compositional and, once obtained for the non-terminals, immediate to lift to sentential forms. The result has three consequences. It is decidable whether a position is in the winning region of a player. The winning regions have a finite representation. We can compute a winning strategy. Technically, the algorithm is a fixed-point iteration over a novel domain that generalizes the transition monoid to negation-free Boolean formulas. It takes doubly exponential time to check whether a winning strategy exists, which is proven to be the optimal time complexity. We show that this domain is not only expressive but also algorithmically appealing. It is compatible with recent antichain- and subsumption-based optimizations, and admits a lazy evaluation strategy.