Dumitriu, Andrei (2022) Linear algorithms for Parity Games with the Signature of a Potential. Bachelor's Thesis, Computing Science.
|
Text
bCS_2022_DumitriuA.pdf Download (410kB) | Preview |
|
![[img]](https://fse.studenttheses.ub.rug.nl/style/images/fileicons/text.png) |
Text
toestemming.pdf Restricted to Registered users only Download (121kB) |
Abstract
Solving parity games has been an important problem in Computer Science, not only because of the applications of this infinite duration game in satisfiability checking and model checking, but also because it is one of the few problems that is both in UP and in co-UP, but not also in P. We propose two new algorithms for solving parity games, based on the newest developments in regards to mean payoff games. The first will solve the parity game using its equivalent mean payoff game. The second one will have a similar structure to the mean payoff game solver, except the winning positions will be found directly in the parity game, with the use of a strategy improvement algorithm. Both algorithms will have linear time complexity for a certain type of games, known as games with the "signature of a potential".
| Item Type: | Thesis (Bachelor's Thesis) |
|---|---|
| Supervisor name: | Lorscheid, O. and Perez Parra, J.A. |
| Degree programme: | Computing Science |
| Thesis type: | Bachelor's Thesis |
| Language: | English |
| Date Deposited: | 06 Sep 2022 12:17 |
| Last Modified: | 06 Sep 2022 12:17 |
| URI: | https://fse.studenttheses.ub.rug.nl/id/eprint/28619 |
Actions (login required)
 |
View Item |