Decidable Problems for Probabilistic Automata on Infinite Words

Details Decidable Problems for Probabilistic Automata on Infinite Words Decidable Problems for Probabilistic Automata on Infinite Words

2011-07-11

arxiv.org/abs/1107.2091v1

Computer Science

Formal Languages and Automata Theory

Scientific paper

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 for every epsilon > 0 there is a word that is accepted with probability at least 1 - epsilon. 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.

Affiliated with

Also associated with

No associations

Rating

Decidable Problems for Probabilistic Automata on Infinite Words does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Decidable Problems for Probabilistic Automata on Infinite Words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decidable Problems for Probabilistic Automata on Infinite Words will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-138250