Computer Science – Formal Languages and Automata Theory
Scientific paper
2009-07-28
EPTCS 3, 2009, pp. 3-16
Computer Science
Formal Languages and Automata Theory
Scientific paper
10.4204/EPTCS.3.1
Probabilistic omega-automata are variants of nondeterministic automata for infinite words where all choices are resolved by probabilistic distributions. Acceptance of an infinite input word can be defined in different ways: by requiring that (i) the probability for the accepting runs is positive (probable semantics), or (ii) almost all runs are accepting (almost-sure semantics), or (iii) the probability measure of the accepting runs is greater than a certain threshold (threshold semantics). The underlying notion of an accepting run can be defined as for standard omega-automata by means of a Buechi condition or other acceptance conditions, e.g., Rabin or Streett conditions. In this paper, we put the main focus on the probable semantics and provide a summary of the fundamental properties of probabilistic omega-automata concerning expressiveness, efficiency, and decision problems.
Baier Christel
Bertrand Nathalie
Größer Marcus
No associations
LandOfFree
Probabilistic Automata over Infinite Words: Expressiveness, Efficiency, and Decidability 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 Probabilistic Automata over Infinite Words: Expressiveness, Efficiency, and Decidability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Probabilistic Automata over Infinite Words: Expressiveness, Efficiency, and Decidability will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-681032