Bisimulation Learning
Abstract
Abstract We introduce a data-driven approach to computing finite bisimulations for state transition systems with very large, possibly infinite state space. Our novel technique computes stutter-insensitive bisimulations of deterministic systems, which we characterize as the problem of learning a state classifier together with a ranking function for each class. Our procedure learns a candidate state classifier and candidate ranking functions from a finite dataset of sample states; then, it checks whether these generalise to the entire state space using satisfiability modulo theory solving. Upon the affirmative answer, the procedure concludes that the classifier constitutes a valid stutter-insensitive bisimulation of the system. Upon a negative answer, the solver produces a counterexample state for which the classifier violates the claim, adds it to the dataset, and repeats learning and checking in a counterexample-guided inductive synthesis loop until a valid bisimulation is found. We demonstrate on a range of benchmarks from reactive verification and software model checking that our method yields faster verification results than alternative state-of-the-art tools in practice. Our method produces succinct abstractions that enable an effective verification of linear temporal logic without next operator, and are interpretable for system diagnostics.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
4 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Neural Abstractions cites Neural termination analysis
- Stochastic Omega-Regular Verification and Control with Supermartingales cites Neural termination analysis
- Quantitative Supermartingale Certificates cites Stochastic Omega-Regular Verification and Control with Supermartingales
- Quantitative Supermartingale Certificates cites Neural Model Checking
- Quantitative Supermartingale Certificates cites Branching Bisimulation Learning
- Quantitative Supermartingale Certificates cites Neural termination analysis
- Neural Model Checking cites Stochastic Omega-Regular Verification and Control with Supermartingales
- Neural Model Checking cites Neural termination analysis
Cited by top-tier papers4
- Neural Model CheckingMirco Giacobbe, Daniel Kroening, Abhinandan Pal, Michael TautschnigNeurIPS 2024 · 17 citations
- Stochastic Omega-Regular Verification and Control with SupermartingalesAlessandro Abate, Mirco Giacobbe, Diptarko RoyCAV 2024 · 13 citations
- Quantitative Supermartingale CertificatesAlessandro Abate, Mirco Giacobbe, Diptarko RoyCAV 2025 · 7 citations
- Branching Bisimulation LearningAlessandro Abate, Mirco Giacobbe, Christian Micheletti, Yannik SchnitzerCAV 2025
Builds on3
- Neural AbstractionsAlessandro Abate, Alec Edwards, Mirco GiacobbeNeurIPS 2022 · 25 citations
- Neural termination analysisMirco Giacobbe, Daniel Kroening, Julian ParsertFSE 2022 · 16 citations
- Stochastic Omega-Regular Verification and Control with SupermartingalesAlessandro Abate, Mirco Giacobbe, Diptarko RoyCAV 2024 · 13 citations
Related papers
- Let a Neural Network be Your InvariantMirco Giacobbe, Daniel Kroening, Abhinandan Pal, Michael TautschnigNeurIPS 2025 · 6 citations
- DistAI: Data-Driven Automated Invariant Learning for Distributed ProtocolsJianan Yao, Runzhou Tao, Ronghui Gu, Jason Nieh et al.OSDI 2021 · 76 citations
- Decision Tree Learning in CEGIS-Based Termination AnalysisSatoshi Kura, Hiroshi Unno, Ichiro HasuoCAV 2021 · 6 citations
- Learning to Synthesize Relational InvariantsJingbo Wang, Chao WangASE 2022 · 9 citations
- Data-driven Recurrent Set Learning For Non-termination AnalysisZhilei Han, Fei HeICSE 2023 · 1 citation
