Selected publications at LSV

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.

@article{BVdB-ijfcs2018,
   author = {Berwanger, Dietmar and {van den Bogaard}, Marie},
   DOI = {10.1142/S0129054118400026},
   journal = {International Journal of Foundations of Computer Science},
   month = feb,
   number = {02},
   pages = {165-185},
   publisher = {World Scientific},
   title = {Consensus Game Acceptors and Iterated Transductions},
   url = {https://www.worldscientific.com/doi/abs/10.1142/S0129054118400026},
   volume = {29},
   year = {2018},
}

About LSV

Select by Year