Abstract
We propose a logic of east and west (LEW) for points in 1D Euclidean space. It formalises primitive direction relations: east (E), west (W) and indeterminate east/west (Iew). It has a parameter τ ∈ ℕ>1, which is referred to as the level of indeterminacy in directions. For every τ ∈ ℕ>1, we provide a sound and complete axiomatisation of LEW, and prove that its satisfiability problem is NP-complete. In addition, we show that the finite axiomatisability of LEW depends on τ: if τ = 2 or τ = 3, then there exists a finite sound and complete axiomatisation; if τ > 3, then the logic is not finitely axiomatisable. LEW can be easily extended to higher-dimensional Euclidean spaces. Extending LEW to 2D Euclidean space makes it suitable for reasoning about not perfectly aligned representations of the same spatial objects in different datasets, for example, in crowd-sourced digital maps.
Original language | English |
---|---|
Pages (from-to) | 527-565 |
Number of pages | 39 |
Journal | Journal of Artificial Intelligence Research |
Volume | 76 |
DOIs | |
Publication status | Published - 28 Feb 2023 |
Bibliographical note
Funding Information:We express sincere thanks to reviewers who provided comments that helped us improve the paper. This work is supported by the Young Scientist programme of the National Natural Science Foundation of China (NSFC) with a project code 61703218. Heshan Du, Amin Farjudian and Can Zhou are partially supported by the project: key technological enhancement and applications for Ningbo port terminal operating system, 2019B10026. Anthony Cohn was partially supported by a Fellowship from the Alan Turing Institute, and by the EU Horizon 2020 under grant agreement 825619 (AI4EU).
Publisher Copyright:
© 2023 AI Access Foundation. All rights reserved.
ASJC Scopus subject areas
- Artificial Intelligence