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

Publikation: Bidrag til bog/antologi/rapport/konference proceeding › Bidrag til bog/antologi › Forskning › peer review

1 Citationer (Scopus)

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

Originalsprog	Engelsk
Titel	Lecture Notes Series, Institute for Mathematical Sciences
Redaktører	Noam Greenberg, Sanjay Jain, Yue Yang, Frank Stephan, Keng Meng Ng, Guohua Wu, Sven Schewe
Antal sider	40
Forlag	World Scientific Publishing Co.
Publikationsdato	2024
Sider	425-464
DOI	https://doi.org/10.1142/9789811278631_0016
Status	Udgivet - 2024

Navn	Lecture Notes Series, Institute for Mathematical Sciences
Vol/bind	42
ISSN	1793-0758

Bibliografisk note

Publisher Copyright:
© 2024 World Scientific Publishing Company.

Adgang til dokumentet

10.1142/9789811278631_0016

weakmullerdelayAccepteret manuskript, 428 KB

AUB Link

Søg efter materialet i Aalborg Universitetsbiblioteks søgemaskine

Andre filer og links

Link to publication in Scopus

Citationsformater

@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. red. / Noam Greenberg; Sanjay Jain; Yue Yang; Frank Stephan; Keng Meng Ng; Guohua Wu; Sven Schewe. World Scientific Publishing Co., 2024. s. 425-464 (Lecture Notes Series, Institute for Mathematical Sciences, Bind 42).

Publikation: Bidrag til bog/antologi/rapport/konference proceeding › Bidrag til bog/antologi › Forskning › 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

Bibliografisk note

Adgang til dokumentet

AUB Link

Andre filer og links

Fingeraftryk

Citationsformater