Summary | Finances | Dinner | Timetable

Opening (van Benthem) |
Tutorial (Abramsky) | Tutorial (Berwanger) | Tutorial (Bonnay) | Tutorial (Väänänen)

Talk(Engström) | Talk (Galliani) | Talk (Kontinen) | Talk (Mann) | Talk (Puchala) | Talk (Tzevelekos)

## Summary

As part of the program of the ESF Eurocores LogICCC program "Logic for Interaction - LINT", a workshop is organized at ILLC in Amsterdam December 4-6, 2008.

The program starts December 4 after lunch and ends December 6 lunch time. The workshop will have four tutorials. They will be given by Samson Abramsky on Game Semantics, Dietmar Berwanger on Imperfect Information Games, Denis Bonnay on Logic Constants and Jouko Väänänen on Dependence Logic.

In addition there will be presentations by Fredrik Engström, Pietro Galliani, Juha Kontinen, Allen Mann, Bernd Puchala, and Nikos Tzevelekos. An Opening Talk on Logic for Interaction will be given by Johan van Benthem.

The organizer of the workshop is Jouko Väänänen, with the help of Pietro Galliani. Lecture halls are Thursday P015A, Friday P018, and Saturday P327.

For details, see this document.

Return to top## Finances

Every participant is assumed to pay their travel and hotel expenses from their own LINT ESF-grant.

Return to top## Workshop dinner

Interested should inform Pietro Galliani () for reservation purposes. The participants pay for their dinner although we are investigating possibilities for getting support.

Return to top## Timetable

Thursday Dec 4 | Friday Dec 5 | Saturday Dec 6 |
---|---|---|

Starts 9:00 ILLC P018 | Starts 9:00 P327 | |

Tutorial (Abramsky) 9:00-10:00 | Talk (Engström) 9:00-9:30 | |

Discussion 10:00-10:15 | Discussion 9:30-9:45 | |

Talk (Tzevelekos) 10:15-11:00 | Talk (Mann) 9:45-10:30 | |

Discussion 11:00-11.15 | Discussion 10:30-10:45 | |

Talk (Kontinen, Juha) 11:15-12:00 | Brainstorming 10:45-11:15 | |

Discussion 12:00-12:15 | COFFEE BREAK 11:15-11:45 | |

Starts 13:00 ILLC P015A | LUNCH | LINT Business meeting 11:45-13:00 |

Registration 13:00-14:00 | Tutorial (Berwanger) 14:00-15:00 | Workshop ends 13:00 |

Opening (van Benthem) 14:00-15:00 | Discussion 15:00-15:15 | |

Discussion 15:00-15:15 | Talk (Puchala) 15:15-15:45 | |

Tutorial (Väänänen) 15:15-16:15 | Discussion 15:45-16:00 | |

Discussion 16:15-16:30 | COFFEE BREAK 16:00-16:30 | |

COFFEE BREAK 16:30-17:00 | Tutorial (Bonnay) 16:30-17:30 | |

Talk (Galliani) 17:00-17:45 | Discussion 17:30-17:45 | |

Discussion 17:45-18:00 | WORKSHOP DINNER 18:00 |

## Logic Meets Games, A Wide-Angle Panorama (Johan van Benthem)

This talk is an overview for the logic and games aspect of the LogiCCC Program,
of which the LINT project pursues several important lines. I will give a map of
encounters, running from games and game theory to logic ('logic games'), and
also in the opposite direction ('game logics'). Then I show how this produces
new research questions for a coalition of computational and philosophical
logic, perhaps an unusual combination. And all that in 60 minutes.

References: (a) J. van Benthem, 2008, "Logical Dynamics of Information Flow",
book draft ILLC Amsterdam, especially Chapters 9, 11. (b) J. van Benthem,
1999 - 2003, 'Logic in Games', lecture notes, ILLC and Stanford,
new draft book version ready by the end of 2008.

## Game Semantics (Samson Abramsky)

The slides for the tutorial can be downloaded here.

Return to top## Imperfect-Information Games in Computing (Dietmar Berwanger)

We begin with a historical account of imperfect-information models established in differend fields of computing science, notably the theory of computation, supervisory control theory, and automated verification. The main questions about these models typically revolve around the notion of a minimax strategy. We survey basic procedures for handling models with two players and present a general undecidability result for setttings with three players. Then, we discuss current challenges and prospective approaches in the area.

The slides for the talk can be downloaded here.

Return to top## Logical Constants - Invariance for Modal Logic and Dynamic Logic (Denis Bonnay)

