On the determinacy of concurrent games on event structures with infinite winning sets

Julian Gutierrez, Glynn Winskel

Research output: Contribution to journalArticleResearchpeer-review

4 Citations (Scopus)

Abstract

We consider nondeterministic concurrent games played on event structures and study their determinacy problem - the existence of winning strategies. It is known that when the winning conditions of the games are characterised by a collection of finite winning sets/plays, a restriction (called race-freedom) on the boards where the games are played guarantees determinacy. However the games may no longer be determined when the winning sets are infinite. This paper provides a study of concurrent games and nondeterministic winning strategies by analysing conditions that ensure determinacy when infinitely many events are played, that is, when the winning sets are infinite. The main result is a determinacy theorem for a class of games with a bounded concurrency property and infinite winning sets shown to be finitely decidable.

Original languageEnglish
Pages (from-to)1119-1137
Number of pages19
JournalJournal of Computer and System Sciences
Volume80
Issue number6
DOIs
Publication statusPublished - Sept 2014
Externally publishedYes

Keywords

  • Concurrency theory
  • Games
  • Mathematical logic

Cite this