کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
439386 690545 2006 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Backtracking games and inflationary fixed points
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Backtracking games and inflationary fixed points
چکیده انگلیسی

We define a new class of games, called backtracking games. Backtracking games are essentially parity games with an additional rule allowing players, under certain conditions, to return to an earlier position in the play and revise a choice or to force a countback of the number of moves. This new feature makes backtracking games more powerful than parity games. As a consequence, winning strategies become more complex objects and computationally harder. The corresponding increase in expressiveness allows us to use backtracking games as model-checking games for inflationary fixed-point logics such as IFP or MIC. We identify a natural subclass of backtracking games, the simple games, and show that these are the “right” model-checking games for IFP by (a) giving a translation of formulae φ and structures A into simple games such that if, and only if, Player 0 wins the corresponding game and (b) showing that the winner of simple backtracking games can again be defined in IFP.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 350, Issues 2–3, 7 February 2006, Pages 174-187