Logic for INTeraction

Main Page

Project Outline

People

Documents

Events

Mailing List *

Links

News:

2-3 April 2011: Oxford LINT Workshop, Oxford, UK

8-12 August 2011: Workshop on Logical Constants at ESSLLI 2011, Ljbuljana, Slovenia

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.

Finances

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

Workshop dinner

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

Timetable

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.

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.

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.

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.

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.

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.

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.

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.

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.

|

maintained by: Pietro Galliani ()