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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

3 Citaten (Scopus)

Samenvatting

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.

Originele taal-2	Engels
Titel	SOFSEM 2016: theory and practice of computer science
Redacteuren	R.M. Freivalds , G. Engels, B. Catania
Uitgeverij	Springer
Pagina's	277-289
Aantal pagina's	13
ISBN van elektronische versie	978-3-662-49192-8
ISBN van geprinte versie	9783662491911
DOI's	https://doi.org/10.1007/978-3-662-49192-8_23
Status	Gepubliceerd - 2016
Evenement	42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016) - Harrachov, Tsjechië Duur: 23 jan. 2016 → 28 jan. 2016 Congresnummer: 42

Publicatie series

Naam	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9587
ISSN van geprinte versie	03029743
ISSN van elektronische versie	16113349

Congres

Congres	42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016)
Verkorte titel	SOFSEM 2016
Land/Regio	Tsjechië
Stad	Harrachov
Periode	23/01/16 → 28/01/16

Toegang tot document

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

Andere bestanden en links

Link to publication in Scopus

Citeer dit

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 (editors), SOFSEM 2016: theory and practice of computer science (blz. 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 (redactie), 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, blz. 277-289, 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016), Harrachov, Tsjechië, 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. redactie / R.M. Freivalds ; G. Engels; B. Catania. Springer, 2016. blz. 277-289 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9587).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › 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, redacteurs, SOFSEM 2016: theory and practice of computer science. Springer. 2016. blz. 277-289. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-49192-8_23

On parity game preorders and the logic of matching plays

Samenvatting

Publicatie series

Congres

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit