Subject-oriented spatial logic
| Autor: | Przemyslaw Andrzej Walega, Michał Zawidzki |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Discrete mathematics
0209 industrial biotechnology Transitive relation Object (grammar) Modal logic 02 engineering and technology Modal operator Computer Science Applications Theoretical Computer Science Orientation (vector space) 020901 industrial engineering & automation Computational Theory and Mathematics Position (vector) 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Boolean satisfiability problem Information Systems PSPACE Mathematics |
| DOI: | 10.1016/j.ic.2020.104643 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|