Computing the complexification of a semi-algebraic set

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computing the complexification of a semi-algebraic set

Full text

Pdf (881 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Proceedings of the 1996 international symposium on Symbolic and algebraic computation table of contents

Zurich, Switzerland

Pages: 26 - 34

Year of Publication: 1996

ISBN:0-89791-796-0

Authors

Marie-Françoise Roy	IRMAR (URA CNRS 305), Université de Rennes, Campus de, Beaulieu 35042 Rennes cedex France
Nicolai Vorobjov	School of Mathematical Sciences, University of Bath, Bath, BA2, 7AY, United Kingdom

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
SIGNUM: ACM Special Interest Group on Numerical Mathematics

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 9, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/236869.236891 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	S. BASU, R. POLLACK, M.-F. RoY, A New Algorithm to Find a Point in Every Cell Defined by a Family of Polynomials. "Quantifier Elimination and Cylindrical Algebraic Decomposition", B. Caviness and J. Johnson Eds., Springer-Verlag, to appear.
	2	Saugata Basu , Richard Pollack , Marie-Françoise Roy, On the combinatorial and algebraic complexity of quantifier elimination, Journal of the ACM (JACM), v.43 n.6, p.1002-1045, Nov. 1996 [doi>10.1145/235809.235813]
	3	J. BOCHNAK, M. COSTE, AND M.-F. RoY, Gdomdtrie Algdbrique RdeUe. Springer-Verlag, Berlin, 1987.
	4	A. L. CHISTOV , Algorithm of polynomial complexity for factoring polynomials and finding the components of varieties in subexponential time. In Zapiski Nauchnykh Seminarov LOMI 137 (1984), 124-188. English translation in J. Soviet Math. 34 (1986), 1838-1882.
	5	Alexander L. Chistov, Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic, Fundamentals of Computation Theory, p.63-69, September 09-13, 1985
	6	A. CHISTOV, Polynomial time computation of the dimension of components of algebraic varieties in zerocharacteristic. Preprint 95-06, Universit~ Paris 12 (1995).
	7	André Galligo , Nicolai Vorobjov, Complexity of finding irreducible components of a semialgebraic set, Journal of Complexity, v.11 n.1, p.174-193, March 1995 [doi>10.1006/jcom.1995.1007]
	8	D. GRIGORIEV, Factorization of polynomials over finite field and the solution of systems of algebraic equations. In Zapiski Nauchnykh Seminarov LOMI137 (1984), 20-79. English translation in J. Soviet Math. 34 (1986), 1762- 1803.
	9	D. Yu. Grigor'ev , N. N. Vorobjov, Solving systems of polynomial inequalities in subexponential time, Journal of Symbolic Computation, v.5 n.1-2, p.37-64, February/April 1988 [doi>10.1016/S0747-7171(88)80005-1]
	10	J. HEINTZ, , Definability and fast quantifier elimination in algebraically closed fields. Theoret. Comput. Sci. 24 (1983), 239-278.
	11	S. LANG, Algebra. New York: Addison-Wesley (1965).
	12	R. POLLACK, M.-F. RoY, On the number of cells defined by a set of polynomials. C. R. Acad. Sci. Paris 316 (1993), 573-577.
	13	J. RENEGAR, A faster PSPA CE algorithm for existential theory of reals. Proc. 29th IEEE Syrup. on Foundations of Comput. Sci. (1988), 291-295.
	14	Marie-Françoise Roy , Nicolai Vorobjov, Finding irreducible components of some real transcendental varieties, Computational Complexity, v.4 n.2, p.107-132, April 1994 [doi>10.1007/BF01202285]
	15	A. TARSKI, A Decision Method for Elementary Algebra and Geometry. Univerity of California Press, Berkeley (1951).
	16	H. E. WARREN, (Lower bounds for approximation of nonlinear manifolds. Trans. Amer. Math. Soc. 133 (1968), 167-178.
	17	Andrew Chi-Chih Yao, Decision tree complexity and Betti numbers, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.615-624, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195414]

CITED BY 2

	Nicolai Vorobjov, Computing local dimension of a semialgebraic set, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.483-487, May 24-26, 1998, Dallas, Texas, United States
	Johannes Grabmeier , Erich Kaltofen , Volker Weispfenning, Cited References, Computer algebra handbook, Springer-Verlag New York, Inc., New York, NY, 2003