Paper Info
Title
Probabilistic Automata Over Infinite Words: Expressiveness, Efficiency, And Decidability
Abstract
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 Buchi 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.
Year
DOI
Venue
2009
10.4204/EPTCS.3.1
ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE
Keywords
Field
DocType
probabilistic automata,formal language,decision problem,probability measure,automata theory
Discrete mathematics,Decision problem,Probability measure,Theoretical computer science,Decidability,Probabilistic logic,Probabilistic automaton,Semantics,Mathematics,ω-automaton,Expressivity
Journal
Volume
Issue
ISSN
abs/0907.4
3
2075-2180
Citations 
PageRank 
References 
1
0.37
10
Authors
3
Name
Order
Citations
PageRank
Christel Baier13053185.85
Nathalie Bertrand225017.84
Marcus Größer333418.23