---
res:
bibo_abstract:
- 'We consider probabilistic automata on infinite words with acceptance defined
by parity conditions. We consider three qualitative decision problems: (i) the
positive decision problem asks whether there is a word that is accepted with positive
probability; (ii) the almost decision problem asks whether there is a word that
is accepted with probability 1; and (iii) the limit decision problem asks whether
words are accepted with probability arbitrarily close to 1. We unify and generalize
several decidability results for probabilistic automata over infinite words, and
identify a robust (closed under union and intersection) subclass of probabilistic
automata for which all the qualitative decision problems are decidable for parity
conditions. We also show that if the input words are restricted to lasso shape
(regular) words, then the positive and almost problems are decidable for all probabilistic
automata with parity conditions. For most decidable problems we show an optimal
PSPACE-complete complexity bound.@eng'
bibo_authorlist:
- 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: Mathieu
foaf_name: Tracol, Mathieu
foaf_surname: Tracol
foaf_workInfoHomepage: http://www.librecat.org/personId=3F54FA38-F248-11E8-B48F-1D18A9856A87
bibo_doi: 10.1109/LICS.2012.29
dct_date: 2012^xs_gYear
dct_language: eng
dct_publisher: IEEE@
dct_title: Decidable problems for probabilistic automata on infinite words@
...