On parity game preorders and the logic of matching plays

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

doi:10.1007/978-3-662-49192-8_23

On parity game preorders and the logic of matching plays

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 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	https://doi.org/10.1007/978-3-662-49192-8_23
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

Access to Document

10.1007/978-3-662-49192-8_23

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

@inproceedings{db577215fb1c4edcb2e5c15a5029a103,

title = "On parity game preorders and the logic of matching plays",

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.",

author = "M.W. Gazda and T.A.C. Willemse",

year = "2016",

doi = "10.1007/978-3-662-49192-8_23",

language = "English",

isbn = "9783662491911",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "277--289",

editor = "{Freivalds }, R.M. and G. Engels and B. Catania",

booktitle = "SOFSEM 2016: theory and practice of computer science",

address = "Germany",

note = "42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016), SOFSEM 2016 ; Conference date: 23-01-2016 Through 28-01-2016",

}

Gazda, MW & Willemse, TAC 2016, On parity game preorders and the logic of matching plays. in RM Freivalds , G Engels & B Catania (eds), SOFSEM 2016: theory and practice of computer science. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9587, Springer, pp. 277-289, 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016), Harrachov, Czech Republic, 23/01/16. https://doi.org/10.1007/978-3-662-49192-8_23

On parity game preorders and the logic of matching plays. / Gazda, M.W.; Willemse, T.A.C.

SOFSEM 2016: theory and practice of computer science. ed. / R.M. Freivalds ; G. Engels; B. Catania. Springer, 2016. p. 277-289 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9587).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - On parity game preorders and the logic of matching plays

AU - Gazda, M.W.

AU - Willemse, T.A.C.

N1 - Conference code: 42

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84956615747&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-49192-8_23

DO - 10.1007/978-3-662-49192-8_23

M3 - Conference contribution

AN - SCOPUS:84956615747

SN - 9783662491911

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 277

EP - 289

BT - SOFSEM 2016: theory and practice of computer science

A2 - Freivalds , R.M.

A2 - Engels, G.

A2 - Catania, B.

PB - Springer

T2 - 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016)

Y2 - 23 January 2016 through 28 January 2016

ER -

Gazda MW, Willemse TAC. On parity game preorders and the logic of matching plays. In Freivalds RM, Engels G, Catania B, editors, SOFSEM 2016: theory and practice of computer science. Springer. 2016. p. 277-289. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-662-49192-8_23

On parity game preorders and the logic of matching plays

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this