Spatial logics with connectedness predicates

Roman Kontchakov; Ian Pratt-Hartmann; Frank Wolter; Michael Zakharyaschev

doi:10.2168/LMCS-6(3:7)2010

Roman Kontchakov ; Ian Pratt-Hartmann ; Frank Wolter ; Michael Zakharyaschev - Spatial logics with connectedness predicates

lmcs:1229 - Logical Methods in Computer Science, August 18, 2010, Volume 6, Issue 3 - https://doi.org/10.2168/LMCS-6(3:7)2010

Spatial logics with connectedness predicatesArticle

Authors: Roman Kontchakov ; Ian Pratt-Hartmann ; Frank Wolter ; Michael Zakharyaschev

We consider quantifier-free spatial logics, designed for qualitative spatial representation and reasoning in AI, and extend them with the means to represent topological connectedness of regions and restrict the number of their connected components. We investigate the computational complexity of these logics and show that the connectedness constraints can increase complexity from NP to PSpace, ExpTime and, if component counting is allowed, to NExpTime.

Comment: Some results of the paper were presented at LPAR 2008 and ECAI 2000

https://doi.org/10.2168/LMCS-6(3:7)2010

Source: arXiv.org:1003.5399

Volume: Volume 6, Issue 3

Published on: August 18, 2010

Imported on: June 17, 2009

Keywords: Computer Science - Logic in Computer Science, F.4.1, I.2.4

Licence: arXiv.org - Non-exclusive license to distribute

Classifications

Mathematics Subject Classification 2020¹

Sources:

[1] zbMATH Open.

Bibliographic References

13 Documents citing this article

Bongjae Kwon;Kiyun Yu, 2025, FGB-OPRAm: integrating fuzzy granular-ball and OPRAm for spatial query answering in uncertain environments, Geo-spatial Information Science, pp. 1-20, 10.1080/10095020.2025.2522144, https://doi.org/10.1080/10095020.2025.2522144.

Zafer Özdemir, 2023, Tableaux approach for contact logics interpreted over intervals, Reports on Mathematical Logic, 58, pp. 3-13, 10.4467/20842589rm.23.001.18800, https://doi.org/10.4467/20842589rm.23.001.18800.

Philippe Balbiani;Tatyana Ivanova, 2020, Relational Representation Theorems for Extended Contact Algebras, arXiv (Cornell University), 109, 4, pp. 701-723, 10.1007/s11225-020-09923-0, http://arxiv.org/abs/1901.10367.

Philippe Balbiani;Çiğdem Gencer, 2020, Contact Logic is Finitary for Unification with Constants, Logic in Asia: Studia logica library, pp. 85-104, 10.1007/978-981-15-1342-8_4.

Tengfei Li;Jing Liu;JieXiang Kang;Haiying Sun;Xiaohong Chen;Li Han, 2020, Model Checking of Spatial Logic, 2020 27th Asia-Pacific Software Engineering Conference (APSEC), pp. 169-177, 10.1109/apsec51365.2020.00025.

Tatyana Ivanova, 2019, Extended Contact Algebras and Internal Connectedness, Studia Logica, 108, 2, pp. 239-254, 10.1007/s11225-019-09845-6.

Philippe Balbiani;Çiğdem Gencer;Zafer Özdemir, 2018, Two decision problems in Contact Logics, 27, 1, pp. 8-32, 10.1093/jigpal/jzy016, https://hal.science/hal-02378372.

Frank Dylla;Jae Hee Lee;Till Mossakowski;Thomas Schneider;André Van Delden;et al., 2017, A Survey of Qualitative Spatial and Temporal Calculi, ACM Computing Surveys, 50, 1, pp. 1-39, 10.1145/3038927.

Philippe Balbiani;Çiğdem Gencer, 2017, Finitariness of Elementary Unification in Boolean Region Connection Calculus, pp. 281-297, 10.1007/978-3-319-66167-4_16, https://hal.science/hal-01650175.

Nick Bezhanishvili;Wiebe van der Hoek, 2014, Structures for Epistemic Logic, UvA-DARE (University of Amsterdam), pp. 339-380, 10.1007/978-3-319-06025-5_12, https://handle.uba.uva.nl/personal/pure/en/publications/structures-for-epistemic-logic(8a7a48fa-14d1-4646-8a6f-45094516a04c).html.

Frank Dylla;Till Mossakowski;Thomas Schneider;Diedrich Wolter, 2013, Algebraic Properties of Qualitative Spatio-temporal Calculi, Lecture notes in computer science, pp. 516-536, 10.1007/978-3-319-01790-7_28.

Ian Pratt-Hartmann, 2013, Twenty Years of Topological Logic, Lecture notes in geoinformation and cartography, pp. 217-235, 10.1007/978-3-642-34359-9_12.

Roman Kontchakov;Yavor Nenov;Ian Pratt-Hartmann;Michael Zakharyaschev, 2013, Topological Logics with Connectedness over Euclidean Spaces, arXiv (Cornell University), 14, 2, pp. 1-48, 10.1145/2480759.2480765, http://arxiv.org/abs/1110.4034.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 3233 times.

This article's PDF has been downloaded 1013 times.