The expressivity of quantifying over regions

Research output: Contribution to journalArticle

Abstract

We categorize in recursion-theoretic terms the expressivity of a number of first-order languages that allow quantification over regions in Euclidean space. Specifically we show the following: (1) Let u be any class of closed regions in Euclidean space that includes all simple polygons. Let C(x,y) be the relation, 'region x is connected to region y' and let Convex(x) be the property, 'region x is convex'. Then any relation over u that is analytical and invariant under affine transformations is first-order definable in the structure (u, C, Convex). (2) Let u be as in (1), and let Closer(x, y, z) be the relation 'region y is closer to y than to z.' Then any relation over u that is analytical and invariant under orthogonal transformations is first-order definable in the structure (u, Closer). (3) Let u be the class of finite unions of intervals in the real line. Then any relation over u that is analytical and invariant under linear transformations is first-order definable in the structure (u, Closer). (4) If the class of regions is restricted to be polygons with rational vertices, then results analogous to (1-3) hold, substituting 'arithmetical relation' for 'analytical relation'.

Original languageEnglish (US)
JournalJournal of Logic and Computation
Volume16
Issue number6
DOIs
StatePublished - Dec 2006

Keywords

  • Analytical relation
  • Expressivity
  • First-order definability
  • Spatial representation

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'The expressivity of quantifying over regions'. Together they form a unique fingerprint.

  • Cite this