---
_id: '5400'
abstract:
- lang: eng
  text: We consider partially observable Markov decision processes (POMDPs) with ω-regular
    conditions specified as parity objectives. The class of ω-regular languages extends
    regular languages to infinite strings and provides a robust specification language
    to express all properties used in verification, and parity objectives are canonical
    forms to express ω-regular conditions. The qualitative analysis problem given
    a POMDP and a parity objective asks whether there is a strategy to ensure that
    the objective is satis- fied with probability 1 (resp. positive probability).
    While the qualitative analysis problems are known to be undecidable even for very
    special cases of parity objectives, we establish decidability (with optimal complexity)
    of the qualitative analysis problems for POMDPs with all parity objectives under
    finite- memory strategies. We establish asymptotically optimal (exponential) memory
    bounds and EXPTIME- completeness of the qualitative analysis problems under finite-memory
    strategies for POMDPs with parity objectives.
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Martin
  full_name: Chmelik, Martin
  id: 3624234E-F248-11E8-B48F-1D18A9856A87
  last_name: Chmelik
- first_name: Mathieu
  full_name: Tracol, Mathieu
  id: 3F54FA38-F248-11E8-B48F-1D18A9856A87
  last_name: Tracol
citation:
  ama: Chatterjee K, Chmelik M, Tracol M. <i>What Is Decidable about Partially Observable
    Markov Decision Processes with ω-Regular Objectives</i>. IST Austria; 2013. doi:<a
    href="https://doi.org/10.15479/AT:IST-2013-109-v1-1">10.15479/AT:IST-2013-109-v1-1</a>
  apa: Chatterjee, K., Chmelik, M., &#38; Tracol, M. (2013). <i>What is decidable
    about partially observable Markov decision processes with ω-regular objectives</i>.
    IST Austria. <a href="https://doi.org/10.15479/AT:IST-2013-109-v1-1">https://doi.org/10.15479/AT:IST-2013-109-v1-1</a>
  chicago: Chatterjee, Krishnendu, Martin Chmelik, and Mathieu Tracol. <i>What Is
    Decidable about Partially Observable Markov Decision Processes with ω-Regular
    Objectives</i>. IST Austria, 2013. <a href="https://doi.org/10.15479/AT:IST-2013-109-v1-1">https://doi.org/10.15479/AT:IST-2013-109-v1-1</a>.
  ieee: K. Chatterjee, M. Chmelik, and M. Tracol, <i>What is decidable about partially
    observable Markov decision processes with ω-regular objectives</i>. IST Austria,
    2013.
  ista: Chatterjee K, Chmelik M, Tracol M. 2013. What is decidable about partially
    observable Markov decision processes with ω-regular objectives, IST Austria, 41p.
  mla: Chatterjee, Krishnendu, et al. <i>What Is Decidable about Partially Observable
    Markov Decision Processes with ω-Regular Objectives</i>. IST Austria, 2013, doi:<a
    href="https://doi.org/10.15479/AT:IST-2013-109-v1-1">10.15479/AT:IST-2013-109-v1-1</a>.
  short: K. Chatterjee, M. Chmelik, M. Tracol, What Is Decidable about Partially Observable
    Markov Decision Processes with ω-Regular Objectives, IST Austria, 2013.
date_created: 2018-12-12T11:39:07Z
date_published: 2013-02-20T00:00:00Z
date_updated: 2025-09-18T11:38:38Z
day: '20'
ddc:
- '000'
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2013-109-v1-1
file:
- access_level: open_access
  checksum: cbba40210788a1b22c6cf06433b5ed6f
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T11:53:06Z
  date_updated: 2020-07-14T12:46:44Z
  file_id: '5467'
  file_name: IST-2013-109-v1+1_What_is_Decidable_about_Partially_Observable_Markov_Decision_Processes_with_ω-Regular_Objectives.pdf
  file_size: 483407
  relation: main_file
file_date_updated: 2020-07-14T12:46:44Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '41'
publication_identifier:
  issn:
  - 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '109'
related_material:
  record:
  - id: '2295'
    relation: later_version
    status: public
  - id: '1477'
    relation: later_version
    status: public
status: public
title: What is decidable about partially observable Markov decision processes with
  ω-regular objectives
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...