Dynamic relational mereotopology: Logics for stable and unstable relations

Vladislav Nenchev

doi:10.12775/LLP.2013.014

Authors

Vladislav Nenchev Sofia University “St. Kl. Ohridski”

DOI:

https://doi.org/10.12775/LLP.2013.014

Keywords

stable and unstable relations, mereology, mereotopology, representation theory, hereditary undecidability, quantifier-free fragment

Abstract

In this paper we present stable and unstable versions of several well-known relations from mereotopology: part-of, overlap, underlap and contact. An intuitive semantics is given for the stable and unstable relations, describing them as dynamic counterparts of the base mereotopo-logical relations. Stable relations are described as ones that always hold, while unstable relations hold sometimes. A set of first-order sentences is provided to serve as axioms for the stable and unstable relations, and representation theory is developed in similar fashion to Stone’s representation theory for Boolean algebras and distributive lattices. Then we present some results about the first-order predicate logic of these relations and about its quantifier-free fragment. Completeness theorems for these logics are proved, the full first-order theory is proved to be hereditary undecidable and the satisfiability problem of the quantifier-free fragment is proved to be NP-complete.

Author Biography

Vladislav Nenchev, Sofia University “St. Kl. Ohridski”

Department of Mathematical Logic and ApplicationsFaculty of Mathematics and Informatics

References

Balbes, R., and P. Dwinger, Distributive Lattices, University of Missouri Press, 1974.

Balbiani, P., T. Tinchev, and D. Vakarelov, “Modal logics for region-based theory of space”, Fundamenta Informaticae, 81 (2007), 1–3: 29–82.

de Laguna, T., “Point, line and surface as sets of solids” The Journal of Philosophy, 19 (1922), 17: 449–461.

Dimov, G., and D. Vakarelov, “Contact algebras and region-based theory of space. A proximity approach. I and II”, Fundamenta Informaticae, 74 (2006), 2–3: 209–249, 251–282.

Düntsch, I., and M. Winter, “A representation theorem for Boolean contact algebras”, Theoretical Computer Science (B), 347 (2005), 3: 498–512. CrossRef

Egenhofer, M., and R. Franzosa, “Point-set topological spatial relations”, International Journal of Geographical Information Systems, 5 (1991), 2: 161–174. CrossRef

Ershov, Y. L., Problems of Decidability and Constructive Models (in Russian), Science, Moskow, 1980.

Finger, M., and D.M. Gabbay, “Adding a temporal dimension to a logic system”, Journal of Logic, Language and Information, 1 (1992), 3: 203–233.

Jonsson, P., and T. Drakengren, “A complete classification of tractability in the spatial theory RCC-5”, Journal of Artificial Intelligence Research, 6 (1997): 211–221.

Kontchakov, R., A. Kurucz, F. Wolter, and M. Zakharyaschev, “Spatial logic + temporal logic = ?”, in M. Aiello, I. Pratt-Hartmann, and J. van Benthem (eds.), Handbook of Spatial Logics, chapter 9, Springer, 2007, pp. 497–564.

Lutz, C., and F. Wolter, “Modal logics for topological relations”, Logical Methods in Computer Science 2, 2–5 (2006): 1–41.

Nenchev, V., “Logics for stable and unstable mereological relations”, Central European Journal of Mathematics, 9 (2011), 6: 1354–1379. CrossReff; WoS

Nenchev, V., “Undecidability of logics for mereological and mereotopological relations”, in Proceedings of 8-thPanhellenic Logic Symposium, Ioannina, Greece, July 2011.

Nenov, Y., and D. Vakarelov, “Modal logics for mereotopological relations”, in C. Areces and R. Goldblatt (eds.), Advances in Modal Logic, Nancy, France, September 2008, pp. 249–272.

Pratt-Hartmann, I., “First-order mereotopology”, in M. Aiello, I. Pratt-Hartmann and J. van Benthem (eds.), Handbook of Spatial Logics, chapter 2, Springer, 2007, pp. 13–97.

Randell, D.A., Zhan Cui, and A.G. Cohn, “A spatial logic based on regions and connection”, in B. Nebel, C. Rich, and W.R. Swartout (eds.), Proceedings of 3rdInternational Conference Knowledge Representation and Reasoning, Cambridge, Massachusetts, USA, October 1992, Morgan Kaufmann, pp. 165–176.

Simons, P., Parts: A Study in Ontology, Oxford University Press, 1987.

Stell, J.G., “Boolean connection algebras: A new approach to the region connection calculus”, Artificial Intelligence, 122 (2000), 1–2: 111–136. CrossRef

Vakarelov, D., “Logical analysis of positive and negative similarity relations in property systems”, in M. De Glas and D. Gabbay (eds), Proceedings of 1-stWorld Conference on the Fundamentals of Artificial Intelligence, Paris, France, July 1991, pp. 491–499.

Vakarelov, D., “A modal logic for set relations”, in Proceedings of 10-th International Congress of Logic, Methodology and Philosophy of Science, Abstracts, Florence, Italy, August 1995, p. 183.

Vakarelov, D., “Region-based theory of space: Algebras of regions, representation theory and logics”, in D.M. Gabbay, M. Zakharyaschev, and S.S. Goncharov (eds.), Mathematical Problems from Applied Logics II. Logics for the XXIst Century, Springer, 2007, pp. 267–348.

Vakarelov, D., “A modal approach to dynamic ontology: modal mereotopology”, Logic and Logical Philosophy, 17 (2008): 167–187.

Vakarelov, D., “Dynamic mereotopology: A point-free theory of changing regions. I. Stable and unstable mereotopological relations”, Fundamenta Informaticae, 100 (2010), 1–4: 159–180. WoS

Whitehead, A.N., Process and Reality, New York: MacMillan, 1929.

Wolter. F., and M. Zakharyaschev, “Spatio-temporal representation and reasoning based on RCC-8”, in A.G. Cohn, F. Giunchiglia, and B. Selman (eds.), Proceedings of the 7thConference on Principles of Knowledge Representation and Reasoning, Breckenridge, Colorado, USA, April 2000, Morgan Kaufmann, pp. 3–14.