N-dimensional versus (N-1)-dimensional connectivity testing of first-order queries to semi-algebraic sets

Authors

Floris Geerts, Lieven Smits, Jan Van den Bussche

Bibliographical Reference

Acta Informatica (2005) 42(1), pages 43-56.

Abstract

This paper addresses the question whether one can determine the connectivity of a semi-algebraic set in three dimensions by looking only at two-dimensional "samples" of the set, where these samples are defined by first-order queries. The question is answered negatively for two classes of first-order queries: cartesian-product-free, and positive one-pass.

References

  1. Abiteboul, S., Hull, R., Vianu, V., "Foundations of Databases," Addison-Wesley 1995.
  2. Benedikt, M., Grohe, M., Libkin, L., Segoufin, L., Reachability and connectivity queries in constraint databases, J.Computer System Sc. 66(1), 169-206 (2003).
  3. Bochnak, J., Coste, M., Roy, M.F., "Real Algebraic Geometry," Springer 1998.
  4. Ebbinghaus, H.D., Flum, J., "Finite Model Theory 2nd Ed.," Springer 1999.
  5. Giannella, C., Van Gucht, D.V., Adding a path connectedness operator to FO+poly (linear), Acta Informatica 33(9), 621-648 (2002).
  6. Immerman, N., "Descriptive Complexity," Springer 1999.
  7. Kuper, G., Paredaens, J., Libkin, L., "Constraint Databases," Springer 2000.
  8. Van den Dries, L., "Tame Topology and O-minimal Structures," Cambridge University Press 1998.

History of this page