Minimisation of spatial models using branching bisimilarity (extended version)

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 poten- tial 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 an- other 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 La- belled 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. Detailed proofs of all results are provided.

Source: ISTI Technical Report, ISTI-2022-TR/027, 2022

Metrics