A Logic of East and West

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

Research output: Contribution to journalArticlepeer-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-566
Number of pages40
JournalJournal of Artificial Intelligence Research
Early online date1 Feb 2023
Publication statusPublished - 28 Feb 2023


  • knowledge representation
  • qualitative reasoning
  • spatial reasoning
  • theorem proving


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

Cite this