A game-theoretic characterization of Boolean grammars

We obtain a simple, purely game-theoretic characterization of Boolean grammars [A. Okhotin, Boolean grammars, Information and Computation, 194(1) (2004) 19–48]. In particular, we propose a two-player infinite game of perfect information for Boolean grammars, which is equivalent to their well-founded semantics. The game is directly applicable to the simpler classes of conjunctive and context-free grammars, and offers a promising new connection between game theory and formal languages.