Probabilistic Weighted Automata
From MaRDI portal
Abstract: Nondeterministic weighted automata are finite automata with numerical weights on transitions. They define quantitative languages L that assign to each word w a real number L(w). The value of an infinite word w is computed as the maximal value of all runs over w, and the value of a run as the maximum, limsup, liminf, limit average, or discounted sum of the transition weights. We introduce probabilistic weighted automata, 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 w is the largest real v such that the runs over w have value at least v with probability 1 (resp. positive probability). We study the classical questions of automata theory for probabilistic weighted automata: emptiness and universality, expressiveness, and closure under various operations on languages. For quantitative languages, emptiness and universality are defined as whether the value of some (resp. every) word exceeds a given threshold. We prove some of these questions to be decidable, and others undecidable. Regarding expressive power, we show that probabilities allow us 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 give an almost complete picture of the closure of various classes of probabilistic weighted automata for the following pointwise operations on quantitative languages: max, min, sum, and numerical complement.
Recommendations
Cites work
- scientific article; zbMATH DE number 1134975 (Why is no real title available?)
- scientific article; zbMATH DE number 3240812 (Why is no real title available?)
- Alternating Weighted Automata
- Automata, Languages and Programming
- Automata, logics, and infinite games. A guide to current research
- Correct Hardware Design and Verification Methods
- Expressiveness and closure properties for quantitative languages
- Finite Automata Computing Real Functions
- Mathematical Foundations of Computer Science 2004
- On Decision Problems for Probabilistic Büchi Automata
- Positional strategies for mean payoff games
- Probabilistic automata
- Quantitative Languages
- Quantitative stochastic parity games
- Skew and infinitary formal power series
- Stochastic Games
- The complexity of probabilistic verification
- Undecidable problems for probabilistic automata of fixed dimension
Cited in
(33)- Non-deterministic Weighted Automata on Random Words
- Discounted-sum automata with multiple discount factors
- Weighted automata and weighted MSO logics for average and long-time behaviors
- Discounted-sum automata with real-valued discount factors
- Between deterministic and nondeterministic quantitative automata (invited talk)
- Probabilistic ω-automata
- Non-deterministic weighted automata evaluated over Markov chains
- Exact and approximate determinization of discounted-sum automata
- Valuations of weighted automata: doing it in a rational way
- Determinizing discounted-sum automata
- Probabilistic automata of bounded ambiguity
- What's decidable about weighted automata?
- Probabilistic asynchronous automata
- Event algebra for transition systems composition application to timed automata
- Expressiveness and closure properties for quantitative languages
- Weighted Tree Automata over Valuation Monoids and Their Characterization by Weighted Logics
- Discounted-sum automata with multiple discount factors
- Stochastization of weighted automata
- Convex language semantics for nondeterministic probabilistic automata
- Randomization in automata on infinite trees
- Quantitative languages
- Weighted restarting automata
- Weighted unranked tree automata over tree valuation monoids and their characterization by weighted logics
- On the comparison of discounted-sum automata with multiple discount factors
- Containment and equivalence of weighted automata: probabilistic and max-plus cases
- Probabilistic automata and probabilistic logic
- A Nivat theorem for weighted picture automata and weighted MSO logic
- On the Verification of Weighted Kripke Structures Under Uncertainty
- Weighted automata and multi-valued logics over arbitrary bounded lattices
- Regular Expressions on Average and in the Long Run
- A Nivat theorem for weighted picture automata and weighted MSO logics
- Max and sum semantics for alternating weighted automata
- Deterministic weighted automata under partial observability
This page was built for publication: Probabilistic Weighted Automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3184677)
