Abstract
Probabilistic Weighted Automata (PWA) provide a formal framework for modeling systems that exhibit both numerical weights (e.g., energy, time) and stochastic behavior. This paper maps the theoretical landscape of PWA, comparing them to traditional nondeterministic weighted models. We establish a hierarchy of expressive power and identify the decidability boundaries for verification problems across different value aggregation functions.
Introduction
Traditional formal verification often focuses on boolean properties—whether a system satisfies a specification or not. However, modern complex systems require quantitative assessments: "What is the expected energy consumption?" or "What is the probability of meeting a response time threshold?" While Weighted Automata (WA) handle numerical values through nondeterminism, they lack the ability to model inherent randomness. Probabilistic Weighted Automata (PWA) bridge this gap by combining transition weights with probability distributions.
As shown in Figure 2, PWA can represent systems with different performance profiles. For instance, a "low reliability but cheap" system (a) might have a higher probability of failure (transitioning to a high-cost 'ack' state) compared to a "high reliability but expensive" system (b). This allows engineers to specify non-functional requirements like quality-of-service levels in randomized environments.
Methods and Semantics
A PWA is a finite automaton where transitions are assigned weights and chosen according to a probability distribution. The value of an infinite sequence of inputs (a word) is determined by a value function that aggregates weights over a run. Key functions analyzed include:
- Supremum (Sup): The maximum weight encountered.
- Limit Average (LimAvg): The long-term average weight.
- Discounted Sum (Disc): A sum where future weights are geometrically discounted.
The paper evaluates these values under two primary semantics:
- Positive Semantics ($>0$): The value is the supremum of $v$ such that the probability of achieving at least $v$ is strictly positive.
- Almost-Sure Semantics ($=1$): The value is the supremum of $v$ such that the probability of achieving at least $v$ is exactly 1.
Key Insights: Expressiveness and Decidability
The inclusion of probabilities fundamentally changes the model's capabilities. For most value functions, probabilistic choice makes the model strictly more expressive than its nondeterministic counterpart.
As illustrated in the hierarchy in Figure 4, the authors proved specific relationships between classes, such as $NLIMINF \subsetneq POSLIMINF \subsetneq ASLIMINF$. This indicates that almost-sure semantics can describe behaviors that positive semantics cannot, and both are more powerful than standard nondeterministic models.
However, this increased power comes at a cost. While verification problems like emptiness (checking if any word meets a threshold) are decidable for Sup and Discounted Sum models, they become undecidable for LimSup and LimInf models. This "decidability wall" highlights the inherent difficulty in verifying long-term average properties in stochastic systems.
Conclusion and Future Work
PWA offer a robust mathematical tool for quantitative verification, yet they introduce significant algorithmic challenges. Future research remains focused on closing the "Limit Average Gap"—specifically determining the decidability of emptiness for LimInf under positive semantics—and exploring closure properties under operations like summation for various PWA classes.
Summary updated