Home > Research > Publications & Outputs > Finite Models for a Spatial Logic with Discrete...

Links

Text available via DOI:

View graph of relations

Finite Models for a Spatial Logic with Discrete and Topological Path Operators

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNConference contribution/Paperpeer-review

Published
Publication date18/08/2021
Host publication46th International Symposium on Mathematical Foundations of Computer Science
EditorsFilippo Bonchi, Simon J. Puglisi
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages72:1-72:16
Number of pages16
Volume202
ISBN (electronic)9783959772013
<mark>Original language</mark>English

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume202
ISSN (Print)1868-8969

Abstract

This paper analyses models of a spatial logic with path operators based on the class of neighbourhood spaces, also called pretopological or closure spaces, a generalisation of topological spaces. For this purpose, we distinguish two dimensions: the type of spaces on which models are built, and the type of allowed paths. For the spaces, we investigate general neighbourhood spaces and the subclass of quasi-discrete spaces, which closely resemble graphs. For the paths, we analyse the cases of quasi-discrete paths, which consist of an enumeration of points, and topological paths, based on the unit interval. We show that the logic admits finite models over quasi-discrete spaces, both with quasi-discrete and topological paths. Finally, we prove that for general neighbourhood spaces, the logic does not have the finite model property, either for quasi-discrete or topological paths.