The winning ways of concurrent games
A bicategory of concurrent games, where nondeterministic strategies are formalized as certain maps of event structures, was introduced recently. This paper studies an extension of concurrent games by winning conditions, specifying players' objectives. The introduction of winning conditions rais...
| Những tác giả chính: | , , |
|---|---|
| Định dạng: | Conference item |
| Ngôn ngữ: | English |
| Được phát hành: |
IEEE
2012
|
| _version_ | 1826306197473460224 |
|---|---|
| author | Clairambault, P Gutierrez, J Winskel, G |
| author_facet | Clairambault, P Gutierrez, J Winskel, G |
| author_sort | Clairambault, P |
| collection | OXFORD |
| description | A bicategory of concurrent games, where nondeterministic strategies are formalized as certain maps of event structures, was introduced recently. This paper studies an extension of concurrent games by winning conditions, specifying players' objectives. The introduction of winning conditions raises the question of whether such games are determined, that is, if one of the players has a winning strategy. This paper gives a positive answer to this question when the games are well-founded and satisfy a structural property, race-freedom, which prevents one player from interfering with the moves available to the other. Uncovering the conditions under which concurrent games with winning conditions are determined opens up the possibility of further applications of concurrent games in areas such as logic and verification, where both winning conditions and determinacy are most needed. A concurrent-game semantics for predicate calculus is provided as an illustration. |
| first_indexed | 2024-03-07T06:44:17Z |
| format | Conference item |
| id | oxford-uuid:fa589c4c-cefe-49b3-ab9f-81e674f5571b |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T06:44:17Z |
| publishDate | 2012 |
| publisher | IEEE |
| record_format | dspace |
| spelling | oxford-uuid:fa589c4c-cefe-49b3-ab9f-81e674f5571b2022-03-27T13:04:58ZThe winning ways of concurrent gamesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:fa589c4c-cefe-49b3-ab9f-81e674f5571bEnglishSymplectic Elements at OxfordIEEE2012Clairambault, PGutierrez, JWinskel, GA bicategory of concurrent games, where nondeterministic strategies are formalized as certain maps of event structures, was introduced recently. This paper studies an extension of concurrent games by winning conditions, specifying players' objectives. The introduction of winning conditions raises the question of whether such games are determined, that is, if one of the players has a winning strategy. This paper gives a positive answer to this question when the games are well-founded and satisfy a structural property, race-freedom, which prevents one player from interfering with the moves available to the other. Uncovering the conditions under which concurrent games with winning conditions are determined opens up the possibility of further applications of concurrent games in areas such as logic and verification, where both winning conditions and determinacy are most needed. A concurrent-game semantics for predicate calculus is provided as an illustration. |
| spellingShingle | Clairambault, P Gutierrez, J Winskel, G The winning ways of concurrent games |
| title | The winning ways of concurrent games |
| title_full | The winning ways of concurrent games |
| title_fullStr | The winning ways of concurrent games |
| title_full_unstemmed | The winning ways of concurrent games |
| title_short | The winning ways of concurrent games |
| title_sort | winning ways of concurrent games |
| work_keys_str_mv | AT clairambaultp thewinningwaysofconcurrentgames AT gutierrezj thewinningwaysofconcurrentgames AT winskelg thewinningwaysofconcurrentgames AT clairambaultp winningwaysofconcurrentgames AT gutierrezj winningwaysofconcurrentgames AT winskelg winningwaysofconcurrentgames |