Erika Abraham, Tudor Jebelean,
"Adapting Cylindrical Algebraic Decomposition for Proof Specific Tasks"
, in G. Kusper: ICAI 2017: 10th International Conference on Applied Informatics, 2017
Original Titel:
Adapting Cylindrical Algebraic Decomposition for Proof Specific Tasks
Sprache des Titels:
Englisch
Original Buchtitel:
ICAI 2017: 10th International Conference on Applied Informatics
Original Kurzfassung:
We develop a case study on using quantifier elimination and cylindrical algebraic decomposition for the purpose of finding specific terms for the automation of proving mathematical properties in elementary analysis. Real--life proofs in specific mathematical domains are difficult to automate because of the high number of assumptions necessary for the prover to succeed. In particular, in elementary analysis, it is allmost impossible to find automatically the appropriate terms for the instantiation of universal assumptions and for witnessing the existential goals. We aim at developing such proofs in natural style, in the frame of the {\em Theorema} system. Finding such terms is actually possible by using quantifier elimination (QE) based on cylindrical algebraic decomposition (CAD). However, the current straightforward approach lacks in efficiency, because several redundant calls may be necessary, and because the nature of the problem is slightly different. We study some natural--style proofs, the necessary special terms, and the corresponding usage of the QE/CAD, and identify specific techniques for adapting these algorithms in order to increase their efficiency. The experiments are performed partially in {\em Mathematica} and partially in {\tt SMT-RAT}, the latter used as ``white--box'', which allows to inspect the intermediate results and to adapt certain parts of the algorithms.