A new approach for automatic theorem proving in real geometry

被引:42
作者
Dolzmann, A [1 ]
Sturm, T [1 ]
Weispfenning, V [1 ]
机构
[1] Univ Passau, Fak Math & Informat, Passau, Germany
关键词
real quantifier elimination; real geometry; automatic theorem proving over the reals;
D O I
10.1023/A:1006031329384
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
We present a new method for proving geometric theorems in the real plane or higher dimension. The method is derived from elimination set ideas for quantifier elimination in linear and quadratic formulas over the reals. In contrast to other approaches, our method can also prove theorems whose complex analogues fail. Moreover, the problem formulation may involve order inequalities. After specification of independent variables, nondegeneracy conditions are generated automatically. Moreover, when trying to prove conjectures that - apart from nondegeneracy conditions - do not hold in the claimed generality missing premises are found automatically. We demonstrate the applicability of our method to nontrivial examples.
引用
收藏
页码:357 / 380
页数:24
相关论文
共 41 条
[1]  
ABDALLAH CT, 1996, 4 IEEE MED S CONTR A
[2]   A BIBLIOGRAPHY OF QUANTIFIER ELIMINATION FOR REAL CLOSED FIELDS [J].
ARNON, DS .
JOURNAL OF SYMBOLIC COMPUTATION, 1988, 5 (1-2) :267-274
[3]  
Basu S., 1994, Proceedings. 35th Annual Symposium on Foundations of Computer Science (Cat. No.94CH35717), P632, DOI 10.1109/SFCS.1994.365728
[4]  
BUCHBERGER B, 1988, LECT NOTES COMPUT SC, V296, P52
[5]  
Buchberger B., 1965, THESIS U INNSBRUCK I
[6]  
CARRAFERRO G, 1987, THESIS MATH U CATANI
[7]  
Chou S.-C., 1988, MECH GEOMETRY THEORE
[8]   PARTIAL CYLINDRICAL ALGEBRAIC DECOMPOSITION FOR QUANTIFIER ELIMINATION [J].
COLLINS, GE ;
HONG, H .
JOURNAL OF SYMBOLIC COMPUTATION, 1991, 12 (03) :299-328
[9]  
COLMERAUER A, 1990, COMMUN ACM, V33, P70
[10]  
CORLESS RM, 1992, ACM SIGSAM B, V26, P2