The GLLC
workshop series provides an informal platform for researchers with an interest
in logic and its applications in, amongst others, game theory, linguistics and
computer science. GLLC 14 aims to emphasize the interface of computability
theory, quantifier theory, and game theory. Everybody is cordially invited to
participate; attendance is free.
| Date: | Tuesday October 3rd, 2006 |
| Place: | Amsterdam, Roetersstraat 11, E020 |
| Nearest metro stop is Weesperplein (five minutes by foot) | |
| Organizer: | Merlijn Sevenster |
| sevenstr at science.uva.nl, +31.20.525.6508 |
| 10:00 - 10:40 | Marcin Mostowski | |
| 10:40 - 11:20 | Bryan Renne | |
| 11:20 - 11:40 | coffee | |
| 11:40 - 12:20 | Jos Uiterwijk | |
| 12:20 - 13:00 | Peter van Emde Boas | |
| 13:00 - 14:20 | lunch | |
| 14:20 - 15:00 | Robert van Rooij | |
| 15:00 - 15:40 | Gabriel Sandu | |
| 15:40 - 16:00 | tea | |
| 16:00 - 16:40 | Tero Tulenheimo | |
| 16:40 - 17:20 | Erich Grädel |
| Title: | Kuhhandel |
| Abstract: | Kuhhandel (Koehandel in Dutch, You Are Bluffing in
English) is a card game invented by R¨¹diger Koltze around 1985. It is
similar to Happy families (Kwartetten) in the sense that groups of
four equal cards showing farm animals have to be collected by the players;
however, cards are being introduced by Auctioning and cards are exchanged
by so-called Cow-trades. Other complications are that the ten groups of
animal cards have unequal game value (in between 10 and 1000), that the
game score also depends on the number of groups collected and that the
money which is an essential ingredient during the game becomes worthless
when the game terminates. The game was suggested as a potential model for research in the InIGMA project grace to the fact that it involves a small amount of imperfect information: at every stage of the game all players have full knowledge about the distribution of the animal cards, but the distribution of the money cards is hidden. Progress in the InIGMA project however went in a different direction, leaving the game open for a recent project for my BA student Gijs Pannebakker (AI), who made some initial steps towards analysing the game. The results reported on are the joint work of Gijs Pannebakker, Merlijn Sevenster and myself. |
| Title: | Path Games: Determinacy, Definability, and Complexity |
| Abstract: | Once upon a time, two players set out on an infinite ride through the
west. More often than not, they had quite different ideas on where to go,
but for reasons that have by now been forgotten they were forced to stay
together -- as long as they were both alive. They agreed on the rule that
each player can determine on every second day, where the ride should go.
After omega days, an infinite ride is completed and it is time for payoff.
There were variants of this game where, after some number of days, one of
the players would be eliminated (these things happened in the west) and
the other was to complete the game by himself for the remaining omega days
(a very lonesome ride, indeed). Path games are two-player games on finite or infinite graphs, where the players, in each move, take a token not just along an edge (as in the common form of graph games), but along a path of any finite length. They arise also in other contexts than the west. They have been studied in descriptive set theory, in the form of Banach-Mazur games. An important issue in this context is determinacy (does one of the players have a winning strategy?) and its dependency on the topological properties of the winning condition. In a quite different setting, path games have been used for task planning in nondeterministic domains. Rather than determinacy (which is obvious for winning conditions in such applications), the main concern there are algorithmic questions. It turns out that planning problems modeled by path games can be solved by automata-based methods. Here we survey path games in a general, abstract setting, but with emphasis on definability and complexity issues. After a brief review on Banach-Mazur games, we discuss path games that are positionally determined, i.e., admit winning strategies that only depend on the current position, not on the history of the play. This can be used to determine the complexity of deciding the winner of path games with LTL winning conditions. Finally we discuss definability issues. We are interested in the question how the logical complexity of defining the winning condition (a property of infinite paths) is related to the logical complexity of defining who wins the associated game (a property of game graphs). In particular, it turns out that the winner of path games with LTL winning conditions is definable in CTL*. |
| Title: | Approximating of second order logic by some of its sublogics |
| Abstract: | The talk will give a survey of results and methods of approximating second order logic by its sublogics. Among logics considered there will be: the logic with Henkin quantifiers, its extension by duality operator, and some modal logics, namely Carnap's logic and some of its extensions. Two aspects of the logics will be taken into account: (1) recursive complexity of the sets of tautologies, and (2) semantical power. |
| Title: | Propositional Games with Explicit Strategies |
| Abstract: | I will discuss a game-theoretic semantics for the LP, Artemov's Logic of Proofs. |
| Title: | Towards a uniform game-theoretical account of conversational implicatures |
| Abstract: | Grice's notion of conversational implicatures plays an important role in linguistic pragmatics. In this talk I will propose a uniform game-theoretical approach of a wide range of implicatures. What is implicated by a sentence follows not from the assumption that speaker's obey the Gricean maxims of conversation, but that they make an Optimal assertion. Game theory is used to determine what is optimal. (This talk is based on joint work with Anton Benz, see also [draft].) |
| Title: | Truth in IF |
| Abstract: | T.b.a. |
| Title: | Games in logic: servant or master? |
| Abstract: | Game-theoretical conceptualizations are indisputably of vital interest for logical theorizing. But what happens if games are given a prescriptive role in logic? I will argue that conceptually, games should rather be seen as an ancilla logicae. I will back up my claims by examples from modal logic. |
| Title: | The Art of Solving Games |
| Abstract: | In this talk an overview will be given of techniques and results for solving games of perfect information during the last decades. Based on the complexities of games, it is shown which techniques are most promising for this purpose. The list of games solved so far, either with knowledge-based or brute-force methods, is ever-growing. Finally, an outlook to solve more games in the near future will be given. |
