Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-26T07:21:25.452Z Has data issue: false hasContentIssue false
  • English
  • Français

Topological elementary equivalence of closed semi-algebraic sets in the real plane

Published online by Cambridge University Press:  12 March 2014

Bart Kuijpers ,
Jan Paredaens  and
Jan Van den Bussche
Bart Kuijpers
Affiliation:
Department Wni, University of Limburg(LUC), Universitaire Campus, B-3590 Diepenbeek, Belgium, E-mail:[email protected]
Jan Paredaens
Affiliation:
Department of Mathematics and Computer Science, University of Antwerp(UIA), Universiteitsplein 1, B-2610 Antwerp, Belgium, E-mail:[email protected]
Jan Van den Bussche
Affiliation:
Department Wni, University of Limburg(LUC), Universitaire Campus, B-3590 Diepenbeek, Belgium, E-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We investigate topological properties of subsets S of the real plane, expressed by first-order logic sentences in the language of the reals augmented with a binary relation symbol for S. Two sets are called topologically elementary equivalent if they have the same such first-order topological properties. The contribution of this paper is a natural and effective characterization of topological elementary equivalence of closed semi-algebraic sets.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 65 , Issue 4 , December 2000 , pp. 1530 - 1555
Copyright
Copyright © Association for Symbolic Logic 2000

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Arnon, D. S., Geometric reasoning with logic and algebra, Artificial Intelligence, vol. 37 (1988), pp. 37–60.CrossRefGoogle Scholar
[2]Belegradek, O. V., Stolboushkin, A. P., and Taitslin, M. A., On order-generic queries, Technical Report 96-01, DIMACS, 1996.Google Scholar
[3]Benedikt, M., Dong, G., Libkin, L., and Wong, L., Relational expressive power of constraint query languages, Proceedings of the 15th ACM symposium on principles of database systems, ACM Press, 1996, pp. 5–16.Google Scholar
[4]Benedikt, M. and Libkin, L., On the structure of queries in constraint query languages, Proceedings of the 11th IEEE symposium on logic in computer science, IEEE Computer Society Press, 1996, pp. 25–34.Google Scholar
[5]Benedikt, M., Languages for relational databases over interpreted structures, Proceedings of the 16th ACM symposium on principles of database systems, ACM Press, 1997, pp. 87–98.Google Scholar
[6]Bochnak, J., Coste, M., and Roy, M.-F., GÉomÉtrie algÉbrique rÉelle, Springer-Verlag, 1987.Google Scholar
[7]Caviness, B. F. and Johnson, J. R. (editors), Quantifier elimination and cylindrical algebraic decomposition, Springer-Verlag, Wien-New York, 1998.CrossRefGoogle Scholar
[8]Collins, G. E., Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Lecture Notes in Computer Science, vol. 33, Springer-Verlag, 1975, pp. 134–183.CrossRefGoogle Scholar
[9]Coste, M., Ensembles semi-algÉbriques,GÉometrie algÉbrique rÉelle et formes quadratiques, Lecture Notes in Mathematics, vol. 959, Springer-Verlag, 1982, pp. 109–138.CrossRefGoogle Scholar
[10]Cromwell, R. H. and Fox, R. H., Introduction to knot theory, Graduate Texts in Mathematics, vol. 57, Springer-Verlag, 1977.CrossRefGoogle Scholar
[11]Ebbinghaus, H. D. and Flum, J., Finite model theory, Springer-Verlag, 1995.Google Scholar
[12]Flum, J. and Ziegler, M., Topological model theory, Lecture Notes in Mathematics, vol. 769, Springer-Verlag, 1980.CrossRefGoogle Scholar
[13]Grumbach, S. and Su, J., Queries with arithmetical constraints, Theoretical Computer Science, vol. 173 (1997), no. 1, pp. 151–181.CrossRefGoogle Scholar
[14]Grumbach, S., Su, J., and Tollu, C., Linear constraint query languages: expressive power and complexity, Logic and computational complexity (Leivant, D., editor). Lecture Notes in Computer Science, vol. 960, Springer-Verlag, 1995, pp. 426–446.CrossRefGoogle Scholar
[15]Henson, C. W., Jockisch, C. G. Jr., Rubel, L. A., and Takeuti, G., First order topology, Dissertations Mathematicae, vol. CXLIII, 1977.Google Scholar
[16]Moise, E. E., Geometric topology in dimensions 2 and 3, Graduate Texts in Mathematics, vol. 47, Springer-Verlag, 1977.CrossRefGoogle Scholar
[17]Paredaens, J., Van den Bussche, J., and Van Gucht, D, First-order queries on finite structures over the reals, Proceedings of the 10th IEEE symposium on logic in computer science, IEEE Computer Society Press, 1995, pp. 79–89.Google Scholar
[18]Pillay, A., First order topological structures and theories, this Journal, vol. 52 (1987). no. 3, pp. 763–778.Google Scholar
[19]Renegar, J., On the computational complexity and geometry of the first-order theory of the reals, Journal of Symbolic Computation, vol. 13 (1989), pp. 255–352.CrossRefGoogle Scholar
[20]Robinson, A., A note on topological model theory, Fundamenta Mathematicae, vol. 81 (1974), pp. 159–171.CrossRefGoogle Scholar
[21]Stillwell, J., Classical topology and combinatorial group theory, Graduate Texts in Mathematics, vol. 72, Springer-Verlag, 1980.CrossRefGoogle Scholar
[22]Stolboushkin, A. P. and Taitslin, M. A., Linear vs. order constraints over rational databases, Proceedings of the 15th ACM symposium on principles of database systems, ACM Press, 1996, pp. 17–27.Google Scholar
[23]Tarski, A., A decision method for elementary algebra and geometry. University of California Press, 1951.CrossRefGoogle Scholar