The universal tangle for spatial reasoning

DOI10.1007/978-3-031-43619-2_55MaRDI QIDQ6432366zbMATH OpenFDO

Authors David Fernández-Duque, Konstantinos Papafilippou

Publication date 6 April 2023

Full work available at URL https://doi.org/10.1007/978-3-031-43619-2_55

Mathematics Subject Classification ID

Logic in artificial intelligence (68T27)

Abstract: The topological $mu$-calculus has gathered attention in recent years as a powerful framework for representation of spatial knowledge. In particular, spatial relations can be represented over finite structures in the guise of weakly transitive (wK4) frames. In this paper we show that the topological $mu$-calculus is equivalent to a simple fragment based on a variant of the "tangle" operator. Similar results were proven for more restricted classes of frames by Anuj Dawar and Martin Otto, using modal characterisation theorems for the corresponding classes of frames. However, since the $mu$-calculus is not equivalent to the bisimulation invariant fragment of FOL or of MSO over wK4 frames, we use a different method to prove our results; namely, the notion of finality which was also employed in the proof of completeness and FMP of the $mu$-calculus over wK4 frames. As a corollary we obtain a new proof of an existing result showing the collapse of the alternation hierarchy over wK4 frames.

Recommendations

• Spatial logic of tangled closure operators and modal mu-calculus
• Qualitative spatial reasoning with topological information
• Succinctness in subsystems of the spatial -calculus

Cited in

(1)

• Exponential lower bounds on definable fixed points

This page was built for publication: The universal tangle for spatial reasoning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6432366)