Matthias Baaz - Böcker

This volume commemorates the life, work and foundational views of Kurt Gödel (1906-78), most famous for his hallmark works on the completeness of first-order logic, the incompleteness of number theory, and the consistency - with the other widely accepted axioms of set theory - of the axiom of choice and of the generalized continuum hypothesis. It explores current research, advances and ideas for future directions not only in the foundations of mathematics and logic, but also in the fields of computer science, artificial intelligence, physics, cosmology, philosophy, theology and the history of science. The discussion is supplemented by personal reflections from several scholars who knew Gödel personally, providing some interesting insights into his life. By putting his ideas and life's work into the context of current thinking and perceptions, this book will extend the impact of Gödel's fundamental work in mathematics, logic, philosophy and other disciplines for future generations of researchers.

This volume commemorates the life, work and foundational views of Kurt Gödel (1906-78), most famous for his hallmark works on the completeness of first-order logic, the incompleteness of number theory, and the consistency - with the other widely accepted axioms of set theory - of the axiom of choice and of the generalized continuum hypothesis. It explores current research, advances and ideas for future directions not only in the foundations of mathematics and logic, but also in the fields of computer science, artificial intelligence, physics, cosmology, philosophy, theology and the history of science. The discussion is supplemented by personal reflections from several scholars who knew Gödel personally, providing some interesting insights into his life. By putting his ideas and life's work into the context of current thinking and perceptions, this book will extend the impact of Gödel's fundamental work in mathematics, logic, philosophy and other disciplines for future generations of researchers.

A compilation of papers presented at the 2001 European Summer Meeting of the Association for Symbolic Logic, Logic Colloquium '01 includes surveys and research articles from some of the world's preeminent logicians. Two long articles are based on tutorials given at the meeting and present accessible expositions of research in two active areas of logic, geometric model theory and descriptive set theory of group actions. The remaining articles cover seperate research topics in many areas of mathematical logic, including applications in Computer Science, Proof Theory, Set Theory, Model Theory, Computability Theory, and aspects of Philosophy. This collection will be of interest not only to specialists in mathematical logic, but also to philosophical logicians, historians of logic, computer scientists, formal linguists and mathematicians in the areas of algebra, abstract analysis and topology. A number of the articles are aimed at non-specialists and serve as good introductions for graduate students.

A compilation of papers presented at the 2001 European Summer Meeting of the Association for Symbolic Logic, Logic Colloquium '01 includes surveys and research articles from some of the world's preeminent logicians. Two long articles are based on tutorials given at the meeting and present accessible expositions of research in two active areas of logic, geometric model theory and descriptive set theory of group actions. The remaining articles cover seperate research topics in many areas of mathematical logic, including applications in Computer Science, Proof Theory, Set Theory, Model Theory, Computability Theory, and aspects of Philosophy. This collection will be of interest not only to specialists in mathematical logic, but also to philosophical logicians, historians of logic, computer scientists, formal linguists and mathematicians in the areas of algebra, abstract analysis and topology. A number of the articles are aimed at non-specialists and serve as good introductions for graduate students.

ThisvolumecontainsthepaperspresentedattheNinthInternationalC- ferenceonLogicforProgramming,Arti?cialIntelligence,andReasoning(LPAR 2002),heldonOctober14-18,2002,attheUniversityofTbilisi(Georgia),- getherwiththeThirdInternationalWorkshoponImplementationofLogics. Therewere68submissions,ofwhicheightbelongedtothespecialsubmission categoryofexperimentalpapers,intendedtodescribeimplementationsorc- parisonsofsystems,orexperimentswithsystems. Eachsubmissionwasreviewed byatleastthreeprogramcommitteemembersandanelectronicprogramc- mitteemeetingwasheldviatheInternet. Thenumberofsubmissionsandshort reviewingperiodcausedalargeamountofwork,andweareverygratefultothe other22PCmembersfortheire?ciencyandforthequalityoftheirreviewsand discussions. Finally,thecommitteedecidedtoaccept30papers. Theprogramme alsoincludesthreeinvitedlecturesandapostersession. Apartfromtheprogrammecomittee,wewouldalsoliketothanktheother people who made LPAR 2002 possible: the additional referees, and the local arrangementschairsKhimuriRhukia,KotePhakadze,GelaChankvetadze,and JemalAntidze. TheInternet-basedsubmissionsoftwareandtheprogramcommitteedisc- sionsoftwarewereprovidedbythesecondco-chair.August2002 MatthiasBaaz AndreiVoronkov ConferenceOrganization ProgramChairs MatthiasBaaz(TechnischeUniversit..atWien) AndreiVoronkov(UniversityofManchester) ProgramCommittee ElviraAlbert(UniversidadPolitecnicadeValencia) FranzBaader(TechnischeUniversit..atDresden) MauriceBruynooghe(KatholiekeUniversiteitLeuven) PatrickCousot(ENSParis) MaartendeRijke(UniversityofAmsterdam) HaraldGanzinger(Max-PlanckInstitut,Saarbruc ..ken) JeanGoubault-Larrecq(ENSdeCachan) MikiHermann(EcolePolytechnique) MatejaJamnik(UniversityofCambridge) NeilJones(KobenhavnsUniversitet) DeepakKapur(UniversityofNewMexico) MaurizioLenzerini(Universit'adiRoma"LaSapienza") GiorgioLevi(Universit'adiPisa) LeonidLibkin(UniversityofToronto) RobertNieuwenhuis(TechnicalUniversityofCatalonia) LeszekPacholski(WroclawskiUniwersytet) MichelParigot(Universit'eParis7) PavelPudlak(MathematicalInstitute,Prague) CarstenSchuermann(YaleUniversity) J..orgSiekmann(DFKISaarbruc ..ken) WolfgangThomas(RWTHAachen) MichaelZakharyaschev(King'sCollege) LocalOrganization KhimuriRhukia KotePhakadze GelaChankvetadze JemalAntidze VIII ConferenceOrganization ListofReferees GianlucaAmato CarlosAreces M.Arenas OferArieli RobertoBarbuti ChristophBenzmueller MartaBilkova BrunoBlanchet AlexandreBoisseau AhmedBouajjani DmitriChubarov PabloCordero VeroniqueCortier AgostinoDovier RachidEchahed MorenoFalaschi C'esarFerri OlivierGasquet BernhardGramlich Jos'eManuelG'omez PhilippedeGroote RainerHaehnle JiriHanika JuanHeguiabehere JoseHernandez-Orallo ThomasHillenbrand JoeHurd EmilJerabek ValentinJijkoun KonstantinKorovin G. Lakemeyer DominiqueLarchey-Wendling OlivierLaurent StefanLeue LuigiLiquori ChristofLoeding CarstenLutz ChristopherLynch PatrickMaier PaoloMancarella FlorenceMaraninchi MaartenMarx Jesus ' Medina EricaMelis AntoineMin'e RalfM..oller PaulinDeNaurois HansdeNivelle MichaelNorrish ManuelOjeda-Aciego NikolayPelov GuyPerrier ReinhardPichler ChristopherPollett Germ'anPuebla Jean-PierreRessayre ChristianRetor'e AlexandreRiazanov MichalRossler PaulRozi'ere NikitaSakhanenko UlrikeSattler StefanSchlobach ManfredSchmidt-Schauss KonradSlind Anni-YasminTurhan ChristianUrban WimVanhoof YdeVenema So?eVerbaeten UweWaldmann KlausWeich ClausPeterWirth StefanWoehrle ConferenceOrganization IX ConferencesprecedingLPAR2001 RCLP'90,Irkutsk,SovietUnion RCLP'91,Leningrad,SovietUnion,aboardtheship"MichailLomonosov" LPAR'92,St. Petersburg,Russia,aboardtheship"MichailLomonosov" LPAR'93,St. Petersburg,Russia LPAR'94,Kiev,Ukraine,aboardtheship"MarshalKoshevoi" LPAR'99,Tbilisi,RepublicofGeorgia LPAR2000,ReunionIsland,France LPAR2001,Havana,Cuba TableofContents ImprovingOn-DemandStrategyAnnotations ...1 M. Alpuente,S. Escobar,B. Gramlich,S. Lucas First-OrderLogicasaConstraintProgrammingLanguage...19 K. R. Apt,C. F. M. Vermeulen MaintenanceofFormalSoftwareDevelopmentsby Strati?edVeri?cation...36 SergeAutexier,DieterHutter ANoteonUniversalMeasuresforWeakImplicit ComputationalComplexity ...53 ArnoldBeckmann ExtendingCompositionalMessageSequenceGraphs...68 BenediktBollig,MartinLeucker,PhilippLucas SearchingforInvariantsUsingTemporalResolution ...86 JamesBrotherston,AnatoliDegtyarev,MichaelFisher, AlexeiLisitsa ProofPlanningforFeatureInteractions:APreliminaryReport...102 ClaudioCastellini,AlanSmaill AnExtensionofBDI withFunctional CTL DependenciesandComponents...115 MehdiDastani,LeendertvanderTorre BindingLogic:ProofsandModels ...130 GillesDowek,Th'er'eseHardin,ClaudeKirchner DirectedAutomatedTheoremProving...145 StefanEdelkamp,PeterLeven AFrameworkforSplittingBDIAgents...160 XiaocongFan,JohnYen OntheComplexityofDisjunctionandExplicitDe?nability PropertiesinSomeIntermediateLogics...175 MauroFerrari,CamilloFiorentini,GuidoFiorino UsingBDDswithCombinationsofTheories ...190 PascalFontaine,E. PascalGribomont XII TableofContents OnExpressiveDescriptionLogicswithCompositionofRolesin NumberRestrictions...202 FabioGrandi QueryOptimizationofDisjunctiveDatabaseswithConstraints throughBindingPropagation ...216 GianluigiGreco,SergioGreco,IrinaTrubtsyna,EsterZumpano ANon-commutativeExtensionofMELL...231 AlessioGuglielmi,LutzStrassburger ProceduralSemanticsforFuzzyDisjunctivePrograms...247 Du?sanGuller PushdownSpeci?cations...262 OrnaKupferman,NirPiterman,MosheY. Vardi TheoremProvingwithSequenceVariablesandFlexible AritySymbols...

