Minimisation of spatial models using branching bisimilarity

Ciancia V., Groote J. F., Latella D., Massink M., De Vink E. P.

Spatial minimisation  Closure spaces  Spatial logics  Spatial bisimilarity  Branching bisimilarity  Spatial model checking 

Spatial logic and spatial model checking have great potential for traditional computer science domains and beyond. Reasoning about space involves two different conditional reachability modalities: a forward reachability, similar to that used in temporal logic, and a backward modality representing that a point can be reached from another point, under certain conditions. Since spatial models can be huge, suitable model minimisation techniques are crucial for efficient model checking. An effective minimisation method for the recent notion of spatial Compatible Path (CoPa)-bisimilarity is proposed, and shown to be correct. The core of our method is the encoding of Closure Models as Labelled Transition Systems, enabling minimisation algorithms for branching bisimulation to compute CoPa equivalence classes. Initial validation via benchmark examples demonstrates a promising speed-up in model checking of spatial properties for models of realistic size.

Source: FM'23 - 25th International Symposium on Formal Methods, pp. 263–281, Luebeck, Germany, 6-10/03/2023

Metrics