Imperfect information in Reactive Modules games
- Submitting institution
-
University of Oxford
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 2026
- Type
- D - Journal article
- DOI
-
10.1016/j.ic.2018.02.023
- Title of journal
- Information and Computation
- Article number
- -
- First page
- 650
- Volume
- 261
- Issue
- 4
- ISSN
- 0890-5401
- Open access status
- Compliant
- Month of publication
- March
- Year of publication
- 2018
- 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
-
2
- Research group(s)
-
-
- Citation count
- 6
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This paper is the journal version of a KR 2016 paper, and presents a comprehensive study of games with imperfect information. It uses Reactive Modules Games to investigate rational verification under imperfect information. The paper formally defines the new framework. It shows that, in this setting, rational verification is undecidable via a complex reduction from uniform synthesis. However, in many restricted scenarios the problem is decidable, and can be solved in 2EXPTIME, EXPSPACE, NEXPTIME, or PSPACE, depending on the particular situation at hand.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -