On the Decidability of Semi-Linearity for Semi-Algebraic Sets and its Implications for Spatial Databases (extended abstract)
Summary: Proves decidability of whether a semi-algebraic set is semi-linear, highlights the role of coefficient types and the geometric notion of regularity, and shows regular points are computable in FO+linear. Consequence: yields a syntactic language exactly capturing the FO+poly queries that are linear, circumventing previous undecidability of testing linearity. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Freddy Dumortier
- 2. Marc Gyssens
- 3. Luc Vandeurzen
- 4. Dirk Van Gucht
Incoming Citations (Sorted by Pagerank)
Showing 6 of 6 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,502 | Efficient Searching with Linear Constraints (Extended Abstract) | 1998 | PODS | 0.00011643406 |
| 2,245 | The DEDALE System for Complex Spatial Queries | 1998 | SIGMOD | 9.2085554e-05 |
| 4,369 | An Expressive Language for Linear Spatial Database Queries (extended abstract) | 1998 | PODS | 6.2487721e-05 |
| 4,379 | Safe Constraint Queries | 1998 | PODS | 6.2397591e-05 |
| 12,682 | Fixed-Point Query Languages for Linear Constraint Databases | 2000 | PODS | 4.1945683e-05 |
| 12,683 | Linear approximation of planar spatial databases using transitive-closure logic | 2000 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 4 of 4 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 620 | Constraint Programming and Database Languages: A Tutorial | 1995 | PODS | 0.00019005954 |
| 1,415 | Towards a Theory of Spatial Database Queries (Extended Abstract) | 1994 | PODS | 0.0001211468 |
| 1,741 | Relational Expressive Power of Constraint Query Languages | 1996 | PODS | 0.00010714223 |
| 3,191 | The LyriC Language: Querying Constraint Objects | 1995 | SIGMOD | 7.4112897e-05 |
Previous
Page 1 / 1
Next