Branching Bisimulation Learning
Alessandro Abate, Mirco Giacobbe, Christian Micheletti, Yannik Schnitzer · 2025
Read Branching Bisimulation Learning by Alessandro Abate, Mirco Giacobbe, Christian Micheletti, Yannik Schnitzer (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-12246.txt.
Introduction
Alessandro Abate and three co-authors presented in 2025 a learning method that shrinks complex systems into faithful small models. The shrink, called a bisimulation, merges states that behave alike, including silent steps that older methods ignored. Past learning versions handled only systems with one set path.
Their version covers systems with bounded choice at each step, which unlocks checks of branching-time logic. The method trains a decision tree on sample moves, then proves it against every move with a solver. The small models stay sound and automatic to build. Tests on varied benchmarks show they stay compact and useful for formal checks.
Catalog record
| CREATOR | Alessandro Abate, Mirco Giacobbe, Christian Micheletti, Yannik Schnitzer |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 77 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-12246
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Branching Bisimulation Learning Alessandro Abate, Mirco Giacobbe, Christian Micheletti, Yannik Schnitzer Abstract We introduce a bisimulation learning algorithm for non-deterministic transition systems. We generalise bisimulation learning to systems with bounded branching and extend its applicability to model checking branching-time temporal logic, while previously it was limited to deterministic systems and model checking linear-time properties. Our method computes a finite stutter-insensitive bisimulation quotient of the system under analysis, represented as a decision tree. We adapt the proof rule for well-founded bisimulations to an iterative procedure that trains candidate decision trees from sample transitions of the system, and checks their validity over the entire transition relation using SMT solving. This results in a new technology for model checking CTL* without the next-time operator. Our technique is sound, entirely automated, and yields abstractions that are succinct and effective for formal verification and system diagnostics. We demonstrate the efficacy of our method on diverse benchmarks comprising concurrent software, communication protocols and robotic scenarios. Our method performs comparably to mature tools in the special case of LTL model checking, and outperforms the state of the art in CTL and CTL* model checking for systems with very large and countably infinite state space. 1 Introduction Bisimulation establishes equivalence between transition systems, ensuring they exhibit identical observable behaviour across all possible computation trees. It captures not only the linear traces of system interactions but also the branching structure of their potential evolutions, making it a powerful characterisation for the abstraction of systems. This enables the efficient analysis of complex concrete systems by reducing them to simpler abstract systems that capture the behaviour that is essential for model checking a formal specification. When the concrete system and its abstract counterpart are in a bisimulation relation, their observable branching behaviour is indistinguishable. As a result, model checking linear- and branching-time temporal logic yield the same result on the abstract and the concrete system, even in the presence of non-determinism. Algorithms for computing bisimulations have been developed extensively for systems with finite state spaces. The Paige-Tarjan algorithm for partition refinement laid the foundations for the automated constructions of bisimulation relations and their respective quotients [ 67 ] . Partition refinement is the state of the art for this purpose, and has lent itself to extension towards on-the-fly quotient construction and symbolic as well as parallel implementations [ 57 , 20 , 58 , 34 , 60 ] . These produce the coarsest bisimulation quotient, namely the most succinct representation possible of a bisimulation. Yet, this can be prohibitively expensive to compute for systems with large state spaces and complex arithmetic pathways, both when using explicit-state and symbolic algorithms. Consequently, model-checking techniques based on the partition refinement algorithm are typically restricted to systems with smaller state spaces and simpler transition logic. Counterexample-guided abstraction refinement (CEGAR) has enabled the incremental construction of abstract systems using satisfiability modulo theory (SMT) solvers, benefitting from their ability to reason effectively over arithmetic constraints [ 28 , 9 ] . Modern software, hardware and cyber-physical systems are rich in arithmetic operations and have often very large state spaces. As a result, significant progress in software model checking and the verification of cyber-physical systems has been driven by advancements in CEGAR [ 47 , 13 , 14 , 36 , 72 , 50 ] , specifically designed to compute simulation quotients to prove safety properties [ 40 ] . However, for model checking liveness properties and linear-time logic, CEGAR requires non-trivial adaptation [ 31 , 29 , 69 ] , and branching-time logic is entirely out of scope for simulation quotients. Bisimulation learning has introduced an incremental approach to computing bisimulation quotients [ 3 ] , where information about the system is learned from counterexample models—as happens in counterexample-guided inductive synthesis (CEGIS) [ 71 ] —as opposed to counterexample proofs—as happens in CEGAR [ 46 , 61 ] . Bisimulation learning relies on a parameterised representation of a quotient, such as a decision tree, and trains its parameters to fit a bisimulation quotient over sampled transitions of the system. Then, an adversarial component, such as an SMT solver, is used to check whether the quotient satisfies the bisimulation property across the entire state space and, upon a negative answer, propose counterexample transitions for further re-training of the quotient parameters. While in principle bisimulation relations preserve branching-time logic and support non-determinism, bisimulation learning was limited to deterministic systems and linear-time logic specifications [ 3 , 2 ] . We introduce a new, generalised bisimulation learning algorithm. Our result builds upon the proof rule for well-founded bisimulation [ 65 ] , which we specialise to systems with bounded branching and integrate it within a bisimulation learning algorithm for non-deterministic systems. While well-founded bisimulations were originally developed for interactive theorem proving, our result enables their fully automated construction. We represent finite stutter-insensitive bisimulation quotients of non-deterministic systems, and enable the effective abstraction of systems with very large or countably infinite state space. Stutter-insensitive bisimulations are indistinguishable to an external observer that cannot track intermediate transitions lacking an observable state change in a system. It is a standard result that stutter-insensitive bisimulation is an abstract semantics for \text{CTL}^{*}_{\setminus\bigcirc} —the branching-time logic \text{CTL}^{*} without the next-time operator [ 33 ] . In other words, when the abstract system corresponds to a stutter-insensitive bisimulation quotient and distinguishes at least the atomic propositions of the \text{CTL}^{*}_{\setminus\bigcirc} formula \phi , then the answers to model checking \phi on the abstract system and the concrete system agree. We demonstrate the efficacy of our method on a standard set of benchmarks for the formal verification of finite and infinite state systems against linear-time and branching-time temporal logic. We compare the runtime performance of our prototype with mature tools for the termination analysis of software (CPAChecker and Ultimate), LTL and CTL model checking finite-state systems (nuXmv), LTL model checking infinite-state systems (nuXmv and UltimateLTL), and CTL* model checking infinite-state systems (T2). Our method performs comparably to mature tools for termination analysis, finite-state model checking, and LTL model checking infinite-state systems, while yielding superior results in branching-time model checking infinite-state systems. Overall, our technology addresses the general CTL* model checking problem for infinite-state systems, performs comparably to specialised tools for linear-time properties, and establishes a new state of the art in branching-time model checking. Our contribution is threefold. First, we generalise bisimulation learning to non-deterministic transition systems, leveraging the proof rule for well-founded bisimulations which we fully automate. Second, we introduce a new model checking algorithm for infinite-state systems against CTL* without the next-time operator. Third, we demonstrate the efficacy of our general approach on standard benchmarks which not only compares favourably with the state of the art but also provides more informative results. Our method produces succinct stutter-insensitive bisimulation quotients of the system under analysis. In conjunction with a fix-point based model checking algorithm, this yields the exact initial conditions for which the concrete system satisfies a given specification. 2 Model Checking We consider the problem of determining whether state transition systems with countable (possibly infinite) state space satisfy linear-time and branching-time temporal logic specifications. More precisely, we consider the model checking problem of non-deterministic transition systems with bounded branching with respect to linear-time and branching-time specifications expressed