Submodel Enumeration for CTL Is Hard

Nicolas Fröhlich, Arne MeierAAAI 2024 · DOI

TL;DR

This paper investigates the computational complexity of enumerating "submodels" of a system that satisfy a given temporal logic specification (CTL). They prove that this task is generally "hard" (specifically, DelNP-complete) for most CTL fragments, meaning it's unlikely to be solved efficiently. However, they also identify specific, restricted fragments of CTL that do allow for efficient enumeration, offering a glimmer of hope for practical applications.

What Problem Does This Paper Address?

In software verification, we often use temporal logics like Computation Tree Logic (CTL) to formally describe desired system behaviors. We then use model checking to verify if a system (represented as a Kripke structure, a type of state machine) satisfies these specifications. When a system fails a specification, a useful debugging technique is to find "submodels" – smaller versions of the original system – that do satisfy the specification. This helps pinpoint the problematic parts of the system.

The problem this paper tackles is: How efficiently can we enumerate all such satisfying submodels? While model checking for CTL is known to be efficient (polynomial time), the task of finding all satisfying submodels is a different beast. The authors want to understand the inherent difficulty of this enumeration problem, especially when considering different subsets of CTL operators.

Methods

The core of the paper is a complexity analysis of the submodel enumeration problem. They leverage established frameworks for "hard enumeration problems" and complexity classes like DelP (efficient enumeration) and DelNP (intractable enumeration).

Key techniques include:

  • Formal Definitions: Precisely defining Kripke models, submodels (as subsets of states and transitions), and the semantics of CTL formulas.
  • Complexity Classes: Using DelP and DelNP to categorize the difficulty of enumeration problems. DelP allows for polynomial delay between outputting solutions, while DelNP implies that solutions cannot be generated efficiently unless P=NP.
  • Reductions: Proving hardness by reducing known hard problems (like SAT, HAMPATH) to the submodel enumeration problem for specific CTL fragments. This shows that if the submodel enumeration problem were easy, then the known hard problem would also be easy, which is a contradiction.
  • Duality: Exploiting the duality between existential and universal path quantifiers in CTL (e.g., EF vs. AF) to extend results from one to another.
  • Fragment Analysis: Systematically examining sub-problems based on subsets of CTL operators (e.g., only AG, only AF, only AX, etc.) and combinations of Boolean operators.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity analysis using abstract Kripke models and CTL formulas, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Ubiquitous Hardness: The most striking insight is that enumerating satisfying submodels for CTL is generally hard (DelNP-complete) for most combinations of CTL operators, even when allowing all Boolean connectors. This suggests that finding all minimal failing submodels is computationally expensive.
  • The "Silver Lining": Despite the general hardness, the paper identifies specific fragments of CTL (e.g., involving only EX, ER, EU operators with conjunction and disjunction) where submodel enumeration is tractable (DelP). This means efficient algorithms exist for these restricted cases.
  • Operator Power: The paper highlights how different CTL operators contribute to the complexity. For instance, fragments involving existential operators (EX, EF, EG, EU, ER) are shown to be NP-complete (a step below DelNP-complete), while fragments with universal operators (AX, AF, AG, AU, AR) are generally DelNP-complete.
  • Boolean Connectors Matter: While many CTL operator fragments are hard even with all Boolean connectors, restricting the Boolean connectors (e.g., to only conjunction and disjunction) can lead to tractable enumeration for certain operator sets.

Key Results

  • DelNP-Completeness: The paper proves that submodel enumeration for most CTL operator fragments (including AG, AF, AU, AR, AX) is DelNP-complete, assuming all Boolean connectors are allowed. This is a strong theoretical result indicating inherent difficulty.
  • NP-Completeness: For fragments involving only existential operators (EX, EF, EG, EU, ER), the problem is NP-complete.
  • DelP Tractability: The paper identifies specific fragments, such as those using only EX, ER, EU operators with conjunction and disjunction, for which submodel enumeration is in DelP, meaning it can be done efficiently.
  • Fragment-Specific Reductions: The authors provide explicit reductions from known hard problems (SAT, HAMPATH) to specific CTL fragments, demonstrating their DelNP-completeness.

Limitations and Future Work

  • Vast Number of Fragments: The paper acknowledges that there are a huge number of possible fragments to consider (over 7000 combinations of CTL operators and Boolean connectors). While they cover many key ones, a complete picture is still a significant undertaking.
  • Parameterised Complexity: The authors suggest exploring parameterised complexity as a way to find more efficient subcases, which could be useful for systems with specific structural properties.
  • Practical Debugging: The paper motivates the work by the idea of using submodel enumeration for debugging. Future work could involve a feasibility study to see how these theoretical results translate into practical debugging tools.
  • Other Enumeration Problems: The paper notes that submodel enumeration is just one type of enumeration problem for CTL. Investigating other variants, such as finding minimal modifications to the system's labeling function (η) instead of its structure, is also a promising direction.

Summary updated

BibTeX
@inproceedings{frohlich2024submodel,
  author = {Nicolas Fröhlich and Arne Meier},
  title = {{Submodel Enumeration for CTL Is Hard}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i9.28921},
}
Figure