Computer Science Logic and 8th Kurt Gödel Colloquium Parosh Aziz Abdulla, Ahmed Bouajjani, Julien d'Orso: Deciding Monotonic Games

Welcome and News Host Institutions Calls and Deadlines Program Social Program Registration Location and Venue Accommodation Committees Contact Colocated Events Authors' instructions

Print this page In an earlier work \cite{Parosh:Bengt:Karlis:Tsay:general:IC} we presented a general framework for verification of infinite-state transition systems, where the transition relation is monotonic with respect to a {\it well quasi-ordering} on the set of states. In this paper, we investigate extending the framework from the context of transition systems to that of {\it games}. We show that monotonic games are in general undecidable. We identify a subclass of monotonic games, called {\it downward closed} games. We provide algorithms for analyzing downward closed games subject to winning conditions which are formulated as safety properties. © 2002-2003 Kurt Gödel Society, Norbert Preining. 2003-06-04