Borel determinacy of concurrent games

Julian Gutierrez, Glynn Winskel

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

1 Citation (Scopus)


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.

Original languageEnglish
Title of host publicationConcurrency Theory - 24th International Conference, CONCUR 2013, Proceedings
Number of pages15
ISBN (Print)9783642401831
Publication statusPublished - 2013
Externally publishedYes
Event24th International Conference on Concurrency Theory, CONCUR 2013 - Buenos Aires, Argentina
Duration: 27 Aug 201330 Aug 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8052 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference24th International Conference on Concurrency Theory, CONCUR 2013
CityBuenos Aires

Cite this