University of Twente Student Theses
Finding Smaller Parity Game Solutions by Identifying and Solving Subgames using Oink
Dijkstra, Stijn (2024) Finding Smaller Parity Game Solutions by Identifying and Solving Subgames using Oink.
|
PDF
435kB |
| Abstract: | Solving parity games is an important step in some reactive synthesis tools. Reactive synthesis is the process of synthesising a controller that implements a formal definition. Finding smaller solutions to parity games can lead to smaller controller designs. Decreasing the size of controllers improves their efficiency. We propose an algorithm that identifies subgames of parity games to find smaller solutions. We implement subgame identification by building on the tool Oink and discover how it benefits performance. We compare multiple approaches to the problem and we show that pruning algorithms are a more viable approach to finding subgames than growing algorithms. We also compare the quality-based performance of various solvers to get a better understanding of the tool Oink. |
| Item Type: | Essay (Bachelor) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 31 mathematics, 54 computer science |
| Programme: | Computer Science BSc (56964) |
| Link to this item: | https://purl.utwente.nl/essays/98288 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page