Computation Tree Logic Model Checking Based on Possibility Measures

Yongming Li, Yali Li, Zhanyou Ma

This paper explores a specialized branch of formal verification designed to handle "fuzzy" uncertainty. While traditional model checking deals with absolute truths and probabilistic model checking deals with likelihoods, this work focuses on Possibilistic Computation Tree Logic (PoCTL). The authors prove that PoCTL is strictly more powerful than standard Computation Tree Logic (CTL) and provide an efficient algorithm to verify these complex, uncertain properties in computer systems.

TL;DR

The authors demonstrate that Possibilistic CTL (PoCTL) is a superior framework for verifying systems with non-additive uncertainty, proving it is strictly more expressive than standard CTL. They introduce a polynomial-time model-checking algorithm that uses fuzzy matrix operations to verify system properties, even when information is vague or incomplete.

What Problem Does This Paper Address?

In the world of formal verification, we want to prove that a system (like a flight controller or a medical device) will always behave correctly. Standard Computation Tree Logic (CTL) is great for this, but it assumes the world is black and white. Probabilistic CTL (PCTL) was later developed to handle "chance" (like a 1% failure rate), but it relies on additive probability—the idea that all possible outcomes must sum to 100%.

However, many real-world scenarios involve "fuzziness" rather than random chance. For example, a doctor’s assessment of a patient as being in "poor" or "fair" condition is a matter of degree and subjective perception, not a dice roll. This is known as possibility theory. Before this paper, it wasn't clear exactly how much more powerful possibilistic logic was compared to standard logic, nor was there a definitive, efficient way to check these properties automatically.

Methods

The authors build their framework on Possibilistic Kripke Structures (PKS). In a PKS, transitions between states aren't just "yes/no" or "0.5 probability"; they are assigned a "possibility degree" between 0 and 1. Crucially, these degrees are non-additive: the most possible path defines the possibility of an event.

The core technical contributions include:

  1. Expressiveness Mapping: The authors formally prove that every CTL formula has an equivalent PoCTL formula.
  2. The PoCTL Algorithm: They adapt the standard bottom-up labeling algorithm used in CTL. To handle the "Until" operator ($\sqcup$), which is the hardest part of model checking, they use max-min composition of fuzzy matrices.
  3. Complexity Analysis: They prove that checking a PoCTL formula is computationally efficient, with a time complexity of $O(size(M) \cdot N \cdot |\Phi|)$, where $N$ is the number of states and $|\Phi|$ is the length of the formula.

Datasets

This is a theoretical paper in computer science, so it does not use large-scale empirical datasets. Instead, the authors use a demonstrative medical example:

  • The Scenario: An animal with a new disease is treated with a drug (Ribavirin).
  • The Model: A three-state system representing "poor," "fair," and "excellent" health conditions.
  • The Goal: To verify properties like "the animal will eventually recover with a possibility of 1" using their new algorithm.

Key Insights and Ideas

  • CTL is a Proper Subclass: The most surprising finding is that PoCTL is strictly more expressive than CTL. In the probabilistic world, CTL and PCTL are "incomparable" (some things one can say, the other cannot). In the possibilistic world, PoCTL can do everything CTL can do, plus much more.
  • Qualitative Power: Even "qualitative" PoCTL (which only cares if a possibility is $>0$ or $=1$) can express complex behaviors like repeated reachability (an event happens infinitely often) and persistence (an event eventually stays true forever) that standard CTL struggles with in uncertain contexts.
  • Computational Elegance: Because possibility theory relies on the "maximum" and "minimum" of values rather than sums and products, the math simplifies. Instead of solving complex systems of linear equations (as PCTL requires), PoCTL model checking relies on calculating the transitive closure of fuzzy matrices.

Key Results

  • Formal Equivalence: The paper provides a direct translation table between CTL operators (like $\exists$, $\forall$, $\text{Next}$, and $\text{Until}$) and PoCTL formulae.
  • Efficiency: The proposed algorithm is polynomial in time, making it practically applicable to finite-state systems.
  • Verification of Persistence: The authors successfully showed how to specify and verify persistence properties with a possibility of 1, a feat that is not possible in standard CTL for these types of uncertain models.

Limitations and Future Work

  • Infinite State Spaces: The authors provide a counterexample showing that some of their equivalence results do not hold if the system has an infinite number of states.
  • Crisp Labeling: Currently, the "labels" on states (e.g., "the patient is healthy") are still binary (true/false). The authors suggest that future work should allow for fuzzy labeling, where even the basic propositions have degrees of truth.
  • Alternative Compositions: The paper uses "max-min" math. The authors note that other types of fuzzy logic (like "max-product") could be explored for different types of industrial applications.
  • Tooling: While the theory is now solid, there is no "push-button" software tool (like a possibilistic version of the popular NuSMV checker) yet available for engineers to use.

Summary updated

Abstract

In order to deal with the systematic verification with uncertain infromation in possibility theory, Li and Li \cite{li12} introduced model checking of linear-time properties in which the uncertainty is modeled by possibility measures. Xue, Lei and Li \cite{Xue09} defined computation tree logic (CTL) based on possibility measures, which is called possibilistic CTL (PoCTL). This paper is a continuation of the above work. First, we study the expressiveness of PoCTL. Unlike probabilistic CTL, it is shown that PoCTL (in particular, qualitative PoCTL) is more powerful than CTL with respect to their expressiveness. The equivalent expressions of basic CTL formulae using qualitative PoCTL formulae are presented in detail. Some PoCTL formulae that can not be expressed by any CTL formulae are presented. In particular, some qualitative properties of repeated reachability and persistence are expressed using PoCTL formulae. Next, adapting CTL model-checking algorithm, a method to solve the PoCTL model-checking problem and its time complexity are discussed in detail. Finally, an example is given to illustrate the PoCTL model-checking method.
BibTeX
@inproceedings{li2014computation,
  author = {Yongming Li and Yali Li and Zhanyou Ma},
  title = {{Computation Tree Logic Model Checking Based on Possibility Measures}},
  booktitle = {Fuzzy},
  year = {2014},
  doi = {10.1016/j.fss.2014.03.009},
}
Figure