Bisimulation Learning
<|reference_start|>Bisimulation Learning: 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.<|reference_end|>
@article{abate2024bisimulation,
    title={Bisimulation Learning},
    author={Alessandro Abate, Mirco Giacobbe, Yannik Schnitzer},
    journal={arXiv preprint arXiv:2405.15723},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.15723},
    primaryClass={cs.LO cs.LG}
}