Lec 39: Backward Reachability in BDD based Symbolic Model Checking

Lec 39: Backward Reachability in BDD based Symbolic Model Checking

by Chandan Karfa · View the channel on PSI

Formal & Physical Sciences Computing & Cybersecurity UMZSoftware EngineeringUMZTSoftware testing and verification
🎙 Chandan Karfa 👥 229K 📅 September 10, 2026 ⏱ 21 min 👁 1 📄 tutorial 🧭 2026-09-10
Available in: English (current) Français

Keywords

BDDbackward reachabilityforward reachabilityCTL model checkingROBDD

Summary

This lecture continues a series on BDD-based symbolic model checking, focusing on backward reachability. The instructor first recaps forward reachability, where a BDD represents the transition relation and reachable states are computed by intersecting with present-state variables and eliminating others. For backward reachability, the target state set is encoded using next-state variables, intersected with the transition relation, and unnecessary variables are eliminated to obtain predecessor states. The method is a direct adaptation of forward traversal, only differing in variable renaming. The lecture then illustrates applications in CTL model checking: for AF, forward reachability is used; for EX and EU, backward reachability is applied. EX requires only one backward step, while EU iterates until a fixed point. The lecture concludes by noting that BDD-based symbolic methods are primarily used in CTL, while LTL model checking uses BDDs only for the fairness check. The exposition is clear, with graphical examples and step-by-step operations.

151 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture excels in its methodical explanation of backward reachability, building on the previously established forward reachability concept. The instructor uses simple examples and clearly demonstrates how BDD operations (AND, variable elimination, renaming) achieve the desired computation. The argumentation is sound, showing that the only difference between forward and backward traversal is the variable set used for restriction. The subsequent connection to CTL operands (EX, EU, AF) effectively motivates the need for backward reachability and shows its direct application. The pacing is appropriate, and the lecturer consistently ties the steps back to the underlying BDD representation. However, the lecture lacks concrete case studies or verification of the method on complex systems, which would strengthen the practical understanding.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is sourced from NPTEL, a government-funded educational initiative in India, and is delivered by Prof. Chandan Karfa, a faculty member at IIT Guwahati, indicating a high level of academic rigor. The description provides links to the full course and playlist, which serve as authoritative references for the material. The content aligns with standard literature on symbolic model checking, such as the seminal works by Bryant on BDDs and Clarke et al. on model checking. The title precisely reflects the content, focusing on backward reachability within BDD-based symbolic model checking. No external sources are cited within the lecture, but the instructor references concepts from previous classes. Overall, the source is reliable and the title accurately represents the tutorial.

251 words

Title / Content Match

The title accurately describes the lecture's focus on backward reachability within BDD-based symbolic model checking, matching the content presented.

Quality & Reliability

8/10

The lecture is delivered by a professor at IIT Guwahati, part of NPTEL, a reputed platform. The content is mathematically rigorous and clearly presented, with step-by-step explanations of BDD operations. However, it assumes prior knowledge and does not provide extensive examples or external references.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

Concurring Sources

Contribution & Novelties

The lecture provides a clear, accessible explanation of backward reachability in BDD-based symbolic model checking, contrasting it with forward reachability and demonstrating its application to CTL operators (EX, EU). It clarifies the variable renaming trick that is essential for computing predecessors. The pedagogical approach of incrementally building on forward traversal helps solidify understanding.

Pour aller plus loin :

  • Binary Decision Diagram — Foundational data structure used throughout the lecture; explains BDD properties and operations.
  • Model Checking — Overview of automatic verification techniques, including symbolic methods and their history.
  • Computation Tree Logic — The logic for which the described CTL model checking algorithms are designed, detailing the semantics of operators like EX, EU, and AF.

114 words

Radar Profile

The radar profile shows high scores in reliability and technical depth, with moderate scores in quantity and quality of information. This indicates a focused, authoritative lecture that assumes prior knowledge but delivers precise content.

Reliability 9/10