Winning strategies for infinite games: from large cardinals to computer science extended abstract

摘要

(1) Set Theory's topic of Large Cardinals is the most infinitary part of Mathematics. At the other end, the study of Finite State machines is the very first chapter of Computer Science. Can we combine these two opposite extremes fruitfully and use ideas coming from large cardinals to produce results about finite state machines?(2) Using the large cardinal axiom of "sharps" Martin proved analytic determinacy: the existence of a winning strategy for one of the players in every infinite game of perfect information between two players, provided the winning set of one of the players happens to be an analytic one. I modify and complement his proof so as to obtain a new proof of the Rabin, Buechi-Landweber, Gurevich-Harrington theorem of finite state determinacy: existence of a winning strategy computed by a finite state machine, when the player's winning sets are themselves finite state accepted. This 4th proof of finite state determinacy is again a totally new one-as must be the case since it still makes use of the large cardinal axiom, to prove such an effective result!(3) Thus to our question (1) the new proof answers with a clear and surprising yes ... of modest bearing, since it only concerns an old result. But we shall explain why the new proof is more suggestive and useful than former ones, in order to address today's two main unsolved problems connecting effective determinacy with Computer Science: the P-time realization of finite state strategies, and the P-time decision of the winner of a parity game. Indeed: adding to our proof an effective elimination of the very restricted part of the axiom of sharps that it really uses, may lead to useful new results, ideas and methods around these two hard, crucial problems. (Of course our use of sharps is eliminated in advance in 3 ways: namely the 3 former proofs of Rabin, of Buechi-Landweber and of Gurevich-Harrington. But the new proof seems to be more suggestive than the old ones when feasibility questions are at stake....) (C) 2004 Published by Elsevier B.V.