---
res:
  bibo_abstract:
  - 'Partially observable Markov decision processes (POMDPs) are a central model for
    uncertainty in sequential decision making. The most basic objective is the reachability
    objective, where a target set must be eventually visited, and the more general
    parity objectives can model all omega-regular specifications. For such objectives,
    the computational analysis problems are the following: (a) qualitative analysis
    that asks whether the objective can be satisfied with probability 1 (almost-sure
    winning) or probability arbitrarily close to 1 (limit-sure winning); and (b) quantitative
    analysis that asks for the approximation of the optimal probability of satisfying
    the objective. For general POMDPs, almost-sure analysis for reachability objectives
    is EXPTIME-complete, but limit-sure and quantitative analyses for reachability
    objectives are undecidable; almost-sure, limit-sure, and quantitative analyses
    for parity objectives are all undecidable. A special class of POMDPs, called revealing
    POMDPs, has been studied recently in several works, and for this subclass the
    almost-sure analysis for parity objectives was shown to be EXPTIME-complete. In
    this work, we show that for revealing POMDPs the limit-sure analysis for parity
    objectives is EXPTIME-complete, and even the quantitative analysis for parity
    objectives can be achieved in EXPTIME.@eng'
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Ali
      foaf_name: Asadi, Ali
      foaf_surname: Asadi
      foaf_workInfoHomepage: http://www.librecat.org/personId=02d96aae-000e-11ec-b801-cadd0a5eefbb
  - foaf_Person:
      foaf_givenName: Krishnendu
      foaf_name: Chatterjee, Krishnendu
      foaf_surname: Chatterjee
      foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-4561-241X
  - foaf_Person:
      foaf_givenName: David
      foaf_name: Lurie, David
      foaf_surname: Lurie
      foaf_workInfoHomepage: http://www.librecat.org/personId=579a6c20-34cf-11f1-acbd-8c2f19cdb4da
  - foaf_Person:
      foaf_givenName: Raimundo J
      foaf_name: Saona Urmeneta, Raimundo J
      foaf_surname: Saona Urmeneta
      foaf_workInfoHomepage: http://www.librecat.org/personId=BD1DF4C4-D767-11E9-B658-BC13E6697425
    orcid: 0000-0001-5103-038X
  bibo_doi: 10.1609/aaai.v40i43.40932
  bibo_issue: '43'
  bibo_volume: 40
  dct_date: 2026^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/2159-5399
  - http://id.crossref.org/issn/2374-3468
  dct_language: eng
  dct_publisher: Association for the Advancement of Artificial Intelligence@
  dct_title: 'Revealing POMDPs: Qualitative and quantitative analysis for parity objectives@'
...