A New Perspective on the Mereotopology of RCC8

Authors Michael Grüninger, Bahar Aameri



PDF
Thumbnail PDF

File

LIPIcs.COSIT.2017.2.pdf
  • Filesize: 0.58 MB
  • 13 pages

Document Identifiers

Author Details

Michael Grüninger
Bahar Aameri

Cite AsGet BibTex

Michael Grüninger and Bahar Aameri. A New Perspective on the Mereotopology of RCC8. In 13th International Conference on Spatial Information Theory (COSIT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 86, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.COSIT.2017.2

Abstract

RCC8 is a set of eight jointly exhaustive and pairwise disjoint binary relations representing mereotopological relationships between ordered pairs of individuals. Although the RCC8 relations were originally presented as defined relations of Region Connection Calculus (RCC), virtually all implementations use the RCC8 Composition Table (CT) rather than the axioms of RCC. This raises the question of which mereotopology actually underlies the RCC8 composition table. In this paper, we characterize the algebraic and mereotopological properties of the RCC8 CT based on the metalogical relationship between the first-order theory that captures the RCC8 CT and Ground Mereotopology (MT) of Casati and Varzi. In particular, we show that the RCC8 theory and MT are relatively interpretable in each other. We further show that a nonconservative extension of the RCC8 theory that captures the intended interpretation of the RCC8 relations is logically synonymous with MT, and that a conservative extension of MT is logically synonymous with the RCC8 theory. We also present a characterization of models of MT up to isomorphism, and explain how such a characterization provides insights for understanding models of the RCC8 theory.
Keywords
  • RCC8
  • mereotopology
  • spatial reasoning
  • ontologies

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. N. Asher and L. Vieu. Toward a geometry of common sense: A semantics and a complete axiomatization of mereotopology. In IJCAI, pages 846-852, 1995. Google Scholar
  2. B. Bennett, A. Isli, and A. G. Cohn. When does a composition table provide a complete and tractable proof procedure for a relational constraint language? In Proceedings of the IJCAI-97 workshop on Spatial and Temporal Reasoning, 1997. Google Scholar
  3. D. J. Bergstrand and K. F. Jones. On upper bound graphs of partially ordered sets. Congression Numerica, 66:185-193, 1988. Google Scholar
  4. R. Casati and A. C. Varzi. Parts and places: The structures of spatial representation. MIT Press, 1999. Google Scholar
  5. I. Düntsch and M. Winter. A representation theorem for boolean contact algebras. Theoretical Computer Science, 347(3):498-512, 2005. Google Scholar
  6. B. Dushnik and E. W. Miller. Partially ordered sets. American Journal of Mathematics, 63:600-610, 1941. Google Scholar
  7. H. Enderton. Mathematical Introduction to Logic. Academic Press, 1972. Google Scholar
  8. C. Eschenbach. Viewing composition tables as axiomatic systems. In Proc. of the Conference on Formal Ontology in Information Systems, pages 93-104. ACM, 2001. Google Scholar
  9. N. M. Gotts. An axiomatic approach to topology for spatial information systems. Research Report Series-University of Leeds School of Computer Studies, 1996. Google Scholar
  10. M. Gruninger, T. Hahmann, A. Hashemi, D. Ong, and A. Ozgovde. Modular first-order ontologies via repositories. Applied Ontology, 7(2):169-209, 2012. Google Scholar
  11. W. Hodges. Model theory. Cambridge University Press Cambridge, 1993. Google Scholar
  12. J. R. Lundgren and J. S. Maybee. A characterization of upper bound graphs. Congression Numerica, 40:189-193, 1983. Google Scholar
  13. W. McCune. Prover9 and mace4. http://www.cs.unm.edu/~mccune/prover9/, 2010.
  14. F. R. McMorris and T. Zaslavsky. Bound graphs of a partially ordered set. Journal of Combinatorics and Information Systems Science, 7:134-138, 1982. Google Scholar
  15. Charles Pinter. Properties preserved under definitional equivalence and interpretations. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 24:481-488, 1978. Google Scholar
  16. A. Pnueli, A. Lempel, and Even S. Transitive orientations of graphs and identification of permutation graphs. Canadian Journal of Mathematics, 23:160-175, 1971. Google Scholar
  17. D. A. Randell, Z. Cui, and A. Cohn. A spatial logic based on regions and connection. In Proceedings of the KR92, pages 165-176. Morgan Kaufmann, 1992. Google Scholar
  18. J. G. Stell. Boolean Connection Algebras: A New Approach to the Region-Connection Calculus. Artificial Intelligence, 122:111-136, 1999. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail