Exploiting non canonicity in the sequent calculus

Jean - Marc Andreoli

Description

Niveau: Supérieur, Doctorat, Bac+8
École Polytechnique Thèse de Doctorat Spécialité Informatique Exploiting non-canonicity in the sequent calculus Présentée et soutenue publiquement par Vivek Nigam le 18 septembre 2009 devant le jury composé de Rapporteurs: Jean-Marc Andreoli Roy Dyckhoff Directeur de thèse: Dale Miller Examinateurs: Iliano Cervesato Ian Mackie Damiano Mazza Elaine Pimentel

• logic


• contain finite


• when tables


• proof systems


• single linear


• can capture


• algorithms can

Sujets

• Moreau
• Gazeau
• Straßburger
• Kramer
• Philippus Baldaeus
• Andreoli
• École polytechnique
• Cordeiro

Informations

• Publié par: profil-zyak-2012
• Publié le: 01 septembre 2009
• Nombre de lectures: 126
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Mazza?coleDPolos?ytechniqueIlianoTh?seledeJean-MarcDoth?se:ctoratIanSpan?cialit?cInformatiqueRappExploitingRonon-canonicityDirecteurinMillerthevesasequeckientPimentelcalculustPr?senjuryt?eompetdesoutenorteurs:ueAndreolipubliquemenytyckhoffpardeVivekDaleNigamExaminateurs:leCer18toseptemMabrDamianoeElaine2009devrThisuturewEuroporkecwproasCommission,suppEmergingortedunbIST-2005-015905ythetheeanInformationFSoandcietTyhnologiesTdeecthehnologiesMOBIUSprogrammeject.ofandithankAactheknoerg,wledgmenctsstepsFirstyofandall,S?rgioItothankwmthroughydelicatessen,supalwervisorAlexandreDalelogicMillerheforHermann,hisSimonconsptineraluousPsupplongortudinwthedespitepastshapthreeyyspearsGuenot,notouponlyforwithofgoersoteams,dainadvice,vbuttonioalsoFwithttIheforencouragemef?ten.tadministrativtoeproTherefore,ceedCatherinewithhalmrencythankresearcolytech.onderfulHeinw,asmalwmaortingysAndreaamvanailableAnne-LaureforSt?phanediscussions,ran?oiscpassionorrpehectingmem-methewhenevresearcerhIBeauxis,propr,osedvidhalf-bak,edJuanideasLisaandrsharingVpatienthetlywhistinsighalsotssandthevision.ofMost-ofduth?coehnique'resultssta,inhathisnotthesisFhamvelleeandinyshelpingocomplicatedmepapwIa296y?coleorwhicanotherthebrenceeneptalsooinuenced.bthankyottomDaleheartandtshisbrotherwysork.and,Mymgratitudebringingalsocolorgolife.esIvtoGazeau,Jean-MarcViel,AndreoliPandon,RoLengrandyFDycWirionkhotheirforfortakingandsomerooftthoryetoirbpreciousoftimeottorreviewhthisUlricdoHerbcumenRomaint.SylvIPradalieamMikialsoDagratefulSatooureyElaineM?rioPimenAlvim,tel,AnIanCordeiro,MacAllali,kie,KrameIlianoandCervrankesatoalenciandforDamianopleasanMazzatimefeorenacceptingtogether.toambgratefuleCarlopartOlarteofco-organizingmsevyeditionsjurythe.sudSpameriecialainethanksLIXtoWithoutmleyolyteccolleaguessateLIX,Iinouldparticular,vtocertainlythelastedmeminbrance.eIrsustofIsabtheBiercewicz,TMoreauarskiAandreChLemarecurcforhmeoce,theDaFvidhBaelerde,ork.OlivieralsoDelandetheandstairAlexisofSaurin,Pashnique,wh,ellofaswtoFthehmemkbmeersgoanddcollabeora-FinallytorsIoffromthebPofARSIFyALmteam,parenLutzandStrassburger,yKaustuvforChaudhauri,suppElainemePimenintel,ecial,AlwyenforTiu,joStefanandHetzl,toAgatayCiabattoni,NicolascateiiifreeAbstracteAlthoughforlogicasandtheoryprotheofwhattheorythhaisvtecalculusbdiereneandenofsuccessfullynon-canonicalusedsearcasultisets.awframeweorkencoforetheorspwecicationbofmeta-lcomputationaresystems,faithfullytheretuitionisticisofstilleanuseimpeortantotandgapresultbdistancesetcweceenlinearthegeneralsystemssystemsthatclassicallogicacanfaithfullycaptureandandcut),theralsystemsprousedequivinypractice.ThenThislogicthesisoattemptsineartotreduceulti-conclusionthiseralgapthebeyofexploiting,usinginIntheonencondata,textfoofethespcomputation-as-protainsof-searcandhwparadigmgraph,fortoswandokingnon-canonicaltaspking.ectswofcansequenastorkcalculus,pronamelyminimal,thetionistic,pFirst,olaritythatassignmentlinearinonefotcusedeductiondsequenprandodeofsthandliminationtheandlinesarusingloesgicpexptsonentialsel.eWthateonenexploitcatheseiasposeectstheoriesindethreeofdiaerenfortanddomainscusingofFcomputerconsciencethesis,:vtabledypdeduction,canlogicalbframewlogiorks,onenandwalgorithmictsptoecications.ultisetsThisthenthesiswproprovidescanalinkprosimpleofationtheoretictexplanationops,forintabledfromdeductionlybillustrateysevexploitingsucthea'sfactthethataintivintedtuitionisticalgorithmlogiceatomsacanrphismbypehecassignedWarbitraryshopthatolaritlogicyb.usedAatableframewisforadingpartiallyoforderedforsetinofuiformandulaslogics.andwisdemonstrateincorpwithoratedsingleinlogicto,acanproaccounoffvianaturalm(normalulticutnon-normal),derivtations.(withHere,withoutwnaturaleductioncionsgeneiederrules,tdeductionwtableauxoofcases:ystemstheyrstlogicalcasealencisandwhenttablesolaritconassignmentaintoonlyevniteliterals.sucwcexploitessesfactandlineartheexpsecondtialscasenotisnwhenntablescalmapropylalsologicconthattainenconitedierenfailurproessystems;.example,Wmesystempropinoselogicasevfofocusedproprosystems.oforsystemlastfortributioneacthishwoneinofestigatettheesalgorithmsebcasesexpressedandysholinearwc'sthat,expintials.someparticular,subsetseofdierenlogic,expthetialsonlylopromofsofandandopwenshoderivthatationscusedaofvhailablebinpreciselytheseedsystemsaarealgorithmicthoseecicthatlanguagedoanotconattemptwhile-lotoconditionals,reproinsertionvtoedeletiontmaFinalbled,formeulas.thisWwitheeralillustratealgorithms,thesehresultsDijkstrwithalgorithmsomendingexamples,shortestsucinhpasisimelyueighlgraphation,anwinningforstrategies,handcletifpgrapholymbipartite.ot

.ts.1.In.tro.duction.1.1.1.Outline..texts...Sm...............................p...rs.ob.......framew.....60.........Deduction....................3.2spNon-canonical.aspwithects.of.thetSequen.t.Calculus.53.122.1.Syn.taxand.....In...........o...enco...4.3...................The.....System...4.9.....and.......................for....5462.2tSequen.t.Calculus..ables.tied.....able.......................orks.........of.......................ob.and.....dequacy..6.2.3.In.tuitionistic.Logic........4.4...........R.....ree...........of.........nalyt.....................remarks......10.2.4.Linear.Logic......3.9ten.......................3.10.freezing.with.ts.........T.p...............3.10.2.univ.ly.p.........3.11.pro..10.2.5.F.o.cusing................................3.13.re.................4.for.59.duction.....................4.2........13.3.Incorp.orating.tables.in.toEncoproct-logicofsm21of3.1.In.tro.duction..4.2.2.els...............6.t.....................Deduction...................4.5.Generalized.es.........4.6......21.3.2.Some.motiv.ating.examples....75.ableaux.KE...............77.an's.c.................W.....................4.1023he3.3.T.able.as.m.ulticut.deriv.ation........................41.LJF........................................24.3.4.F.o42cusingAandecicpdisciplineolaritablingtxedioines.via.LJF..............3.10.1.ables.xed.oin.literals...........................46.T.with.e.al.quan.xed2oin5literals3.5.F.o.cused.Pro.ofs.with.Cuts50.T.as.of.ject.....................................52.Examples....................27.3.6.A.sp.ecic.p.olarit.y.discipline.for.tabl.ing53.Conclusions.futu.w.................................56.A.ork.pro.systems.4.1.tro31.3.6.1.Ho.w.to.pro.vide.an.atom.with.a.p.olarit.y?................59.Preliminaries........................31.3.6.2.The.LJF.Con..pro.of.system..4.2.1.ding.je.f.r.ulas.pro.con.................60.A.lev.for.dings....................32.3.6.3.Dropping.the.re2lease-leftSequenruleCalculus.......................................64.Natural..............33.3.7.T.able.s.of.nite.successes..........67.Natural.with.Elimination.ul...................70.F.Deduction............................34.3.7.1.The.Horn.clause.case..4.7.T.Pro.System.................................4.8.ully.A.i.Cut................34.3.7.2.More.than.Horn.clauses....79.Related.ork.........................................81.Conclusions.furt.r......37.3.8.A.Pro.of.Theoretic.Notion.for.Fixed.P.oin.ts..81..vi.Con.ten.ts.5.Linear.Logic.withorksub.exp1onen127tials.85.5.1.Linear.Logic.with.Subtheirexp.onen.tialstials.......130.ting.7.3.3...............orks.............i.......a........85c5.2.F.o.cusing.i.nnewlinear.logic.with.sub.exp.onen.tials..................endix...y.......and.........thmic.with.tro..8.8.5.2.1.Case.withoutminimalre.lev.an.t128form.ulas........and...............lo.......131.........eci.........131..89.5.2.2.A.dding.relevComplexitan.t.form.ulas..135...........Conclusions.........Conclusions.deduction.dings...................6.9.w..........96.5.3.Creating.and7moedifyinglinearsubexpexp7.1onen.tials....................Example:.t.ultiset.............Preliminaries..............98.5.4.Related.WIncludingorkst.erations.........7.3.2.Structures...............ts.................Creation.cations...............7.4.ying............101.5.5.Conclusions.andExamplesfuture.w.orks................134.Analysis...................Related.....................137.future..1.03.6.F.o.cusing.in.linear38metaAlogicA.1withasublogicexp.onen.tials.105.6.1143InIndextro.duction........................124.Conclusions.future.orks.................................24.Algori.sp.cications.n.logic.sub.onen.127.In.duction105.6.2.Preliminaries......................................7.2.a.elemen.of.m...........................7.3........106.6.3.G1{mic}..............................7.3.1.denitions.arithme.i.op...................130.Represen.Data..........................106.6.4130Multi-conclusionComplemenProofofcationsSystem.for.In.tuitionistic.Logic......................7.3.4.of.lo..........110.6.5.A.fo.cused.m.ulti-conclusion.system.for.In.tuitionistic131LogicSp.f.Algorithms............................113.6.6.LKF....7.5.............................................7.6.y.......................................7.71W16.6.7.LJF......................................7.8.and.w.................................1.8.141.App.143.Natural.rules.nd.linear120enco6.8.Other.F.o.cused.Pro.of.Systems....Bibliograph.147.154.connectionChapteruseful1theInfotroTheductioninItphasesisounfortunatetthatstatescomputersequenceartifactser,arehoftenHoconstructeducinof-searcsucquenthencanproadsequenhovcualfashion.spSoftinferencewearecalledishusuallytheyjusttzbuiltolaritytoexpruncomputereciensearctlybwciofthoutttorepresenocalculusmanaytheerrors.wOthereimpcomortanthetrunscanoncerns,manthatviors.arethatessen1992tialstructuredforptheforqualitulasyorofcomlarge,sequencomplicated,ects,andfoexplineensivyedierensystems,thearewleftlasidelusorinwhen].addressed,atheyderivaresenotparadigmhandledforwiws:thsequenformal;andtprecisermethoderivds:theforitsexamplethe,fromcTherefore,orre,einctnesssawiffromprogramstrealersa.lysystemscomputedisciplinewhalloaofstinwconsiderasalinsometended;Amosucdularitywhereoiulasfgativedierentrotesprogramsascanvbasenon-canonicalcompeosed1withoutsequenaectingformtheirnon-canonicalindividualthebmentehadviors;andrloe,adabilitytheparadigmifdomainsoneAcanofeasilyeunderstandprotheandlogic