The expressive power of first-order topological languages

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the expressive power of the first-order structure 〈Ω,C 〉 where Ω is either of two of different domains of extended regions in Euclidean space, and C(x,y) is the topological relation 'Region x is in contact with region y.' We prove two main theorems: Let P[+] be the domain of bounded, non-empty, rational polyhedra in two- or three-dimensional Euclidean space. A relation Γ over P[+] is definable in the structure 〈P[+], C〉 if and only if Γ is arithmetic and invariant under rational PL-homeomorphisms of the space to itself. We also extend this result to a number of other domains, including the domain of all polyhedra and the domain of semi-algebraic regions.Let R be the space of bounded, non-empty, closed regular regions in n-dimensional Euclidean space. Any analytical relation over lower dimensional (i.e. empty interior) compact point sets that is invariant under homeomorphism is implicitly definable in the structure 〈R,C〉.

Original languageEnglish (US)
Pages (from-to)1107-1141
Number of pages35
JournalJournal of Logic and Computation
Volume23
Issue number5
DOIs
StatePublished - Oct 2013

Keywords

  • First-order language
  • expressivity
  • qualitative spatial reasoning
  • topological language

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Logic
  • Arts and Humanities (miscellaneous)
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'The expressive power of first-order topological languages'. Together they form a unique fingerprint.

Cite this