Conference item
Strategy complexity of parity objectives in countable MDPs
- Abstract:
-
We study countably infinite MDPs with parity objectives. Unlike in finite MDPs, optimal strategies need not exist, and may require infinite memory if they do. We provide a complete picture of the exact strategy complexity of ε-optimal strategies (and optimal strategies, where they exist) for all subclasses of parity objectives in the Mostowski hierarchy. Either MD-strategies, Markov strategies, or 1-bit Markov strategies are necessary and sufficient, depending on the number of colors, the bra...
Expand abstract
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Authors
Funding
Bibliographic Details
- Publisher:
- Schloss Dagstuhl Publisher's website
- Journal:
- LIPIcs Journal website
- Volume:
- 171
- Pages:
- 1-17
- Publication date:
- 2020-08-28
- Acceptance date:
- 2020-06-29
- Event title:
- 31st International Conference on Concurrency Theory (CONCUR 2020)
- Event website:
- https://concur2020.forsyte.at/
- Event start date:
- 2020-09-01
- Event end date:
- 2020-09-04
- DOI:
- ISSN:
-
1868-8969
- ISBN:
- 9783959771603
Item Description
- Language:
- English
- Keywords:
- Pubs id:
-
1119181
- Local pid:
- pubs:1119181
- Deposit date:
- 2020-07-16
Terms of use
- Copyright holder:
- Kiefer et al.
- Copyright date:
- 2020
- Rights statement:
- © Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, and Patrick Totzke; licensed under Creative Commons License CC-BY.
- Notes:
- This paper was presented at the 31st International Conference on Concurrency Theory (CONCUR 2020), September 2020.
- Licence:
- CC Attribution (CC BY)
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record