In this paper we provide a broad investigation of the symbolic approach for solving Parity Games. Specifically, we implement in a fresh tool, called, four symbolic algorithms to solve Parity Games and compare their performances to the corresponding explicit versions for different classes of games. By means of benchmarks, we show that for random games, even for constrained random games, explicit algorithms actually perform better than symbolic algorithms. The situation changes, however, for structured games, where symbolic algorithms seem to have the advantage. This suggests that when evaluating algorithms for parity-game solving, it would be useful to have real benchmarks and not only random benchmarks, as the common practice has been.
Solving parity games: Explicit vs symbolic / Di Stasio, A.; Murano, A.; Vardi, M. Y.. - 10977:(2018), pp. 159-172. (Intervento presentato al convegno 23rd International Conference on Implementation and Application of Automata, CIAA 2018 tenutosi a Charlottetown; Canada) [10.1007/978-3-319-94812-6_14].
Solving parity games: Explicit vs symbolic
Di Stasio A.
;
2018
Abstract
In this paper we provide a broad investigation of the symbolic approach for solving Parity Games. Specifically, we implement in a fresh tool, called, four symbolic algorithms to solve Parity Games and compare their performances to the corresponding explicit versions for different classes of games. By means of benchmarks, we show that for random games, even for constrained random games, explicit algorithms actually perform better than symbolic algorithms. The situation changes, however, for structured games, where symbolic algorithms seem to have the advantage. This suggests that when evaluating algorithms for parity-game solving, it would be useful to have real benchmarks and not only random benchmarks, as the common practice has been.File | Dimensione | Formato | |
---|---|---|---|
DiStasio_Postprint_Solving_2018.pdf
accesso aperto
Note: https://link.springer.com/chapter/10.1007/978-3-319-94812-6_14
Tipologia:
Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
412.08 kB
Formato
Adobe PDF
|
412.08 kB | Adobe PDF | |
DiStasio_Solving_2018.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
366.02 kB
Formato
Adobe PDF
|
366.02 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.