Interpreting topological logics over Euclidean spaces
Roman Kontchakov, Ian E. Pratt-Hartmann, Michael Zakharyaschev · Research Explorer (The University of Manchester) · 2010
In this paper we prove some results on the computational complexity of standard quantifierfree spatial logics with the connectedness predicate interpreted over the Euclidean spaces R and R 2. Topological logics with connectedness. A topological logic is a formal language whose variables range over subsets of topological spaces, and whose non-logical primitives denote fixed topological properties and operations involving these subsets. For example, let the function symbols ∩, ∪ and · − denote the operations of intersection, union and topological closure, respectively; let the constant 0 denote the empty set; let the unary predicate c denote the property of connectedness; and let the binary predicate ⊆ denote the subset relation. Then the formula c(r1) ∧ c(r2) ∧ ¬(r1 ∩ r2 ⊆ 0) → c(r1 ∪ r2) (1) states that the union of two intersecting connected sets r1 and r2 is connected; likewise, the formula c(r1) ∧ (r1 ⊆ r2) ∧ (r2 ⊆ r1 − ) → c(r2) (2) states that, if r1 is a connected set, and r2 is sandwiched between r1 and its closure, then r2 is also connected. It is well known that these statements hold for any subsets r1, r2 of any topological