Skip to main content Skip to main navigation menu Skip to site footer
  • Register
  • Login
  • Language
    • English
    • Język Polski
  • Menu
  • Home
  • Current
  • Archives
  • Online First Articles
  • About
    • About the Journal
    • Submissions
    • Editorial Team
    • Advisory Board
    • Peer Review Process
    • Logic and Logical Philosophy Committee
    • Open Access Policy
    • Privacy Statement
    • Contact
  • Register
  • Login
  • Language:
  • English
  • Język Polski

Logic and Logical Philosophy

Dynamic relational mereotopology: Logics for stable and unstable relations
  • Home
  • /
  • Dynamic relational mereotopology: Logics for stable and unstable relations
  1. Home /
  2. Archives /
  3. Vol. 22 No. 3 (2013): September /
  4. Articles

Dynamic relational mereotopology: Logics for stable and unstable relations

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.

Logic and Logical Philosophy

Downloads

  • PDF

Published

2013-06-11

How to Cite

1.
NENCHEV, Vladislav. Dynamic relational mereotopology: Logics for stable and unstable relations. Logic and Logical Philosophy [online]. 11 June 2013, T. 22, nr 3, s. 295–325. [accessed 25.3.2023]. DOI 10.12775/LLP.2013.014.
  • PN-ISO 690 (Polish)
  • ACM
  • ACS
  • APA
  • ABNT
  • Chicago
  • Harvard
  • IEEE
  • MLA
  • Turabian
  • Vancouver
Download Citation
  • Endnote/Zotero/Mendeley (RIS)
  • BibTeX

Issue

Vol. 22 No. 3 (2013): September

Section

Articles

Stats

Number of views and downloads: 204
Number of citations: 2

Crossref
Scopus
Google Scholar
Europe PMC

Search

Search

Browse

  • Browse Author Index
  • Issue archive

User

User

Current Issue

  • Atom logo
  • RSS2 logo
  • RSS1 logo

Information

  • For Readers
  • For Authors
  • For Librarians

Newsletter

Subscribe Unsubscribe

Language

  • English
  • Język Polski

Tags

Search using one of provided tags:

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

Akademicka Platforma Czasopism

Najlepsze czasopisma naukowe i akademickie w jednym miejscu

apcz.umk.pl

Partners

  • Akademia Ignatianum w Krakowie
  • Akademickie Towarzystwo Andragogiczne
  • Fundacja Copernicus na rzecz Rozwoju Badań Naukowych
  • Instytut Historii im. Tadeusza Manteuffla Polskiej Akademii Nauk
  • Instytut Kultur Śródziemnomorskich i Orientalnych PAN
  • Karmelitański Instytut Duchowości w Krakowie
  • Państwowa Akademia Nauk Stosowanych w Krośnie
  • Państwowa Akademia Nauk Stosowanych we Włocławku
  • Państwowa Wyższa Szkoła Zawodowa im. Stanisława Pigonia w Krośnie
  • Polskie Towarzystwo Ekonomiczne
  • Polskie Towarzystwo Ludoznawcze
  • Towarzystwo Miłośników Torunia
  • Towarzystwo Naukowe w Toruniu
  • Uniwersytet im. Adama Mickiewicza w Poznaniu
  • Uniwersytet Mikołaja Kopernika
  • Uniwersytet w Białymstoku
  • Uniwersytet Warszawski
  • Wojewódzka Biblioteka Publiczna - Książnica Kopernikańska
  • Wyższe Seminarium Duchowne w Pelplinie / Wydawnictwo Diecezjalne „Bernardinum" w Pelplinie

© 2021- Nicolaus Copernicus University Accessibility statement Shop