TY - GEN
T1 - Borel determinacy of concurrent games
AU - Gutierrez, Julian
AU - Winskel, Glynn
PY - 2013
Y1 - 2013
N2 - Just as traditional games can be represented by trees, so concurrent games can be represented by event structures. We show the determinacy of such concurrent games with Borel sets of configurations as winning conditions, provided they are race-free and bounded-concurrent. Both properties are shown necessary. The determinacy proof proceeds via a reduction to the determinacy of tree games, and the determinacy of these in turn reduces to the determinacy of Gale-Stewart games.
AB - Just as traditional games can be represented by trees, so concurrent games can be represented by event structures. We show the determinacy of such concurrent games with Borel sets of configurations as winning conditions, provided they are race-free and bounded-concurrent. Both properties are shown necessary. The determinacy proof proceeds via a reduction to the determinacy of tree games, and the determinacy of these in turn reduces to the determinacy of Gale-Stewart games.
UR - http://www.scopus.com/inward/record.url?scp=84882788728&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-40184-8_36
DO - 10.1007/978-3-642-40184-8_36
M3 - Conference Paper
AN - SCOPUS:84882788728
SN - 9783642401831
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 516
EP - 530
BT - Concurrency Theory - 24th International Conference, CONCUR 2013, Proceedings
PB - Springer
T2 - 24th International Conference on Concurrency Theory, CONCUR 2013
Y2 - 27 August 2013 through 30 August 2013
ER -