To begin with, I will present the Gothenburg project regarding the logical foundations of interaction. As a case in point, I will then expose some recent joint work with J. van Benthem on the invariance analysis of logical operations in modal and dynamic logic.

I shall first introduce some general methods to study the relationships between the logical vocabulary of a logical system and associated equivalence relations on structures. These general methods will be applied to shed some new light on invariance under bisimulation and safety as standard properties of logical operations in modal and dynamic logic.

The slides for the tutorial can be downloaded here.

Return to top## Dependence logic (Jouko Väänänen)

Games provide a possible and indeed quite good model of interaction. Underlying the concept of game is the more fundamental concept of dependence, namely we can think of a strategy as a special case of the dependence of moves on other moves in a game. Mixed strategies can be construed, respectively, as probabilistic dependences (see the talk by Pietro Galliani in this workshop). But dependence is actually a more common phenomenon: astronomy, ecological systems, health issues, inheritance, human history, stock markets. It is perhaps a matter of opinion whether these are all examples of games. Independently of the answer, we can ask, what is the logic of dependence? In this tutorial I set the stage for a systematic logical study of this important concept. The new logic, called dependence logic, simply adds the concept of dependence to first order logic. I will give the syntax and semantics of dependence logic and give it an alternative game theoretic semantics. The semantics is given in terms of sets of assignments. We call such sets teams. The strong connection to games is that the canonical example of a team is a set of parallel plays of the same game. Such parallelism provides also a convenient definition of imperfectness of information in a game. Not perhaps surprisingly, a particularly nice approach to dependence is provided by a combination of Heyting's intuitionistic logic and Girard's linear logic. Such a combination is already known from the so called logic of bunched implications (Pym).

Literature: Väänänen, J.: Dependence Logic, Cambridge University Press, 2007.

## Is dependence logical? (Fredrik Engström)

Several explications of the vague notion of a logical constant has been proposed. Many of these explications use generalized quantifiers (as defined by Lindström) and first-order model theory. I will give some very preliminary thoughts about applying these techniques to the setting of dependence logic.

Return to top## Probabilistic Dependence Logic (Pietro Galliani)

Given a finite model *M*, it is possible to associate to every sentence *φ*
of Backslash Logic and Dependence Logic the value of the corresponding
imperfect information game *H(φ)*, that is, the best average payoff that the Verifier can guarantee when both players are allowed to play random moves.
Hodges' compositional semantics can then be adapted to this new logic, and the value of atomic dependence formulas in the
resulting framework is seen to correspond to one of Kivinen
and Mannila's measures of approximate functional dependency.

The slides for the talk can be downloaded here.

Return to top## Definability in dependence logic (Juha Kontinen)

We study the expressive power of open formulas of Dependence Logic. In particular, we answer a question raised by Wilfrid Hodges: how to characterize the sets of teams definable by means of identity only in dependence logic, or equivalently in independence friendly logic. Finally, we discuss the analogous question in the context of Team Logic, which is the extension of dependence logic obtained by adding classical negation.

The slides for the talk can be downloaded here.

Return to top## Algebraic Independence-Friendly Logic (Allen Mann)

We will present an algebraization of independence-friendly logic. We use algebraic methods to show that the propositional logic underlying IF logic is Kleene's strong three-valued logic. We will also characterize which IF-formulas are equivalent to first-order formulas. Finally, we will show that "iff" is not expressible in IF logic.

The slides for the talk can be downloaded here.

Return to top## Winning Strategies in Two-Player Games with Partial Information (Bernd Puchala)

In this talk, we address the problem of deciding the existence of winning strategies and of synthesizing corresponding finite memory strategies in two-player games with partial information. We generalize the usual construction for observation based winning conditions to arbitrary winning conditions and moreover we solve this problem for a modified asynchronous framework. We also outline extensions of this framework by means of logical formulas and automata as well as several other logical questions concerning games with partial information. Finally, we present lower bounds for the memory which is needed to implement winning strategies in games with partial information and we clarify the connection between games with partial information and alternating tree automata.

The slides for the tutorial can be downloaded here.

Return to top## Nominal Techniques: from Nominal Logic to Nominal Games (Nikos Tzevelekos)

The line of research on Nominal Techniques, which commenced by Gabbay and Pitts in the late 90's and focuses on the formal treatment of names and name-binding, has proved remarkably prolific over the last decade and has spread over several fields within Theoretical Computer Science. In this talk we start from the originators' motivations and taking our way through Nominal Sets we arrive to their recent application to the semantics of programming languages.

Return to top