کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6873949 | 686072 | 2015 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The Rabin index of parity games: Its complexity and approximation
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The Rabin index of parity games: Its complexity and approximation The Rabin index of parity games: Its complexity and approximation](/preview/png/6873949.png)
چکیده انگلیسی
We study the descriptive complexity of parity games by taking into account the coloring of their game graphs whilst ignoring their ownership structure. Colorings of game graphs are identified if they determine the same winning regions and strategies, for all ownership structures of nodes. The Rabin index of a parity game is the minimum of the maximal color taken over all equivalent coloring functions. We show that deciding whether the Rabin index is at least k is in P for k=1 but NP-hard for all fixedkâ¥2. We present an EXPTIME algorithm that computes the Rabin index by simplifying its input coloring function. When replacing simple cycle with cycle detection in that algorithm, its output over-approximates the Rabin index in polynomial time. We evaluate this efficient algorithm as a preprocessor of solvers in detailed experiments: for Zielonka's solver on random and structured parity games and for our partial solver psolB on random games.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 245, December 2015, Pages 36-53
Journal: Information and Computation - Volume 245, December 2015, Pages 36-53
نویسندگان
Michael Huth, Jim Huan-Pu Kuo, Nir Piterman,