@misc{5392, abstract = {We consider probabilistic automata on infinite words with acceptance defined by safety, reachability, Büchi, coBüchi and limit-average conditions. We consider quantitative and qualitative decision problems. We present extensions and adaptations of proofs of [GO09] and present a precise characterization of the decidability and undecidability frontier of the quantitative and qualitative decision problems.}, author = {Chatterjee, Krishnendu}, issn = {2664-1690}, pages = {17}, publisher = {IST Austria}, title = {{Probabilistic automata on infinite words: Decidability and undecidability results}}, doi = {10.15479/AT:IST-2009-0004}, year = {2009}, } @misc{5395, abstract = {We study observation-based strategies for partially-observable Markov decision processes (POMDPs) with omega-regular objectives. An observation-based strategy relies on partial information about the history of a play, namely, on the past sequence of observa- tions. We consider the qualitative analysis problem: given a POMDP with an omega-regular objective, whether there is an observation-based strategy to achieve the objective with probability 1 (almost-sure winning), or with positive probability (positive winning). Our main results are twofold. First, we present a complete picture of the computational complexity of the qualitative analysis of POMDPs with parity objectives (a canonical form to express omega-regular objectives) and its subclasses. Our contribution consists in establishing several upper and lower bounds that were not known in literature. Second, we present optimal bounds (matching upper and lower bounds) on the memory required by pure and randomized observation-based strategies for the qualitative analysis of POMDPs with parity objectives and its subclasses.}, author = {Chatterjee, Krishnendu and Doyen, Laurent and Henzinger, Thomas A}, issn = {2664-1690}, pages = {20}, publisher = {IST Austria}, title = {{Qualitative analysis of partially-observable Markov decision processes}}, doi = {10.15479/AT:IST-2009-0001}, year = {2009}, }