Weak Muller Conditions Make Delay Games Hard

Sarah Winter; Martin Zimmermann

doi:10.1142/9789811278631_0016

Weak Muller Conditions Make Delay Games Hard

Sarah Winter, Martin Zimmermann

Research output: Contribution to book/anthology/report/conference proceeding › Book chapter › Research › peer-review

1 Citation (Scopus)

31 Downloads (Pure)

Abstract

We show that solving delay games with winning conditions given by deterministic and non-deterministic weak Muller automata is 2EXPTIME-complete respectively 3EXPTIME-complete. Furthermore, doubly- and triply-exponential lookahead is necessary and sufficient to win such games. These results are the first that show that the succinctness of the automata types used to specify the winning conditions has an influence on the complexity of these problems.

Original language	English
Title of host publication	Lecture Notes Series, Institute for Mathematical Sciences
Editors	Noam Greenberg, Sanjay Jain, Yue Yang, Frank Stephan, Keng Meng Ng, Guohua Wu, Sven Schewe
Number of pages	40
Publisher	World Scientific Publishing Co.
Publication date	2024
Pages	425-464
DOIs	https://doi.org/10.1142/9789811278631_0016
Publication status	Published - 2024

Series	Lecture Notes Series, Institute for Mathematical Sciences
Volume	42
ISSN	1793-0758

Bibliographical note

Publisher Copyright:
© 2024 World Scientific Publishing Company.

Access to Document

10.1142/9789811278631_0016

weakmullerdelayAccepted author manuscript, 428 KB

AUB Link

Search for the material in Aalborg University Library's search engine

Cite this

Winter, Sarah ; Zimmermann, Martin. / Weak Muller Conditions Make Delay Games Hard. Lecture Notes Series, Institute for Mathematical Sciences. editor / Noam Greenberg ; Sanjay Jain ; Yue Yang ; Frank Stephan ; Keng Meng Ng ; Guohua Wu ; Sven Schewe. World Scientific Publishing Co., 2024. pp. 425-464 (Lecture Notes Series, Institute for Mathematical Sciences, Vol. 42).

@inbook{dcc045a0844f4de3a4c13a4f8ad22273,

title = "Weak Muller Conditions Make Delay Games Hard",

abstract = "We show that solving delay games with winning conditions given by deterministic and non-deterministic weak Muller automata is 2EXPTIME-complete respectively 3EXPTIME-complete. Furthermore, doubly- and triply-exponential lookahead is necessary and sufficient to win such games. These results are the first that show that the succinctness of the automata types used to specify the winning conditions has an influence on the complexity of these problems.",

author = "Sarah Winter and Martin Zimmermann",

note = "Publisher Copyright: {\textcopyright} 2024 World Scientific Publishing Company.",

year = "2024",

doi = "10.1142/9789811278631_0016",

language = "English",

series = "Lecture Notes Series, Institute for Mathematical Sciences",

publisher = "World Scientific Publishing Co.",

pages = "425--464",

editor = "Noam Greenberg and Sanjay Jain and Yue Yang and Frank Stephan and Ng, {Keng Meng} and Guohua Wu and Sven Schewe",

booktitle = "Lecture Notes Series, Institute for Mathematical Sciences",

}

Weak Muller Conditions Make Delay Games Hard. / Winter, Sarah; Zimmermann, Martin.
Lecture Notes Series, Institute for Mathematical Sciences. ed. / Noam Greenberg; Sanjay Jain; Yue Yang; Frank Stephan; Keng Meng Ng; Guohua Wu; Sven Schewe. World Scientific Publishing Co., 2024. p. 425-464 (Lecture Notes Series, Institute for Mathematical Sciences, Vol. 42).

Research output: Contribution to book/anthology/report/conference proceeding › Book chapter › Research › peer-review

TY - CHAP

T1 - Weak Muller Conditions Make Delay Games Hard

AU - Winter, Sarah

AU - Zimmermann, Martin

PY - 2024

Y1 - 2024

N2 - We show that solving delay games with winning conditions given by deterministic and non-deterministic weak Muller automata is 2EXPTIME-complete respectively 3EXPTIME-complete. Furthermore, doubly- and triply-exponential lookahead is necessary and sufficient to win such games. These results are the first that show that the succinctness of the automata types used to specify the winning conditions has an influence on the complexity of these problems.

AB - We show that solving delay games with winning conditions given by deterministic and non-deterministic weak Muller automata is 2EXPTIME-complete respectively 3EXPTIME-complete. Furthermore, doubly- and triply-exponential lookahead is necessary and sufficient to win such games. These results are the first that show that the succinctness of the automata types used to specify the winning conditions has an influence on the complexity of these problems.

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

U2 - 10.1142/9789811278631_0016

DO - 10.1142/9789811278631_0016

M3 - Book chapter

AN - SCOPUS:85179435737

T3 - Lecture Notes Series, Institute for Mathematical Sciences

SP - 425

EP - 464

BT - Lecture Notes Series, Institute for Mathematical Sciences

A2 - Greenberg, Noam

A2 - Jain, Sanjay

A2 - Yang, Yue

A2 - Stephan, Frank

A2 - Ng, Keng Meng

A2 - Wu, Guohua

A2 - Schewe, Sven

PB - World Scientific Publishing Co.

ER -

Weak Muller Conditions Make Delay Games Hard

Abstract

Bibliographical note

Access to Document

AUB Link

Other files and links

Fingerprint

Cite this