A formal quantifier elimination for algebraically closed fields - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2010

A formal quantifier elimination for algebraically closed fields

Résumé

We prove formally that the first order theory of algebraically closed fields enjoy quantifier elimination, and hence is decidable. This proof is organized in two modular parts. We first reify the first order theory of rings and prove that quantifier elimination leads to decidability. Then we implement an algorithm which constructs a quantifier free formula from any first order formula in the theory of ring. If the underlying ring is in fact an algebraically closed field, we prove that the two formulas have the same semantic. The algorithm producing the quantifier free formula is programmed in continuation passing style, which leads to both a concise program and an elegant proof of semantic correctness.
Fichier principal
Vignette du fichier
main.pdf (337.5 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00464237 , version 1 (16-03-2010)
inria-00464237 , version 2 (19-03-2010)
inria-00464237 , version 3 (29-03-2010)

Identifiants

  • HAL Id : inria-00464237 , version 2

Citer

Cyril Cohen, Assia Mahboubi. A formal quantifier elimination for algebraically closed fields. 2010. ⟨inria-00464237v2⟩
533 Consultations
1194 Téléchargements

Partager

Gmail Facebook X LinkedIn More