Parameterized Algorithms for Parity Games
作者： Jakub Gajarský , Michael Lampis , Kazuhisa Makino , Valia Mitsou , Sebastian Ordyniak
DOI: 10.1007/978-3-662-48054-0_28
关键词: Parameterized algorithms 、 Parity (mathematics) 、 Computational complexity theory 、 Model checking 、 Treewidth 、 Dynamic programming 、 Theoretical computer science 、 Mathematics 、 Parity game 、 Parameterized complexity
摘要: Determining the winner of a Parity Game is a major problem in computational complexity with a number of applications in verification. In a parameterized complexity setting, the …
dauphine.fr
springer.com
hal.science 参考文章(28)
Fedor V. Fomin, Mathieu Liedloff, Pedro Montealegre, Ioan Todinca, Algorithms Parameterized by Vertex Cover and Modular Width, through Potential Maximal Cliques scandinavian workshop on algorithm theory. pp. 182- 193 ,(2014) , 10.1007/978-3-319-08404-6_16
Sven Sandberg, Sergei Vorobyov, Henrik Björklund, On Fixed-Parameter Complexity of Infinite Games Uppsala: Department of Information Technology, Uppsala University. ,(2003)
Marcin Jurdziński, Small Progress Measures for Solving Parity Games symposium on theoretical aspects of computer science. pp. 290- 301 ,(2000) , 10.1007/3-540-46541-3_24
Ralf Küsters, Memoryless determinacy of parity games Automata logics, and infinite games. pp. 95- 106 ,(2002) , 10.1007/3-540-36387-4_6
Sven Schewe, Solving Parity Games in Big Steps FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science. pp. 449- 460 ,(2007) , 10.1007/978-3-540-77050-3_37
Anne Condon, The complexity of stochastic games Information & Computation. ,vol. 96, pp. 203- 224 ,(1992) , 10.1016/0890-5401(92)90048-K
Robert McNaughton, Infinite games played on finite graphs Annals of Pure and Applied Logic. ,vol. 65, pp. 149- 184 ,(1993) , 10.1016/0168-0072(93)90036-D
E.Allen Emerson, Charanjit S. Jutla, A.Prasad Sistla, On model checking for the m-calculus and its fragments Theoretical Computer Science. ,vol. 258, pp. 491- 522 ,(2001) , 10.1016/S0304-3975(00)00034-7
A. Browne, E.M. Clarke, S. Jha, D.E. Long, W. Marrero, An improved algorithm for the evaluation of fixpoint expressions Theoretical Computer Science. ,vol. 178, pp. 237- 255 ,(1997) , 10.1016/S0304-3975(96)00228-9
Dietmar Berwanger, Erich Grädel, Łukasz Kaiser, Roman Rabinovich, Entanglement and the complexity of directed graphs Theoretical Computer Science. ,vol. 463, pp. 2- 25 ,(2012) , 10.1016/J.TCS.2012.07.010