Abstract
Parity games can be used to solve satisfiability, verification and controller synthesis problems. As part of an effort to better understand their nature, or the nature of the problems they solve, preorders on parity games have been studied. Defining these relations, and in particular proving their transitivity, has proven quite difficult on occasion. We propose a uniform way of lifting certain preorders on Kripke structures to parity games and study the resulting preorders. We explore their relation with parity game preorders from the literature and we study new relations. Finally, we investigate whether these preorders can also be obtained via modal characterisations of the preorders.
Original language | English |
---|---|
Title of host publication | SOFSEM 2016: theory and practice of computer science |
Editors | R.M. Freivalds , G. Engels, B. Catania |
Publisher | Springer |
Pages | 277-289 |
Number of pages | 13 |
ISBN (Electronic) | 978-3-662-49192-8 |
ISBN (Print) | 9783662491911 |
DOIs | |
Publication status | Published - 2016 |
Event | 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016) - Harrachov, Czech Republic Duration: 23 Jan 2016 → 28 Jan 2016 Conference number: 42 |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 9587 |
ISSN (Print) | 03029743 |
ISSN (Electronic) | 16113349 |
Conference
Conference | 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016) |
---|---|
Abbreviated title | SOFSEM 2016 |
Country/Territory | Czech Republic |
City | Harrachov |
Period | 23/01/16 → 28/01/16 |