Consensus game acceptors

We present a game for recognising formal languages, in which two players with imperfect information need to coordinate on a common decision, given private input strings correlated by a finite graph. The players have a joint objective to avoid an inadmissible decision, in spite of the uncertainty induced by the input. We show that the acceptor model based on consensus games characterises context-sensitive languages, and conversely, that winning strategies in such games can be described by context-sensitive languages. We also discuss consensus game acceptors with a restricted observation pattern that describe nondeterministic linear-time languages. Joint work with Dietmar Berwanger. To appear in DLT 2015.

Authors

• Marie van den Bogaard

Keywords

No keywords are indexed for this paper.