Spatial logic and spatial model checking for closure spaces

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

Modal Logics  Model Checking  Closure Spaces  Topological Spaces 

Spatial aspects of computation are increasingly relevant in Computer Science, especially in the field of collective adaptive systems and when dealing with systems distributed in physical space. Traditional formal verification techniques are well suited to analyse the temporal evolution of concurrent systems; however, properties of space are typically not explicitly taken into account. This tutorial provides an introduction to recent work on a topology-inspired approach to formal verification of spatial properties depending upon (physical) space. A logic is presented, stemming from the tradition of topological interpretations of modal logics, dating back to earlier logicians such as Tarski, where modalities describe neighbourhood. These topological definitions are lifted to the more general setting of closure spaces, also encompassing discrete, graph-based structures. The present tutorial illustrates the extension of the framework with a spatial surrounded operator, leading to the spatial logic for closure spaces SLCS, and its combination with the temporal logic CTL, leading to STLCS. The interplay of space and time permits one to define complex spatio-temporal properties. Both for the spatial and the spatio-temporal fragment efficient model-checking algorithms have been developed and their use on a number of case studies and examples is illustrated.

Source: Formal Methods for the Quantitative Evaluation of Collective Adaptive Systems, edited by Bernardo M., De Nicola R., Hillston J., pp. 156–201, 2016

Metrics