Consensus Game Acceptors and Iterated Transductions
Abstract
We study a game for recognising formal languages, in which two players with imperfect information should coordinate on a common decision, given private input words correlated by a finite graph. The players have a common 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. Further, we describe the expressiveness of these games in terms of iterated synchronous transductions and identify a subclass that characterises context-free languages.
Communicated by Igor Potapov and Pavel Semukhin
Remember to check out the Most Cited Articles! |
---|
Check out these Handbooks in Computer Science |