Reasoning About Bounds in Weighted Transition Systems

Mikkel Hansen, Kim G. Larsen, Radu Mardare, Mathias Ruggaard Pedersen

Abstract

This paper presents a novel modal logic framework for Weighted Transition Systems (WTS) that prioritizes interval-based reasoning over exact weight matching. By focusing on upper and lower bounds of transition costs, the authors establish a robust system for verifying Cyber-Physical Systems (CPS) subject to measurement uncertainty. The work includes a sound and complete finitary axiomatization and a decidable tableau-based satisfiability procedure, bridging the gap between theoretical formal methods and practical system verification.

What Problem Does This Paper Address?

Weighted Transition Systems (WTSs) are standard tools for modeling systems where actions have costs, such as bandwidth usage in a network or battery consumption in a robot. Traditionally, these models require precise weights for every transition. However, in the real world—especially in Cyber-Physical Systems (CPS)—measurements are rarely exact. Sensors have noise, and physical processes like "recharging a battery" or "cleaning a room" vary in duration.

A Weighted Transition System (WTS) modeling a robot vacuum cleaner with states for waiting, cleaning, and charging.

Standard WTSs are too "rigid" to handle this inherent uncertainty. If two states have slightly different transition weights, a standard model-checking tool would treat them as completely different, even if their behavior is effectively the same within a certain tolerance. The authors set out to create a logic that allows for approximate reasoning, enabling developers to ask questions like: "Is the minimum cost to reach a safe state at least 5?" or "Is the maximum cost to finish this task at most 10?"

Methods

The authors develop several interconnected theoretical tools to handle this uncertainty:

  1. Generalized Weighted Bisimulation: A new, "coarser" definition of state equivalence. Instead of requiring exact weight matches, it only requires that the minimum and maximum weights to reach equivalent sets of states are the same.
  2. Modal Logic ($\mathcal{L}$): A logic featuring two primary modal operators:
  3. $L_r\phi$: The lower bound of the cost to reach a state satisfying $\phi$ is at least $r$.
  4. $M_r\phi$: The upper bound of the cost to reach a state satisfying $\phi$ is at most $r$.
  5. Finitary Axiomatization: A finite set of axioms that are both sound and complete, avoiding the infinite rule sets common in other quantitative logics.
  6. Tableau Method: An algorithmic procedure to determine if a logical formula is satisfiable and to construct a sample model.

Key Insights and Ideas

The Power of Abstraction

By "hiding" the specific weights of individual transitions and only looking at the infimum (minimum) and supremum (maximum) of the "image set" of weights, the authors create a model that is robust against small fluctuations in data. This makes the logic mathematically "coarser" than the classic version, which is a significant advantage for practical verification.

Illustration of generalized weighted bisimulation where systems with different intermediate weights share the same bounds.

As illustrated in Figure 3, the system on the left (with weights {1, 2, 3}) and the system on the right (with weights {1, 3}) are considered equivalent under this logic. Both share an infimum of 1 and a supremum of 3. The intermediate weight '2' is abstracted away, allowing the logic to group together states that behave similarly under uncertainty.

Finitary Completeness and Decidability

One of the most significant technical achievements is proving that the logic is "finitary." Many similar logics in the probabilistic domain require "infinitary" rules (rules with an infinite number of premises) to achieve completeness. The authors avoided this, making the logic much more amenable to automated theorem proving. Furthermore, they prove the Finite Model Property: if a formula has any model at all, it must have a finite model, which ensures the satisfiability problem is decidable.

Key Results

  • Bisimulation Invariance: The logic perfectly captures the intended notion of "approximate equivalence."
  • Soundness and Completeness: The authors successfully provided a complete axiomatic system, bridging the gap between abstract logic and automated reasoning.
  • Decidability: The paper provides a tableau-based algorithm that can automatically check if a system specification is consistent.

Limitations and Future Work

While the logic achieves "weak" completeness, it is non-compact, meaning "strong" completeness (reasoning from infinite sets of assumptions) remains a challenge. Additionally, the current logic is purely modal and lacks temporal operators like "Until" or fixed-point operators. Future research will likely focus on these temporal features and exploring the accumulation of weights over entire paths rather than single steps, which is essential for reasoning about total energy consumption in long-term missions.

Summary updated

Abstract

We propose a way of reasoning about minimal and maximal values of the weights of transitions in a weighted transition system (WTS). This perspective induces a notion of bisimulation that is coarser than the classic bisimulation: it relates states that exhibit transitions to bisimulation classes with the weights within the same boundaries. We propose a customized modal logic that expresses these numeric boundaries for transition weights by means of particular modalities. We prove that our logic is invariant under the proposed notion of bisimulation. We show that the logic enjoys the finite model property and we identify a complete axiomatization for the logic. Last but not least, we use a tableau method to show that the satisfiability problem for the logic is decidable.
BibTeX
@article{hansen2018reasoning,
  author = {Mikkel Hansen and Kim G. Larsen and Radu Mardare and Mathias Ruggaard Pedersen},
  title = {{Reasoning About Bounds in Weighted Transition Systems}},
  journal = {Log. Methods Comput. Sci.},
  year = {2018},
  doi = {10.23638/lmcs-14(4:19)2018},
}
Figure