Hostname: page-component-745bb68f8f-d8cs5 Total loading time: 0 Render date: 2025-01-07T16:19:53.216Z Has data issue: false hasContentIssue false
  • English
  • Français

Implementing the cylindrical algebraic decomposition within the Coq system

Published online by Cambridge University Press:  01 February 2007

ASSIA MAHBOUBI
ASSIA MAHBOUBI*
Affiliation:
INRIA Sophia Antipolis, 2004, routes des Lucioles – B.P. 93, 06902 Sophia Antipolis Cedex, France Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The Coq system is a Curry–Howard based proof assistant. Therefore, it contains a full functional, strongly typed programming language, which can be used to enhance the system with powerful automation tools through the implementation of reflexive tactics. We present the implementation of a cylindrical algebraic decomposition algorithm within the Coq system, whose certification leads to a proof producing decision procedure for the first-order theory of real numbers.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 17 , Issue 1 , February 2007 , pp. 99 - 127
Copyright
Copyright © Cambridge University Press 2007

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

Allen, S. F., Constable, R. L., Constable, L., Howe, D. J. and Aitken, W. (1990) The Semantics of Reflected Proof. Proceedings of the 5th Symposium on Logic in Computer Science (LICS), IEEE Computer Society Press.Google Scholar
Avigad, J., Donnelly, K., Gray, D. and Raff, P. (2005) A Formally Verified Proof of the Prime Number Theorem. To appear in the ACM Transactions on Computational Logic. (Available at http://arxiv.org/abs/cs.AI/0509025.)Google Scholar
Barthe, G., Capretta, V. and Pons, O. (2003) Setoids in Type Theory. Journal of Functional Programming 13 (2)261–293.CrossRefGoogle Scholar
Basu, S., Pollack, R. and Roy, M. (2003) Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics 10, Springer-Verlag. (Draft of the second version available at http://name.math.univ-rennes1.fr/marie-francoise.roy/bpr-posted1.html.)CrossRefGoogle Scholar
Bertot, Y. and Casteran, P. (2004) Interactive Theorem Proving and Program Development. Coq'Art: The Calculus of Inductive Constructions, Texts in Theoretical Computer Science, an EATCS Series, Springer-Verlag.CrossRefGoogle Scholar
Bronstein, M. et al. (2004) AXIOM – The Scientific Computation System. (Homepage: http://axiom.axiom-developer.org/axiom-website/community.html)Google Scholar
Brown, C. W. (2004) QEPCAD. (Homepage: http://www.cs.usna.edu/~qepcad/B/QEPCAD.html)CrossRefGoogle Scholar
Brown, C. W. (2003) QEPCAD B: a Program for Computing with Semi-Algebraic Sets using CADs. SIGSAM Bull. 37 (4)97–108.CrossRefGoogle Scholar
Caviness, B. and Johnson, J. (eds.) (1998) Quantifier Elimination and Cylindrical Algebraic Decomposition, Texts and monographs in symbolic computation, Springer-Verlag.CrossRefGoogle Scholar
Collins, G. E. (1975) Quantifier Elimination for the Elementary Theory of Real Closed Fields by Cylindrical Algebraic Decomposition. Springer-Verlag Lecture Notes in Computer Science 33 134–183.CrossRefGoogle Scholar
Collins, G. E. and Hong, H. (1991) Partial Cylindrical Algebraic Decomposition for Quantifier Elimination. Journal of Symbolic Computation 12 (3)299–328.CrossRefGoogle Scholar
Delahaye, D. (2002) A Proof Dedicated Meta-Language. In: Proceedings of Logical Frameworks and Meta-Languages (LFM), Copenhagen (Denmark). Electronic Notes in Theoretical Computer Science 70 (2).Google Scholar
Delahaye, D. and Mayero, M. (2005) Quantifier Elimination over Algebraically Closed Fields in a Proof Assistant using a Computer Algebra System. In: Proceedings of Calculemus 2005.Google Scholar
Dolzmann, A., Seidl, A. and Sturm, T. (2004) Efficient Projection Orders for CAD. In: Gutierrez, J. (ed.) Proceedings of the ISSAC 2004, ACM Press 111–118.Google Scholar
Dolzmann, A. and Sturm, T. (1997) Redlog: Computer Algebra meets Computer Logic. SIGSAM Bull 31 (2).CrossRefGoogle Scholar
Dolzmann, A., Sturm, T. and Weispfenning, V. (1998) A New Approach for Automatic Theorem Proving in Real Geometry. Journal of Automated Reasoning 21 357–380.CrossRefGoogle Scholar
Grégoire, B. and Leroy, X. (2002) A Compiled Implementation of Strong Reduction. In: International Conference on Functional Programming 2002, ACM Press 235–246.Google Scholar
Grégoire, B. and Mahboubi, A. (2005) Proving Equalities in a Commutative Ring Done Right in Coq. In: Proceedings of the TPHOLs 2005, Springer-Verlag 98–113.Google Scholar
Grégoire, B. and Théry, L. (2006) Certifying Large Prime Numbers: a purely functional library for modular arithmetic To appear in Proceedings of IJCAR06. (Available at http://gforge.inria/projects/coqprime/)Google Scholar
Harrison, J. and Théry, L. (1998) A Skeptic's Approach to Combining HOL and Maple. Journal of Automated Reasoning 21 279–294.CrossRefGoogle Scholar
Hörmander, L. (2003) The Analysis of Linear Partial Differential Operators (II), Grundlehren der Mathematischen Wissenschaften 257, Springer-Verlag.CrossRefGoogle Scholar
Mahboubi, A. (2006) Proving Formally the Implementation of an Efficient GCD Algorithm for Polynomials. To appear in Proceedings of IJCAR06.CrossRefGoogle Scholar
Mahboubi, A. and Pottier, L. (2002) Elimination des Quantificateurs sur les Réels en Coq. In: Journées Françaises des Languages Applicatifs.Google Scholar
McLaughlin, S. and Harrison, J. (2005) A Proof-Producing Decision Procedure for Real Arithmetic. In: CADE 295–314.Google Scholar
Niqui, M. and Bertot, Y. (2003) Qarith: Coq Formalisation of Lazy Rational Arithmetic. In: TYPES 2003. Springer-Verlag Lecture Notes in Computer Science 3839309–323.Google Scholar
Palmgren, E. (2002) An Intuitionistic Axiomatisation of Real Closed Fields. Mathematical Logic Quarterly 48 (2)297–299.3.0.CO;2-G>CrossRefGoogle Scholar
Sacerdoti, C. (2006) A Semi-reflexive Tactic for (Sub-)Equational Reasoning. In: TYPES 2004. Springer-Verlag Lecture Notes in Computer Science 383998–114.Google Scholar
Strzebonski, A. (2004) Cylindrical Algebraic Decomposition. In: MathWorld – A Wolfram Web Resource, created by Eric W. Weisstein. (Available at http://mathworld.wolfram.com/CylindricalAlgebraicDecomposition.html)Google Scholar
Tarski, A. (1948) A Decision Method for Elementary Algebra and Geometry, The RAND Corporation, Santa Monica, U.S. Air Force Project RAND, R-109.Google Scholar
The Coq Development Team (2004) The Coq Proof Assistant Reference Manual Version 8.0, Institut National de Recherche en Informatique et en Automatique. (Available at http://coq.inria.fr/)Google Scholar
Théry, L. (2001) A Machine-Checked Implementation of Buchberger's Algorithm. Journal of Automated Reasoning 26 107–137.CrossRefGoogle Scholar
von zur Gathen, J. and Lücking, T. (2003) Subresultants Revisited. Theoretical Computer Science 297 199–239.CrossRefGoogle Scholar