Dynamic relational mereotopology: Logics for stable and unstable relations

• Authors: Vladislav Nenchev
• Languages of publication: EN

Abstracts

EN

In this paper we present stable and unstable versions of sev- eral 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.

Keywords

EN

stable and unstable relations; mereology; mereotopology; repre- sentation theory; hereditary undecidability; quantifier-free fragment

• Publisher: Uniwersytet Mikołaja Kopernika (Nicolaus Copernicus University in Toruń)
• Journal: Logic and Logical Philosophy
• Year: 2013
• Volume: 22
• Issue: 3
• Pages: 295-325

Dates

published

2013-09-01

online

2013-07-02

Contributors

author

Vladislav Nenchev

• Department of Mathematical Logic and Applications Faculty of Mathematics and Informatics Sofia University “St. Kl. Ohridski” 5 James Bourchier blvd. Sofia, 1164, Bulgaria

References

• [1] Balbes, R., and P. Dwinger, Distributive Lattices, University of Missouri Press, 1974.
• [2] Balbiani, P., T. Tinchev, and D. Vakarelov, “Modal logics for region-based theory of space”, Fundamenta Informaticae, 81 (2007), 1-3: 29-82.
• [3] de Laguna, T., “Point, line and surface as sets of solids” The Journal ofPhilosophy, 19 (1922), 17: 449-461.
• [4] 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.
• [5] Düntsch, I., and M. Winter, “A representation theorem for Boolean contact algebras”, Theoretical Computer Science (B), 347 (2005), 3: 498-512.[Crossref]
• [6] Egenhofer, M., and R. Franzosa, “Point-set topological spatial relations”, International Journal of Geographical Information Systems, 5 (1991), 2: 161-174.[Crossref]
• [7] Ershov, Y. L., Problems of Decidability and Constructive Models (in Russian), Science, Moskow, 1980.
• [8] 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.
• [9] 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.
• [10] 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.
• [11] Lutz, C., and F. Wolter, “Modal logics for topological relations”, LogicalMethods in Computer Science 2, 2-5 (2006): 1-41.
• [12] Nenchev, V., “Logics for stable and unstable mereological relations”, Central European Journal of Mathematics, 9 (2011), 6: 1354-1379.[WoS][Crossref]
• [13] Nenchev, V., “Undecidability of logics for mereological and mereotopological relations”, in Proceedings of 8-th Panhellenic Logic Symposium, Ioannina, Greece, July 2011.
• [14] 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.
• [15] 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.
• [16] 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 3rd International Conference Knowledge Representationand Reasoning, Cambridge, Massachusetts, USA, October 1992, Morgan Kaufmann, pp. 165-176.
• [17] Simons, P., Parts: A Study in Ontology, Oxford University Press, 1987.
• [18] Stell, J.G., “Boolean connection algebras: A new approach to the region connection calculus”, Artificial Intelligence, 122 (2000), 1-2: 111-136.[Crossref]
• [19] Vakarelov, D., “Logical analysis of positive and negative similarity relations in property systems”, in M. De Glas and D. Gabbay (eds), Proceed-ings of 1-st World Conference on the Fundamentals of Artificial Intelli-gence, Paris, France, July 1991, pp. 491-499.
• [20] Vakarelov, D., “A modal logic for set relations”, in Proceedings of 10-thInternational Congress of Logic, Methodology and Philosophy of Science,Abstracts, Florence, Italy, August 1995, p. 183.
• [21] 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.
• [22] Vakarelov, D., “A modal approach to dynamic ontology: modal mereotopology”, Logic and Logical Philosophy, 17 (2008): 167-187.
• [23] Vakarelov, D., “Dynamic mereotopology: A point-free theory of changing regions. I. Stable and unstable mereotopological relations”, FundamentaInformaticae, 100 (2010), 1-4: 159-180.[WoS]
• [24] Whitehead, A.N., Process and Reality, New York: MacMillan, 1929.
• [25] 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 7th Conference on Principles of KnowledgeRepresentation and Reasoning, Breckenridge, Colorado, USA, April 2000, Morgan Kaufmann, pp. 3-14.

Identifiers

DOI

10.12775/LLP.2013.014