An experimental spatio-temporal model checker

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

Modal Logics  Model Checking  Software/Program Verification  Simulation  Closure Spaces  Mathematical Logic 

In this work we present a spatial extension of the global model checking algorithm of the temporal logic CTL. This classical veri- fication framework is augmented with ideas coming from the tradition of topological spatial logics. More precisely, we add to CTL the operators of the Spatial Logic of Closure Spaces, including the surrounded operator, with its intended meaning of a point being surrounded by entities sat- isfying a specific property. The interplay of space and time permits one to define complex spatio-temporal properties. The model checking algo- rithm that we propose features no particular efficiency optimisations, as it is meant to be a reference specification of a family of more efficient algorithms that are planned for future work. Its complexity depends on the product of temporal states and points of the space. Nevertheless, a prototype model checker has been implemented, made available, and used for experimentation of the application of spatio-temporal verifica- tion in the field of collective adaptive systems.

Source: Software Engineering and Formal Methods, edited by Domenico Bianculli, Radu Calinescu, Bernhard Rumpe, pp. 297–311, 2015

Metrics