A Logic of East and West

We propose a logic of east and west (LEW) for points in 1D Euclidean space. It for-malises primitive direction relations: east (E), west (W) and indeterminate east/west (Iew). It has a parameter T is an element of N > 1, which is referred to as the level of indeterminacy in directions. For every T is an element of 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 axioma-tisability of LEW depends on T: if T = 2 or T = 3, then there exists a finite sound and complete axiomatisation; if T > 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.

Automated summary

We propose a logic system called LEW for describing direction relations in 1D Euclidean space, including east (E), west (W), and indeterminate east/west (Iew). It has a parameter T that represents the level of indeterminacy in directions. For each T, we provide a complete axiomatisation of LEW and prove its NP-completeness. The finite axiomatisability of LEW depends on T: finite axiomatisation exists for T = 2 or T = 3, but not for T > 3. LEW can be extended to higher-dimensional Euclidean spaces, which is useful for reasoning about imperfectly aligned representations of spatial objects in different datasets, such as crowd-sourced digital maps.