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.

DeductionModulo[DHK03]isapresentationof rst-order

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
Proof search and proof check for equational and inductive theorems 6.5.3. Inductive termination proofs 6.5.4. Termination proofs for strategies combining ...
Proof search and proof n... 暂无评价 2页 免费...er 1.3 Techniques of Proof: I inductive ...4.2 Limit Theorems diverge to +∞ diverge to ...
Conditional Equational Specifications of Data Types with Partial Operations for ...proof by mathematical induction or inductive theorem proving (ITP) is likely...
Conditional Equational Specifications of Data Types with Partial Operations for ...proof by mathematical induction or inductive theorem proving (ITP) is likely...
Matrix-based inductive t... 暂无评价 15页 免费...Integrating equational r... 暂无评价 15页 免费 ...often use tactics to code automated proof search....
Equational reasoning and term rewriting systemsEquational reasoning and term rewriting...5 Inductive theorems : : : : : : : : : : : : : : : : : :...
for producing new rules and proving theorems. Generalization...Equational inference, canonical proofs, and proof ...Deductive and inductive synthesis of equational...
that can be run on putative theorems or on ...Quickcheck excels at inductive datatypes but is restricted...Nitpick relies on the more natural equational sp...
that can be run on putative theorems or on ...Quickcheck excels at inductive datatypes but is restricted...Nitpick relies on the more natural equational sp...
热门文档