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
- 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
- scientific article; zbMATH DE number 1134975 (Why is no real title available?)
- scientific article; zbMATH DE number 3240812 (Why is no real title available?)
- 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)- Convex language semantics for nondeterministic probabilistic automata
- Event algebra for transition systems composition application to timed automata
- Weighted restarting automata
- Weighted automata and weighted MSO logics for average and long-time behaviors
- Non-deterministic weighted automata evaluated over Markov chains
- Probabilistic automata of bounded ambiguity
- A Nivat theorem for weighted picture automata and weighted MSO logics
- Expressiveness and closure properties for quantitative languages
- A Nivat theorem for weighted picture automata and weighted MSO logic
- Probabilistic automata and probabilistic logic
- Determinizing discounted-sum automata
- Stochastization of weighted automata
- Quantitative languages
- Randomization in automata on infinite trees
- Weighted unranked tree automata over tree valuation monoids and their characterization by weighted logics
- Regular Expressions on Average and in the Long Run
- Weighted Tree Automata over Valuation Monoids and Their Characterization by Weighted Logics
- Valuations of weighted automata: doing it in a rational way
- Max and sum semantics for alternating weighted automata
- What's decidable about weighted automata?
- Probabilistic asynchronous automata
- Non-deterministic Weighted Automata on Random Words
- Probabilistic ω-automata
- Exact and approximate determinization of discounted-sum automata
- On the comparison of discounted-sum automata with multiple discount factors
- On the Verification of Weighted Kripke Structures Under Uncertainty
- Between deterministic and nondeterministic quantitative automata (invited talk)
- Deterministic weighted automata under partial observability
- Discounted-sum automata with multiple discount factors
- Discounted-sum automata with multiple discount factors
- Discounted-sum automata with real-valued discount factors
- Weighted automata and multi-valued logics over arbitrary bounded lattices
- Containment and equivalence of weighted automata: probabilistic and max-plus cases
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)
