A Characterisation of Context-Sensitive Languages by Consensus Games
Dietmar Berwanger, Marie van den Bogaard · arXiv (Cornell University) · 2015
We propose a game for recognising formal languages, in which two players with imperfect information need to coordinate on a common decision, given private input information. The players have a joint objec- tive to avoid an inadmissible decision, in spite of the uncertainty induced by the input. We show that this model of consensus acceptor games characterises context-sensitive languages, and conversely, that winning strategies in such games can be described by context-sensitive languages. This im- plies that it is undecidable whether a consensus game admits a winning strategy, and, even if so, it is PSPACE-hard to execute one. On the pos- itive side, we show that whenever a winning strategy exists, there exists one that can be implemented by a linear bounded automaton.