This book constitutes the joint refereed proceedings of the 17th International Workshop on Computer Science Logic, CSL 2003, held as the 12th Annual Conference of the EACSL and of the 8th Kurt Godel Colloquium, KGC 2003 in Vienna, Austria, in August 2003.The 30 revised full papers presented together with abstracts of 9 invited presentations were carefully reviewed and selected from a total of 112 submissions. All current aspects of computer science logic are addressed ranging from mathematical logic and logical foundations to the application of logics in various computing aspects.

This is the first book on cut-elimination in first-order predicate logic from an algorithmic point of view. Instead of just proving the existence of cut-free proofs, it focuses on the algorithmic methods transforming proofs with arbitrary cuts to proofs with only atomic cuts (atomic cut normal forms, so-called ACNFs). The first part investigates traditional reductive methods from the point of view of proof rewriting. Within this general framework, generalizations of Gentzen's and Sch\”utte-Tait's cut-elimination methods are defined and shown terminating with ACNFs of the original proof. Moreover, a complexity theoretic comparison of Gentzen's and Tait's methods is given.The core of the book centers around the cut-elimination method CERES (cut elimination by resolution) developed by the authors. CERES is based on the resolution calculus and radically differs from the reductive cut-elimination methods. The book shows that CERES asymptotically outperforms all reductive methods based on Gentzen's cut-reduction rules. It obtains this result by heavy use of subsumption theorems in clause logic. Moreover, several applications of CERES are given (to interpolation, complexity analysis of cut-elimination, generalization of proofs, and to the analysis of real mathematical proofs). Lastly, the book demonstrates that CERES can be extended to nonclassical logics, in particular to finitely-valued logics and to G\"odel logic.