Subject-oriented spatial logic

Journal article

We present a modal logic for subject-oriented representation and reasoning about a two-dimensional space, which we call SOSL. The space is represented with the polar coordinate system where the subject occupies the central point and modal operators are interpreted by relations defined relatively to the position and orientation of the subject, namely ‘outwards’, ‘inwards’, ‘clockwise’, ‘counter-clockwise’, and the transitive closures of the first two. Such logic enables to express operators for the intrinsic relations: ‘in front’, ‘behind’, ‘to the left’, and ‘to the right’ of the subject, for the relative relations: ‘behind an object’, ‘between the subject and an object’, ‘to the left of an object’, and ‘to the right of an object’, and hybrid or distance operators. We prove that the satisfiability problem in SOSL is PSpace-complete, the same complexity holds over the classes of finite or infinite models, however, for models of fixed size the problem becomes NP-complete.

Authors: Wałęga, PA; Zawidzki, M

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Information and Computation
• Volume: 280
• Article number: 104643
• Publication date: 2020-11-01
• Acceptance date: 2020-09-29
• DOI: 10.1016/j.ic.2020.104643
• ISSN: 0890-5401
• Language: English
• Keywords: modal logics; FFR; spatial logics; knowledge representation