As they are conventionally formulated, Boolean games assume that players make their choices in ignorance of the choices being made by other players – they are games of simultaneous moves. For many settings, this is clearly unrealistic. In this paper, we show how Boolean games can be enriched by dependency graphs which explicitly represent the informational dependencies between variables in a game. More precisely, dependency graphs play two roles. First, when we say that variable x depends on variable y, then (...) we mean that when a strategy assigns a value to variable x, it can be informed by the value that has been assigned to y. Second, and as a consequence of the first property, they capture a richer and more plausible model of concurrency than the simultaneous-action model implicit in conventional Boolean games. Dependency graphs implicitly define a partial ordering of the run-time events in a game: if x is dependent on y, then the assignment of a value to y must precede the assignment of a value to x; if x and y are independent, however, then we can say nothing about the ordering of assignments to these variables—the assignments may occur concurrently. We refer to Boolean games with dependency graphs as partial-order Boolean games. After motivating and presenting the partial-order Boolean games model, we explore its properties. We show that while some problems associated with our new games have the same complexity as in conventional Boolean games, for others the complexity blows up dramatically. We also show that the concurrency in partial-order Boolean games can be modelled using a closure-operator semantics, and conclude by considering the relationship of our model to Independence-Friendly logic. (shrink)

The Annual Conference of the European Association for Computer Science Logic, CSL 2002, was held in the Old College of the University of Edinburgh on 22–25 September 2002. The conference series started as a programme of Int- national Workshops on Computer Science Logic, and then in its sixth meeting became the Annual Conference of the EACSL. This conference was the sixteenth meeting and eleventh EACSL conference; it was organized by the Laboratory for Foundations of Computer Science at the University of (...) Edinburgh. The CSL 2002 Programme Committee considered 111 submissions from 28 countries during a two week electronic discussion; each paper was refereed by at least three reviewers. The Committee selected 37 papers for presentation at the conference and publication in these proceedings. The Programme Committee invited lectures from Susumu Hayashi, Frank Neven, and Damian Niwinski; ́ the papers provided by the invited speakers appear at the front of this volume. In addition to the main conference, two tutorials – ‘Introduction to Mu- Calculi’ and ‘Parametrized Complexity’ – were given on the previous day. (shrink)