Deciding polynomial-exponential problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Deciding polynomial-exponential problems

Full text

Pdf (209 KB)

Source

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

Linz/Hagenberg, Austria

SESSION: Contributed papers table of contents

Pages 215-222

Year of Publication: 2008

ISBN:978-1-59593-904-3

Authors

Melanie Achatz	University of Passau, Passau, Germany
Scott McCallum	Macquarie University, Sydney, Australia
Volker Weispfenning	University of Passau, Passau, Germany

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 43, Citation Count: 0

Additional Information:

abstract references 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/1390768.1390799 What is a DOI?

ABSTRACT

This paper presents a decision procedure for a certain class of sentences of first order logic involving integral polynomials and the exponential function in which the variables range over the real numbers. The inputs to the decision procedure are prenex sentences in which only the outermost quantified variable can occur in the exponential function. The decision procedure has been implemented in the computer logic system REDLOG. Closely related work is reported in [2, 7, 16, 20, 24].

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	M. Achatz. Deciding polynomial-exponential problems. Diploma thesis, University of Passau, D-94030 Passau, Germany, Sept. 2006.
	2	Hirokazu Anai , Volker Weispfenning, Deciding linear-trigonometric problems, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.14-22, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345567]
	3	D. S. Arnon, G. E. Collins, and S. McCallum. Cylindrical algebraic decomposition i: Basic algorithm. In B. Caviness and J. Johnson, editors, Quantifier Elimination and Cylindrical Algebraic Decomposition, Texts and Monographs in Symbolic Computation, pages 136--151. Springer, Wien, New York, 1998.
	4	Thomas Becker , Volker Weispfenning , Heinz Kredel, Gro¨bner bases: a computational approach to commutative algebra, Springer-Verlag, London, 1993
	5	E. Bishop. Foundations of Constructive Analysis. McGraw-Hill, New York, 1967.
	6	E. Bishop and D. Bridges. Constructive Analysis. Grundlehren der math. Wissenschaften. Springer-Verlag, Berlin, 1985.
	7	G. E. Collins. Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In B. Caviness and J. Johnson, editors, Quantifier Elimination and Cylindrical Algebraic Decomposition, Texts and Monographs in Symbolic Computation, pages 85--121. Springer, Wien, New York, 1998.
	8	George E. Collins , Rüdiger Loos, Polynomial real root isolation by differentiation, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.15-25, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806319]
	9	George E. Collins , Rudiger Loos, Real zeroes of polynomials, Computer algebra: symbolic and algebraic computation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1983
	10	A. Dolzmann and T. Sturm. Redlog user manual, edition 3.0. Technical report, University of Passau, 2004.
	11	G. H. Hardy. Orders of Infinity. Cambridge Univ. Press, Cambridge, 1910.
	12	A. Hearn. Reduce user's manual for version 3.8. Technical report, RAND Corporation, 2004.
	13	J. R. Johnson. Algorithms for polynomial real root isolation. In B. Caviness and J. Johnson, editors, Quantifier Elimination and Cylindrical Algebraic Decomposition, Texts and Monographs in Symbolic Computation, pages 269--299. Springer, Wien, New York, 1998.
	14	R. G. K. Loos. Computing in algebraic extensions. In B. Buchberger, G. Collins, and R. Loos, editors, Computer Algebra: Symbolic and Algebraic Computation, pages 173--188. Springer, Wien, New York, 1982.
	15	A. Macintyre and A. Wilkie. On the decidability of the real exponential field. In Kreiseliana: About and around Georg Kreisel, pages 441--467. A. K. Peters, 1996.
	16	Aude Maignan, Solving one and two-dimensional exponential polynomial systems, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.215-221, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281616]
	17	A. Maignan. Real solving of elementary-algebraic systems. Numerical Algorithms, 27:153--167, 2001.
	18	S. McCallum and V. Weispfenning. Deciding polynomial-exponential problems. Technical report, Macquarie University, 2006.
	19	Savvas Pericleous , Nicolai Vorobjov, New complexity bounds for cylindrical decompositions of sub-pfaffian sets, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.268-275, July 2001, London, Ontario, Canada [doi>10.1145/384101.384137]
	20	Daniel Richardson, Towards computing non algebraic cylindrical decompositions, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.247-255, July 15-17, 1991, Bonn, West Germany [doi>10.1145/120694.120732]
	21	A. Seidl. Cylindrical decomposition under application-oriented paradigms. Doctoral dissertation. University of Passau, D-94030 Passau, Germany, Nov. 2006.
	22	A. B. Shidlovskii. Transcendental Numbers. Walter de Gruyter, Berlin, New York, 1989.
	23	A. Tarski. A decision algorithm for elementary algebra and geometry. In B. Caviness and J. Johnson, editors, Quantifier Elimination and Cylindrical Algebraic Decomposition, Texts and Monographs in Symbolic Computation, pages 24--84. Springer, Wien, New York, 1998.
	24	V. Weispfenning. Deciding linear--transcendental problems. In V. Ganzha, E. Mayr, and E. Vorozhtshov, editors, Computer Algebra in Scientific Computation -- CASC 2000, pages 423--438. Springer, 2000.