On parity game preorders and the logic of matching plays

M.W. Gazda, T.A.C. Willemse

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)

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 languageEnglish
Title of host publicationSOFSEM 2016: theory and practice of computer science
EditorsR.M. Freivalds , G. Engels, B. Catania
PublisherSpringer
Pages277-289
Number of pages13
ISBN (Electronic)978-3-662-49192-8
ISBN (Print)9783662491911
DOIs
Publication statusPublished - 2016
Event42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016) - Harrachov, Czech Republic
Duration: 23 Jan 201628 Jan 2016
Conference number: 42

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9587
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016)
Abbreviated titleSOFSEM 2016
CountryCzech Republic
CityHarrachov
Period23/01/1628/01/16

Fingerprint Dive into the research topics of 'On parity game preorders and the logic of matching plays'. Together they form a unique fingerprint.

  • Cite this

    Gazda, M. W., & Willemse, T. A. C. (2016). On parity game preorders and the logic of matching plays. In R. M. Freivalds , G. Engels, & B. Catania (Eds.), SOFSEM 2016: theory and practice of computer science (pp. 277-289). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9587). Springer. https://doi.org/10.1007/978-3-662-49192-8_23