{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,6]],"date-time":"2024-07-06T00:07:02Z","timestamp":1720224422309},"reference-count":16,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2018,2]]},"abstract":"<jats:p>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.<\/jats:p><jats:p>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.<\/jats:p>","DOI":"10.1142\/s0129054118400026","type":"journal-article","created":{"date-parts":[[2018,4,11]],"date-time":"2018-04-11T07:34:45Z","timestamp":1523432085000},"page":"165-185","source":"Crossref","is-referenced-by-count":0,"title":["Consensus Game Acceptors and Iterated Transductions"],"prefix":"10.1142","volume":"29","author":[{"given":"Dietmar","family":"Berwanger","sequence":"first","affiliation":[{"name":"CNRS, ENS Paris-Saclay, LSV, Universit\u00e9 Paris-Saclay, Paris, France"}]},{"given":"Marie","family":"van den Bogaard","sequence":"additional","affiliation":[{"name":"CNRS, ENS Paris-Saclay, LSV, Universit\u00e9 Paris-Saclay, Paris, France"}]}],"member":"219","published-online":{"date-parts":[[2018,4,11]]},"reference":[{"key":"S0129054118400026BIB001","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585270"},{"key":"S0129054118400026BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/S0898-1221(00)00333-3"},{"key":"S0129054118400026BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-663-09367-1"},{"key":"S0129054118400026BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/s10849-009-9115-8"},{"key":"S0129054118400026BIB005","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"S0129054118400026BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90036-X"},{"key":"S0129054118400026BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)72023-8"},{"key":"S0129054118400026BIB008","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/5803.001.0001","volume-title":"Reasoning about Knowledge","author":"Fagin R.","year":"1995"},{"key":"S0129054118400026BIB009","doi-asserted-by":"crossref","DOI":"10.1201\/b10581","volume-title":"Games, Puzzles, and Computation","author":"Hearn R. A.","year":"2009"},{"key":"S0129054118400026BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(64)90120-2"},{"key":"S0129054118400026BIB012","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2659"},{"key":"S0129054118400026BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00283-6"},{"key":"S0129054118400026BIB019","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139195218"},{"key":"S0129054118400026BIB020","volume-title":"Formal Languages","author":"Salomaa A.","year":"1973"},{"key":"S0129054118400026BIB021","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2000109"},{"key":"S0129054118400026BIB022","series-title":"Lecture Notes in Pure and Applied Mathematics","first-page":"331","volume-title":"Complexity, Logic, and Recursion Theory","volume":"18","author":"van Emde Boas P.","year":"1997"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054118400026","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,5]],"date-time":"2024-07-05T22:20:00Z","timestamp":1720218000000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054118400026"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2]]},"references-count":16,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2018,4,11]]},"published-print":{"date-parts":[[2018,2]]}},"alternative-id":["10.1142\/S0129054118400026"],"URL":"https:\/\/doi.org\/10.1142\/s0129054118400026","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2]]}}}