Conference item
Bisimulation learning
- 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 2.8MB, Terms of use)
-
- Publisher copy:
- 10.1007/978-3-031-65633-0_8
Authors
- Publisher:
- Springer
- Host title:
- Computer Aided Verification 36th International Conference, CAV 2024, Montreal, QC, Canada, July 24–27, 2024, Proceedings, Part III
- Pages:
- 161–183
- Series:
- Lecture Notes in Computer Science
- Series number:
- 14683
- Publication date:
- 2024-07-26
- Acceptance date:
- 2024-03-27
- Event title:
- 36th International Conference on Computer Aided Verification (CAV 2024)
- Event location:
- Montreal, QC, Canada
- Event website:
- https://i-cav.org/2024/
- Event start date:
- 2024-07-24
- Event end date:
- 2024-07-27
- DOI:
- EISSN:
-
1611-3349
- ISSN:
-
0302-9743
- EISBN:
- 9783031656330
- ISBN:
- 9783031656323
- Language:
-
English
- Keywords:
- Pubs id:
-
2019918
- Local pid:
-
pubs:2019918
- Deposit date:
-
2024-08-03
- ARK identifier:
Terms of use
- Copyright holder:
- Abate et al.
- Copyright date:
- 2024
- Rights statement:
- © 2024 The Author(s). This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made. The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
- Notes:
- This paper was presented at the 36th International Conference on Computer Aided Verification (CAV 2024), 24th-27th July 2024, Montreal, QC, Canada.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record