Probabilistic weighted automata
LNCS
Chatterjee, Krishnendu
Doyen, Laurent
Henzinger, Thomas A
ddc:000
ddc:005
Nondeterministic weighted automata are finite automata with numerical weights oil transitions. They define quantitative languages 1, that assign to each word v; a real number L(w). The value of ail infinite word w is computed as the maximal value of all runs over w, and the value of a run as the supremum, limsup liminf, limit average, or discounted sum of the transition weights. We introduce probabilistic weighted antomata, in which the transitions are chosen in a randomized (rather than nondeterministic) fashion. Under almost-sure semantics (resp. positive semantics), the value of a word v) is the largest real v such that the runs over w have value at least v with probability I (resp. positive probability). We study the classical questions of automata theory for probabilistic weighted automata: emptiness and universality, expressiveness, and closure under various operations oil languages. For quantitative languages, emptiness university axe defined as whether the value of some (resp. every) word exceeds a given threshold. We prove some, of these questions to he decidable, and others undecidable. Regarding expressive power, we show that probabilities allow its to define a wide variety of new classes of quantitative languages except for discounted-sum automata, where probabilistic choice is no more expressive than nondeterminism. Finally we live ail almost complete picture of the closure of various classes of probabilistic weighted automata for the following, provide, is operations oil quantitative languages: maximum, sum. and numerical complement.
Springer
2009
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
http://purl.org/coar/resource_type/c_5794
https://research-explorer.ista.ac.at/record/3871
https://research-explorer.ista.ac.at/download/3871/4771
Chatterjee K, Doyen L, Henzinger TA. Probabilistic weighted automata. In: Vol 5710. Springer; 2009:244-258. doi:<a href="https://doi.org/10.1007/978-3-642-04081-8_17">10.1007/978-3-642-04081-8_17</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-642-04081-8_17
info:eu-repo/grantAgreement/EC/FP7/214373
info:eu-repo/grantAgreement/EC/FP7/215543
info:eu-repo/semantics/openAccess