Definability over Linear Constraints

Abstract We settle a number of questions concerning definability in first order logics with an extra predicate symbol ranging over semi-linear sets. These questions are motivated by the constraint database model for representing spatial data. We give new results both on the positive and negative side: we show that in first-order logic one cannot query a semi-linear set as to whether or not it contains a line, or whether or not it contains the line segment between two given points. However, we show that some of these queries become definable if one makes small restrictions on the semi-linear sets considered.

Authors

• Michael Benedikt
• H. Jerome Keisler

Keywords

No keywords are indexed for this paper.