Borel determinacy of concurrent games
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 n...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Published: |
Springer, Berlin, Heidelberg
2013
|
| _version_ | 1797052395613585408 |
|---|---|
| author | Gutierrez, J Winskel, G |
| author_facet | Gutierrez, J Winskel, G |
| author_sort | Gutierrez, J |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T18:31:01Z |
| format | Conference item |
| id | oxford-uuid:09a89817-7bea-4fc8-b761-4859e8772620 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T18:31:01Z |
| publishDate | 2013 |
| publisher | Springer, Berlin, Heidelberg |
| record_format | dspace |
| spelling | oxford-uuid:09a89817-7bea-4fc8-b761-4859e87726202022-03-26T09:19:31ZBorel determinacy of concurrent gamesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:09a89817-7bea-4fc8-b761-4859e8772620Symplectic Elements at OxfordSpringer, Berlin, Heidelberg2013Gutierrez, JWinskel, GJust 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. |
| spellingShingle | Gutierrez, J Winskel, G Borel determinacy of concurrent games |
| title | Borel determinacy of concurrent games |
| title_full | Borel determinacy of concurrent games |
| title_fullStr | Borel determinacy of concurrent games |
| title_full_unstemmed | Borel determinacy of concurrent games |
| title_short | Borel determinacy of concurrent games |
| title_sort | borel determinacy of concurrent games |
| work_keys_str_mv | AT gutierrezj boreldeterminacyofconcurrentgames AT winskelg boreldeterminacyofconcurrentgames |