文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Proof Search and Proof Check for Equational and Inductive Theorems
侵权投诉

Proof Search and Proof Check for Equational and Inductive Theorems

Abstract. This paper presents on-going researches on theoretical and practical issues of combining rewriting based automated theorem proving and user-guided proof development, with the strong constraint of safe cooperation of both. In practice, we instanti

ProofSearchandProofCheckforEquational

andInductiveTheorems

EricDeplagne,ClaudeKirchner,H´el`eneKirchner,andQuangHuyNguyen

LORIA-INRIA-CNRS

BP239F-54506Vand uvre-l`es-NancyCedex

Helene.Kirchner@loria.fr

Fax:+33383278319

Abstract.Thispaperpresentson-goingresearchesontheoreticalandpracticalissuesofcombiningrewritingbasedautomatedtheoremprov-inganduser-guidedproofdevelopment,withthestrongconstraintofsafecooperationofboth.Inpractice,weinstantiatethetheoreticalstudyontheCoqproofassistantandtheELANrewritingbasedsystem,focusing rstonequationalandthenoninductiveproofs.Di erentconcepts,es-peciallyrewritingcalculusanddeductionmodulo,contributetode neandtorelateproofsearch,proofrepresentationandproofcheck.

Keywords:automatedtheoremproving,proofassistant,deduction,computation,rewriterules,proofterms,induction.

1Introduction

Althoughformalizedsincethebeginningofmechanizeddeduction,thethreeconceptsofproofsearch,proofrepresentationandproofcheckarealwaysoffundamentalinterest,bothfromthetheoreticalpointofviewandfortheirap-plications,inparticularconcerningcomputersecurityanddependability.Thesethreenotionshavedrawnindependentlymuchattention,butarecloselyrelatedandthisworkaddressesthemasawhole,focusing rstonequationalandthenoninductiveproofs.

Theconceptualbridgesjoiningproofsearch,representationandcheckarethedeductionmoduloandtherewritingcalculus.

Proof Search and Proof Check for Equational and Inductive Theorems

DeductionModulo[DHK03]isapresentationof rst-order

Proof Search and Proof Check for Equational and Inductive Theorems

logicallowingtoidentifythenotionsofcomputationanddeductionandtheirinteractions.Thisfundamentaldi erencebetweencom-putationanddeductionhasbeenidenti edsinceatleastonecenturybyHenriPoincar´eanditplaysafundamentalroleintodayprooftheory,becausethesta-tusofwhatwesearchforandwhatneedstobecomputedshouldbeidenti edandtreatedappropriately,inordertogetproofswhereonlyuseful(andoftendi cult)partsaredescribed.

Indeed,wearetodayabletocomputebillionofnumericaloperationspersecondandsymbolicsystemslikeELAN[KM01]areabletoexecuteseveraltensofmillionsofcomputationalrewritespersecond.Buildingthesecomputationsasexplicitpartsofproofsishopelessand,mostimportant,uninteresting.Deductionmoduloisawaytokeepsuchcomputationsintoaccount.

F.Baader(Ed.):CADE-19,LNAI2741,pp.297–316,2003.

cSpringer-VerlagBerlinHeidelberg2003

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email