Computer Laboratory Home Page Search A-Z Directory Help
University of Cambridge Home Logic and Semantics Seminar
Thu 29th May, 2003: Stephan Kreutzer
Computer Laboratory > Research > TSG > Logic and Semantics Seminar > Thu 29th May, 2003: Stephan Kreutzer

Speaker: Stephan Kreutzer, University of Edinburgh
Title: Once upon a Time in the West:
Determinacy, Definability and Complexity of Path Games
Time: Thu 29th May, 2003, 15:00
Venue: William Gates Building, room FW11
Abstract:

We study games as they were played in the wild west. Two players set out for an infinite ride through the west. For reasons long forgotten, they were forced to stay together -- as long as both were alive. Often enough they had different ideas on where the ride should go. Therefore they agreed on the following rule: the players take turns, on alternate days, to determine where the ride should go that day. A player might well decide not to move at all (in particular if the last day's ride stopped at a saloon). However, only a finite distance could be covered each day. After omega days the ride is completed and it is time for payoff.

There are variants of this game where one of the players would fade away (these things happened in the west) and the other player was to complete the game by himself for the remaining omega days (a lonesome ride indeed).

Besides the wild west, path games like this also occur in other contexts, for instance in planning in non-deterministic domains. In this talk we will briefly consider some of such connections to the wild west. We will then focus on the determinacy of path games for various classes of winning conditions (the conditions which determine the payoff at the end of the ride) and study the complexity of deciding the winner of such games. Finally, we will consider the definability of these games in various logics like the mu-calculus, CTL*, FO, ...