TY - GEN
T1 - Solving parity games on the GPU
AU - Hoffmann, Philipp
AU - Luttenberger, Michael
N1 - Funding Information:
This work was partially founded by the DFG project “Polynomial Systems on Semirings: Foundations, Algorithms, Applications” and by the DFG Graduiertenkolleg 1480 (PUMA).
PY - 2013
Y1 - 2013
N2 - We present our GPU-based implementations of three well-known algorithms for solving parity games. Our implementations are in general faster by a factor of at least two than the corresponding implementations found in the widely known PGSolver collection of solvers. For benchmarking we use several of PGSolver 's benchmarks as well as arenas obtained by means of the reduction of the language inclusion problem of nondeterministic Büchi automata to parity games with only three colors [3]. The benchmark suite of http://languageinclusion.org/ CONCUR2011 was used in the latter case.
AB - We present our GPU-based implementations of three well-known algorithms for solving parity games. Our implementations are in general faster by a factor of at least two than the corresponding implementations found in the widely known PGSolver collection of solvers. For benchmarking we use several of PGSolver 's benchmarks as well as arenas obtained by means of the reduction of the language inclusion problem of nondeterministic Büchi automata to parity games with only three colors [3]. The benchmark suite of http://languageinclusion.org/ CONCUR2011 was used in the latter case.
UR - http://www.scopus.com/inward/record.url?scp=84887439124&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-02444-8_34
DO - 10.1007/978-3-319-02444-8_34
M3 - Conference contribution
AN - SCOPUS:84887439124
SN - 9783319024431
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 455
EP - 459
BT - Automated Technology for Verification and Analysis - 11th International Symposium, ATVA 2013, Proceedings
T2 - 11th International Symposium on Automated Technology for Verification and Analysis, ATVA 2013
Y2 - 15 October 2013 through 18 October 2013
ER -