La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

# LIX janvier

De
39 pages
Niveau: Supérieur
Parsifal? Typical David Baelde University of Minnesota LIX, 14 janvier 2010

• inductive definitions

• parsifal? typical

• logic programming

• generic quantification

• complex proof

• introduction linc

• very little

• sequent calculus

Voir plus Voir moins
##### Sequent calculus

Vous aimerez aussi

### Focused Inductive Theorem Proving

de profil-zyak-2012

de chaeh

### C documents and settings administrateur mes documents travail

de englue

Parsifal
Typical
David Baelde
University of Minnesota
LIX,
14
janvier
2010
Introduction
LINC,µMALL,µ
IctionistiIntui
IedroriF-tsr
LJ,G
ISequent calculus
,tec.
IUseful structures (focusing)
IProof-search : logic programming, model-checking, theorem proving
Coq
IutnIoitinistic
IedrHigher-or
INatural deduction
IMore complex proof structures
IVery little proof-search
Introduction
This talk
ICoq lacks automation
IWe want more expressivity : heterogeneous (co)inductive deﬁnitions, recursive deﬁnitions
ICoq is a necessary comparison anyway
Outline
Iµ
JL
IEquality
IFixed points
IGeneric quantiﬁcation
µLJ
Denitions
Origins inlogic programming:
nat0
4 =>
nat(s X) =4
antX
Focusedderivations correspond to natural numbers :
T `
nat0
axiom
.at(s0)L,L T `n, . . .
Denitions
Origins inlogic programming:
ant0
=4>nat(s X)4=
antX
Denitionsprovide moreructstrueandssneisevrpsexe
{,B`P)θ:A4=BandA0θ=.Aθ} Γ,A0`P
Derivations correspond to natural numbers :
`nat0 `nat(s0)
Γ`BθA=4B Γ`Aθ
:
4 =
simplify
Let’s
)
X
>
4 =
`uPΓ
Fixed points
=u
(s
Γθ`Pθ:θ,µB~t`G{}),Γ=u`vsc(u.uv=Γ`~tB)(µ`B:ΓesulΓG`t~)Bµ(B,Γt~Bµsdowboily)ItsyNnirgllwoehoftnto(X4=tXnaX=Y.=0tanXtanλx.x(λN.y.x==0ta)YYsnfeµ=andtnat0
X
=
)
=
(X
4 =
Let’s
.
Y
0
u=u`
:
simplify
Fixed points
u=Γ,PΓv`u.u()}=vθscP`:θ{GθΓ~B`tGΓ,µ)~t`B(µB~tΓ,Bµ`Γt~)Bµ(B`Γ:seulgrinowllfoheotxλ.N0=x..yys=xy)NboItsdilntowXtYsnatYnatdef=µ(λna
nirgluseΓ:BI`tµb(o)iBlsdowntothefollowΓG`t~Bµ,{G`tP`θΓΓ`~t~XttµaBnB(Γ,)~µBΓPu`=u`v
=4(X=0∨ ∃Y.X=s Y
Let’syfiimpls:
s yNy)
nat Y)
u=
Fixed points
csu(θ:θ)}Γ,u.=v
nat
µ(λNx.x=0∨ ∃y.x=
def =
Fixed points
Let’sypliifms:
nat X4= (X=0∨ ∃Y.X=s Ynat Y)
natd=efµ(λNx.x=0∨ ∃y.x=s yNy)
It boils down to the following rules :
Γ`B(µB)~tΓ,B(µB)~t`G Γ`µB~tΓ, µB~t`G
{Γθ`Pθ:θcsu(.)} u=v Γ,u=v`P
Γ`u=u
Example
sxnatx
`nat xaxiom =s x,nat x`nat x=L s x=s ynat y`nat xLL s x=0`nat x=Ly.s x=s ynat y`nat x (s x) =0nyat.(ssxx)=`ysnatnytax`nat xµLL =y,nat(s x)`nat y=L
x
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin