Complexity in Infinite Games of Graphs and Temporal Constraint Networks

Place: Seminar Room "-1"-  Department of Mathematics - Via Sommarive 14 - Povo - Trento
at 9.00 a.m.

• Carlo Comin - PhD in mathematics

Abstract:
This dissertation deals with a number of algorithmic problems motivated by automated temporal planning and formal verfication of reactive and finite state systems.

Algorithmic Game Theory (especially, that concerning infinite two-player pebble-games played on finite graphs [Automata, Logics, and Infinite Games, Gradel-Thomas-Wilke, 2002]) is the red thread that makes it possible to look at the various contributions of our work in a suffciently coherent way.

Particularly, we shall focus on game theoretical methods in order to obtain improved computational complexity upper bounds and faster algorithms for the following models: Hyper Temporal Networks (HyTNs), a strict generalization of Simple Temporal Networks (STNs) [Dechter-Meiri-Pearl, 1991] introduced to overcome the limitation of considering only conjunctions of constraints but maintaining a practical effciency in the consistency check of the instances; Conditional Simple Temporal Networks (CSTNs) and Dynamic Consistency Checking (DC-Checking) [Tsamardinos-Vidal-Pollack, 2003], which is a constraint-based graph-formalism for conditional temporal planning; CSTNs and DC-Checking with an Instantaneous Reaction-Time, in which the planner can react to any observation at the same instant of time in which the observation is made; Update Games (UGs) [Dinneen-Khoussainov, 1999] and Explicity Mc-Naughton Muller Games [Horn, 2008], and finally, Mean-Payoff Games [Ehrenfeucht-Mycielski, 1979 and Zwick-Paterson, 1996]. In this defence seminar we shall retrace the motivations, models, and main theorems proved in the thesis, offering a summary of the main results and the employed techniques.

Supervisor: Romeo Rizzi