A Large-Scale Experiment in Executing Extracted Programs | Zendy

Luís Cruz-Filipe | Zendy; Pierre Letouzey | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A Large-Scale Experiment in Executing Extracted Programs

Author(s) -

Luís Cruz-Filipe,

Pierre Letouzey

Publication year - 2006

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2005.11.024

Subject(s) - mathematical proof , computer science , inefficiency , proof assistant , algebra over a field , scale (ratio) , theoretical computer science , automated theorem proving , algorithm , calculus (dental) , mathematics , pure mathematics , medicine , physics , geometry , economics , microeconomics , dentistry , quantum mechanics

It is a well-known fact that algorithms are often hidden inside mathematical proofs. If these proofs are formalized inside a proof assistant, then a mechanism called extraction can generate the corresponding programs automatically. Previous work has focused on the difficulties in obtaining a program from a formalization of the Fundamental Theorem of Algebra inside the Coq proof assistant. In theory, this program allows one to compute approximations of roots of polynomials. However, as we show in this work, there is currently a big gap between theory and practice. We study the complexity of the extracted program and analyze the reasons of its inefficiency, showing that this is a direct consequence of the approach used throughout the formalization

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research