Logics for stable and unstable mereological relations

Vladislav Nenchev

Open Mathematics (2011)

  • Volume: 9, Issue: 6, page 1354-1379
  • ISSN: 2391-5455

Abstract

top
In this paper we present logics about stable and unstable versions of several well-known relations from mereology: part-of, overlap and underlap. An intuitive semantics is given for the stable and unstable relations, describing them as dynamic counterparts of the base mereological 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 distributive lattices. First-order predicate logic and modal logic are presented with semantics based on structures with stable and unstable mereological relations. Completeness theorems for these logics are proved, as well as decidability in the case of the modal logic, hereditary undecidability in the case of the first-order logic, and NP-completeness for the satisfiability problem of the quantifier-free fragment of the first-order logic.

How to cite

top

Vladislav Nenchev. "Logics for stable and unstable mereological relations." Open Mathematics 9.6 (2011): 1354-1379. <http://eudml.org/doc/269055>.

@article{VladislavNenchev2011,
abstract = {In this paper we present logics about stable and unstable versions of several well-known relations from mereology: part-of, overlap and underlap. An intuitive semantics is given for the stable and unstable relations, describing them as dynamic counterparts of the base mereological 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 distributive lattices. First-order predicate logic and modal logic are presented with semantics based on structures with stable and unstable mereological relations. Completeness theorems for these logics are proved, as well as decidability in the case of the modal logic, hereditary undecidability in the case of the first-order logic, and NP-completeness for the satisfiability problem of the quantifier-free fragment of the first-order logic.},
author = {Vladislav Nenchev},
journal = {Open Mathematics},
keywords = {Stable and unstable relations; Mereology; Representation theory; First-order logic; Hereditary undecidability; Quantifier-free fragment; Modal logic; stable relation; unstable relation; mereology; representation theory; first-order logic; hereditary undecidability; quantifier-free fragment; modal logic},
language = {eng},
number = {6},
pages = {1354-1379},
title = {Logics for stable and unstable mereological relations},
url = {http://eudml.org/doc/269055},
volume = {9},
year = {2011},
}

TY - JOUR
AU - Vladislav Nenchev
TI - Logics for stable and unstable mereological relations
JO - Open Mathematics
PY - 2011
VL - 9
IS - 6
SP - 1354
EP - 1379
AB - In this paper we present logics about stable and unstable versions of several well-known relations from mereology: part-of, overlap and underlap. An intuitive semantics is given for the stable and unstable relations, describing them as dynamic counterparts of the base mereological 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 distributive lattices. First-order predicate logic and modal logic are presented with semantics based on structures with stable and unstable mereological relations. Completeness theorems for these logics are proved, as well as decidability in the case of the modal logic, hereditary undecidability in the case of the first-order logic, and NP-completeness for the satisfiability problem of the quantifier-free fragment of the first-order logic.
LA - eng
KW - Stable and unstable relations; Mereology; Representation theory; First-order logic; Hereditary undecidability; Quantifier-free fragment; Modal logic; stable relation; unstable relation; mereology; representation theory; first-order logic; hereditary undecidability; quantifier-free fragment; modal logic
UR - http://eudml.org/doc/269055
ER -

References

top
  1. [1] Balbes R., Dwinger Ph., Distributive Lattices, University of Missouri Press, Columbia, 1974 Zbl0321.06012
  2. [2] Balbiani Ph., Tinchev T., Vakarelov D., Modal logics for region-based theory of space, Fund. Inform., 2007, 81(1–3), 29–82 Zbl1142.03012
  3. [3] Blackburn P., de Rijke M., Venema Y., Modal Logic, Cambridge Tracts Theoret. Comput. Sci., 53, Cambridge University Press, Cambridge, 2001 Zbl0988.03006
  4. [4] Chagrov A., Zakharyaschev M., Modal Logic, Oxford Logic Guides, Oxford University Press, New York, 1997 
  5. [5] Egenhofer M.J., Franzosa R., Point-set topological spatial relations, International Journal of Geographic Information Systems, 1991, 5(2), 161–174 http://dx.doi.org/10.1080/02693799108927841 
  6. [6] Ershov Yu.L., Problems of Decidability and Constructive Models, Nauka, Moscow, 1980 (in Russian) 
  7. [7] Fine K., Essence and modality, Philosophical Perspectives, 1994, 8, 1–16 http://dx.doi.org/10.2307/2214160 
  8. [8] Finger M., Gabbay D.M., Adding a temporal dimension to a logic system, J. Logic Lang. Inform., 1992, 1(3), 203–233 http://dx.doi.org/10.1007/BF00156915 Zbl0798.03031
  9. [9] Jonsson P., Drakengren T., A complete classification of tractability in RCC-5, J. Artificial Intelligence Res., 1997, 6, 211–221 Zbl0894.68096
  10. [10] Kontchakov R., Kurucz A., Wolter F., Zakharyaschev M., Spatial logic + temporal logic = ?, In: Handbook of Spatial Logics, Springer, Dordrecht, 2007, 497–564 http://dx.doi.org/10.1007/978-1-4020-5587-4_9 
  11. [11] de Laguna T., Point, line, and surface, as sets of solids, J. Philos., 1922, 19(17), 449–461 http://dx.doi.org/10.2307/2939504 
  12. [12] Lutz C., Wolter F., Modal logics of topological relations, Log. Methods Comput. Sci., 2006, 2(2), #5 Zbl1126.03026
  13. [13] Nenchev V., Vakarelov D., An axiomatization of dynamic ontology of stable and unstable mereological relations, In: 7th Panhellenic Logic Symposium, Patras, July 15–19, 2009, 137–141 
  14. [14] Nenov Y., Vakarelov D., Modal Llogics for mereotopological relations, In: Advances in Modal Logic, 7, Nancy, September 9–12, 2008, College Publications, London, 2008, 249–272 Zbl1244.03069
  15. [15] Randell D.A., Cui Z., Cohn A.G., A spatial logic based on regions and connection, In: 3rd International Conference on Knowledge Representation and Reasoning, 1992, Morgan Kaufmann, 1992, 165–176 
  16. [16] Segerberg K., An Essay in Classical Modal Logic, Filosofiska Studier, 13, Filosofiska Föreningen och Filosofiska Institutionen vid Uppsala Universitet, Uppsala, 1971 Zbl0311.02028
  17. [17] Simons P., Parts. A Study in Ontology, Clarendon Press, Oxford, 1987 
  18. [18] Vakarelov D., Logical analysis of positive and negative similarity relations in property systems, In: 1st World Conference on the Fundamentals of Artificial Intelligence, Paris, July 1–5, 1991, 491–499 
  19. [19] Vakarelov D., A modal logic for set relations, In: 10th International Congress of Logic, Methodology and Philosophy of Science, Florence, August 19–25, 1995, 183 
  20. [20] Vakarelov D., A modal approach to dynamic ontology: modal mereotopology, Logic Log. Philos., 2008, 17(1–2), 163–183 Zbl1156.03028
  21. [21] Vakarelov D., Dynamic mereotopology: a point-free theory of changing regions. I. Stable and unstable mereotopological relations, Fund. Inform., 2010, 100, 159–180 Zbl1225.03027
  22. [22] Whitehead A.N., Process and Reality, Cambridge University Press, Cambridge, 1929 
  23. [23] Wolter F., Zakharyaschev M., Spatio-temporal representation and reasoning based on RCC-8, In: 7th International Conference on Knowledge Representation and Reasoning, 2000, Morgan Kaufmann, 2000, 3–14 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.