A Logic of East and West

Heshan Du, Natasha Alechina, Amin Farjudian, Brian Logan, Can Zhou, Anthony G. Cohn

Research output: Journal PublicationArticlepeer-review


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 τ ∈ N>1, which is referred to as the level of indeterminacy in directions. For every τ ∈ N>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 languageEnglish
Pages (from-to)527-565
Number of pages39
JournalJournal of Artificial Intelligence Research
Publication statusPublished - 2023

ASJC Scopus subject areas

  • Artificial Intelligence


Dive into the research topics of 'A Logic of East and West'. Together they form a unique fingerprint.

Cite this