How Much Lookahead is Needed to Win Infinite Games?
- Submitting institution
-
The University of Liverpool
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 12141
- Type
- D - Journal article
- DOI
-
10.2168/LMCS-12(3:4)2016
- Title of journal
- Logical Methods in Computer Science
- Article number
- 4
- First page
- 2017
- Volume
- 12
- Issue
- 3
- ISSN
- 1860-5974
- Open access status
- Compliant
- Month of publication
- April
- Year of publication
- 2017
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
1
- Research group(s)
-
-
- Citation count
- 3
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- A preliminary version of this paper was published at ICALP 2015. The paper settles the complexity of omega-regular delay games and gives tight bounds on the lookahead. Both problems were open since the introduction of delay games by Hosch and Landweber in 1972. The lower bounds were applied by Clemente and Mayr to the size reduction problem for nondeterministic automata (LMCS 2019) and by Filiot et al. to the determinisation of weighted automata (LICS 2017).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -