Document Open Access Logo

A Modal Logic for Subject-Oriented Spatial Reasoning

Authors Przemysław Andrzej Wałęga, Michał Zawidzki

PDF
Thumbnail PDF

File

LIPIcs.TIME.2019.4.pdf
  • Filesize: 1.12 MB
  • 22 pages

Document Identifiers

Author Details

Przemysław Andrzej Wałęga
  • University of Oxford, Department of Computer Science, United Kingdom
  • University of Warsaw, Institute of Philosophy, Poland
Michał Zawidzki
  • University of Łódź, Department of Logic, Poland

Funding

  • Wałęga, Przemysław Andrzej: the SIRIUS Centre for Scalable Data Access, the EPSRC projects DBOnto, AnaLOG, and ED^3; and the Foundation for Polish Science (FNP).
  • Zawidzki, Michał: the NCN grant DEC-2011/02/A/HS1/00395.

Cite AsGet BibTex

Przemysław Andrzej Wałęga and Michał Zawidzki. A Modal Logic for Subject-Oriented Spatial Reasoning. In 26th International Symposium on Temporal Representation and Reasoning (TIME 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 147, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.TIME.2019.4

Abstract

We present a modal logic for representing and reasoning about space seen from the subject’s perspective. The language of our logic comprises modal operators for the relations "in front", "behind", "to the left", and "to the right" of the subject, which introduce the intrinsic frame of reference; and operators for "behind an object", "between the subject and an object", "to the left of an object", and "to the right of an object", employing the relative frame of reference. The language allows us to express nominals, hybrid operators, and a restricted form of distance operators which, as we demonstrate by example, makes the logic interesting for potential applications. We prove that the satisfiability problem in the logic is decidable and in particular PSpace-complete.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity theory and logic
  • Theory of computation → Modal and temporal logics
  • Theory of computation → Automata over infinite objects
  • Theory of computation → Verification by model checking
Keywords
  • spatial logic
  • modal logic
  • subject-oriented
  • computational complexity

Metrics

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

References

  1. Marco Aiello and Johan Van Benthem. A modalwalk through space. Journal of Applied Non-Classical Logics, 12(3-4):319-363, 2002. Google Scholar
  2. Carlos Areces, Patrick Blackburn, and Maarten Marx. The computational complexity of hybrid temporal logics. Logic Journal of IGPL, 8(5):653-679, 2000. Google Scholar
  3. Alessandro Artale, Roman Kontchakov, Vladislav Ryzhikov, and Michael Zakharyaschev. The Complexity of Clausal Fragments of LTL. In Ken McMillan, Aart Middeldorp, and Andrei Voronkov, editors, Logic for Programming, Artificial Intelligence, and Reasoning: 19th International Conference, LPAR-19, Stellenbosch, South Africa, December 14-19, 2013. Proceedings, pages 35-52, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. Google Scholar
  4. Christel Baier and Joost-Pieter Katoen. Principles of model checking. MIT press, 2008. Google Scholar
  5. Brandon Bennett. Modal logics for qualitative spatial reasoning. Logic Journal of the IGPL, 4(1):23-45, 1996. Google Scholar
  6. Mehul Bhatt, Carl Schultz, and Minqian Huang. The shape of empty space: Human-centred cognitive foundations in computing for spatial design. In 2012 IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC), pages 33-40. IEEE, 2012. Google Scholar
  7. Francis DK Ching. Architecture: Form, space, and order. John Wiley & Sons, 2014. Google Scholar
  8. Bowman L Clark et al. Individuals and points. Notre Dame Journal of Formal Logic, 26(1):61-75, 1985. Google Scholar
  9. Matt Duckham, Jenny Lingham, Keith Mason, and Michael Worboys. Qualitative reasoning about consistency in geographic information. Information Sciences, 176(6):601-627, 2006. Google Scholar
  10. Manfred Eppe and Mehul Bhatt. Narrative based postdictive reasoning for cognitive robotics. arXiv preprint, 2013. URL: http://arxiv.org/abs/1306.0665.
  11. Michael Fisher. A Resolution Method for Temporal Logic. In Proceedings of the 12th International Joint Conference on Artificial Intelligence - Volume 1, IJCAI'91, pages 99-104, San Francisco, CA, USA, 1991. Morgan Kaufmann Publishers Inc. Google Scholar
  12. Dov M Gabbay, Agi Kurucz, Frank Wolter, and Michael Zakharyaschev. Many-dimensional modal logics: Theory and applications. Elsevier North Holland, Amsterdam, Boston, 2003. Google Scholar
  13. Dexter Kozen and Rohit Parikh. An elementary proof of the completeness of PDL. Theoretical Computer Science, 14(1):113-118, 1981. Google Scholar
  14. Stephen C Levinson. Frames of reference and Molyneux’s question: Crosslinguistic evidence. Language and Space, 109:169, 1996. Google Scholar
  15. Stephen C Levinson. Language and space. Annual Review of Anthropology, 25(1):353-382, 1996. Google Scholar
  16. Gérard Ligozat. On Generalized Interval Calculi. In Thomas L. Dean and Kathleen McKeown, editors, AAAI, pages 234-240. AAAI Press / The MIT Press, 1991. Google Scholar
  17. Carsten Lutz and Frank Wolter. Modal logics of topological relations. arXiv preprint, 2006. URL: http://arxiv.org/abs/cs/0605064.
  18. Asifa Majid, Melissa Bowerman, Sotaro Kita, Daniel BM Haun, and Stephen C Levinson. Can language restructure cognition? The case for space. Trends in Cognitive Sciences, 8(3):108-114, 2004. Google Scholar
  19. Maarten Marx and Mark Reynolds. Undecidability of Compass Logic. Journal of Logic and Computation, 9(6):897-914, 1999. Google Scholar
  20. Angelo Montanari, Gabriele Puppis, and Pietro Sala. A decidable spatial logic with cone-shaped cardinal directions. In Computer Science Logic, pages 394-408. Springer, 2009. Google Scholar
  21. Antonio Morales, Isabel Navarrete, and Guido Sciavicco. A new modal logic for reasoning about space: Spatial propositional neighborhood logic. Annals of Mathematics and Artificial Intelligence, 51(1):1-25, 2007. Google Scholar
  22. Emilio Muñoz-Velasco, Alfredo Burrieza, and Manuel Ojeda-Aciego. A logic framework for reasoning with movement based on fuzzy qualitative representation. Fuzzy Sets and Systems, 242:114-131, 2014. Google Scholar
  23. Isabel Navarrete, Antonio Morales, and Guido Sciavicco. Consistency Checking of Basic Cardinal Constraints over Connected Regions. In IJCAI, pages 495-500, 2007. Google Scholar
  24. Isabel Navarrete, Antonio Morales, Guido Sciavicco, and M. Antonia Cardenas-Viedma. Spatial reasoning with rectangular cardinal relations. Annals of Mathematics and Artificial Intelligence, 67(1):31-70, 2013. Google Scholar
  25. Werner Nutt. On the translation of qualitative spatial reasoning problems into modal logics. In Annual Conference on Artificial Intelligence, pages 113-124. Springer, 1999. Google Scholar
  26. Eric Pederson. How many reference frames? In International Conference on Spatial Cognition, pages 287-304. Springer, 2002. Google Scholar
  27. Ian Pratt and Dominik Schoop. A complete axiom system for polygonal mereotopology of the real plane. Journal of Philosophical Logic, 27(6):621-658, 1998. Google Scholar
  28. David A. Randell, Zhan Cui, and Anthony Cohn. A Spatial Logic Based on Regions and Connection. In Bernhard Nebel, Charles Rich, and William Swartout, editors, KR'92. Principles of Knowledge Representation and Reasoning: Proceedings of the Third International Conference, pages 165-176. Morgan Kaufmann, 1992. Google Scholar
  29. Mark Reynolds and Michael Zakharyaschev. On the products of linear modal logics. Journal of Logic and Computation, 11(6):909-931, 2001. Google Scholar
  30. Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of computer and system sciences, 4(2):177-192, 1970. Google Scholar
  31. V. Javier Traver and Alexandre Bernardino. A review of log-polar imaging for visual perception in robotics. Robotics and Autonomous Systems, 58(4):378-398, 2010. Google Scholar
  32. Yde Venema. Expressiveness and completeness of an interval tense logic. Notre Dame Journal of Formal Logic, 31(4):529-547, 1990. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact