2015/01/28 by Berwanger, Dietmar, Bogaard, Marie van den
#68Q45 #68Q85 #91A43 #Computer Science and Game Theory (cs.GT) #F.1.2 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #I.2.11 #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.1501.07131
We study a game for recognising formal languages, in which two players with imperfect information need to coordinate on a common decision, given private input words 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. Further, we describe the expressiveness of these games in terms of iterated synchronous transductions and identify a subclass that characterises context-free languages.