Model checking spatial logics for closure spaces. Extended version

Ciancia V., Latella D., Loreti M., Massink M.

Model logics  Spatial logics  Specifying and verifying and reasoning about programs 

Spatial aspects of computation are becoming increasingly relevant in Computer Science, es- pecially in the eld of collective adaptive systems and when dealing with systems distributed in physical space. Traditional formal verication techniques are well suited to analyse the temporal evolution of programs; however, properties of space are typically not taken into account explic- itly. We present a topology-based approach to formal verication of spatial properties depending upon physical space. We dene an appropriate logic, stemming from the tradition of topological interpretations of modal logics, dating back to earlier logicians such as Tarski, where modalities describe neighbourhood. We lift the topological denitions to the more general setting of closure spaces, also encompassing discrete, graph-based structures. We extend the framework with a spa- tial surrounded operator, a propagation operator and with some collective operators. The latter are interpreted over arbitrary sets of points instead of individual points in space. We dene ecient model checking procedures, both for the individual and the collective spatial fragments of the logic and provide a proof-of-concept tool.

Source: ISTI Technical reports, 2016