Alexander Leitsch - Böcker

On the history of the book: In the early 1990s several new methods and perspectives in au- mated deduction emerged. We just mention the superposition calculus, meta-term inference and schematization, deductive decision procedures, and automated model building. It was this last ?eld which brought the authors of this book together. In 1994 they met at the Conference on Automated Deduction (CADE-12) in Nancy and agreed upon the general point of view, that semantics and, in particular, construction of models should play a central role in the ?eld of automated deduction. In the following years the deduction groups of the laboratory LEIBNIZ at IMAG Grenoble and the University of Technology in Vienna organized several bilateral projects promoting this topic. This book emerged as a main result of this cooperation. The authors are aware of the fact, that the book does not cover all relevant methods of automated model building (also called model construction or model generation); instead the book focuses on deduction-based symbolic methods for the construction of Herbrand models developed in the last 12 years. Other methods of automated model building, in particular also ?nite model building, are mainly treated in the ?nal chapter; this chapter is less formal and detailed but gives a broader view on the topic and a comparison of di?erent approaches. Howtoreadthisbook: In the introduction we give an overview of automated deduction in a historical context, taking into account its relationship with the human views on formal and informal proofs.

Schemata are formal tools for describing inductive reasoning. They opened a new area in the analysis of inductive proofs.The book introduces schemata for first-order terms, first-order formulas and first-order inference systems. Based on general first-order schemata, the cut-elimination-by-resolution (CERES) method—developed around the year 2000—is extended to schematic proofs. This extension requires the development of schematic methods for resolution and unification which are defined in this book. The added value of proof schemata compared to other inductive approaches consists in the extension of Herbrand’s theorem to inductive proofs (in the form of Herbrand systems, which can be constructed effectively). An application to an analysis of mathematical proof is given.  The work also contains and extends the newest results on schematic unification and corresponding algorithms.Core topics covered:first-order schematacut-elimination by resolutionpoint transition systemsschematic resolutionHerbrand systemsinductive proof analysisThis volume is the first comprehensive work on first-order schemata and their applications. As such, it will be eminently suitable for researchers and PhD students in logic and computer science either working or with an interest in proof theory, inductive reasoning and automated deduction.  Prerequisites are a firm knowledge of first-order logic, basic knowledge of automated deduction and a background in theoretical computer science.Alexander Leitsch and Anela Lolic are affiliated with the Institute of Logic and Computation of the Technische Universität Wien, David M. Cerna with the Czech Academy of Sciences, Institute of Computer Science (Ústav informatiky AV ČR, v.v.i.).

The last ten years have seen a gradual fragmentation of the Automated Reas- ing community into various disparate groups, each with its own conference: the Conference on Automated Reasoning (CADE), the International Workshop on First-Order Theorem Proving (FTP), and the International Conference on - tomated Reasoning with Analytic Tableau and Related Methods (TABLEAUX) to name three. During 1999, various members of these three communities d- cussed the idea of holding a joint conference in 2001 to bring our communities togetheragain.Theplanwastoholdaone-o?conferencefor2001,toberepeated ifitprovedasuccess.Thisvolumecontainsthepaperspresentedattheresulting event:the?rstInternationalJointConferenceonAutomatedReasoning(IJCAR 2001), held in Siena, Italy, from June 18-23, 2001. We received 88 research papers and 24 systems descriptions as submissions. Each submission was fully refereed by at least three peers who were asked to writeareportonthequalityofthesubmissions.Thesereportswereaccessibleto membersoftheprogrammecommitteeviaaweb-basedsystemspeciallydesigned for electronic discussions.As a result we accepted 37 research papers and 19 system descriptions, which make up these proceedings. In addition, this volume contains full papers or extended abstracts from the ?ve invited speakers. Tenone-dayworkshopsandfourtutorialswereheldduringIJCAR2001.The automatedtheoremprovingsystemcompetition(CASC)wasorganizedbyGeo? Sutcli?e to evaluate the performance of sound, fully automatic, classical, ?r- order automated theorem proving systems. The third Workshop on Inference in Computational Semantics (ICoS-3) and the 9th Symposium on the Integration of Symbolic Computation and Mechanized Reasoning (CALCULEMUS-2001) were co-located with IJCAR 2001, and held their own associated workshops and produced their own separate proceedings.

The Third Kurt G|del Symposium, KGC'93, held in Brno, CzechRepublic, August1993, is the third in a series of biennialsymposia on logic, theoretical computer science, andphilosophy of mathematics. The aim of this meeting wastobring together researchers working in the fields ofcomputational logic and proof theory. While proof theorytraditionally is a discipline of mathematical logic, thecentral activity in computational logic can be foundincomputer science. In both disciplines methods were inventedwhich arecrucial to one another. This volume contains theproceedings of the symposium. It contains contributions by36 authors from 10 different countries. In addition to 10invited papers there are 26 contributed papers selected fromover 50 submissions.

This book constitutes the refereed proceedings of the 5th Kurt Godel Colloquium on Computational Logic and Proof Theory, KGC '97, held in Vienna, Austria, in August 1997.The volume presents 20 revised full papers selected from 38 submitted papers. Also included are seven invited contributions by leading experts in the area. The book documents interdisciplinary work done in the area of computer science and mathematical logics by combining research on provability, analysis of proofs, proof search, and complexity.

The History of the Book In August 1992 the author had the opportunity to give a course on resolution theorem proving at the Summer School for Logic, Language, and Information in Essex. The challenge of this course (a total of five two-hour lectures) con­ sisted in the selection of the topics to be presented. Clearly the first selection has already been made by calling the course "resolution theorem proving" instead of "automated deduction" . In the latter discipline a remarkable body of knowledge has been created during the last 35 years, which hardly can be presented exhaustively, deeply and uniformly at the same time. In this situ­ ation one has to make a choice between a survey and a detailed presentation with a more limited scope. The author decided for the second alternative, but does not suggest that the other is less valuable. Today resolution is only one among several calculi in computational logic and automated reasoning. How­ ever, this does not imply that resolution is no longer up to date or its potential exhausted. Indeed the loss of the "monopoly" is compensated by new appli­ cations and new points of view. It was the purpose of the course mentioned above to present such new developments of resolution theory. Thus besides the traditional topics of completeness of refinements and redundancy, aspects of termination (resolution decision procedures) and of complexity are treated on an equal basis.

This is the first book on automated model building, a discipline of automated deduction that is of growing importance. Although models and their construction are important per se, automated model building has appeared as a natural enrichment of automated deduction, especially in the attempt to capture the human way of reasoning. The book provides an historical overview of the field of automated deduction, and presents the foundations of different existing approaches to model construction, in particular those developed by the authors. Finite and infinite model building techniques are presented. The main emphasis is on calculi-based methods, and relevant practical results are provided. The book is of interest to researchers and graduate students in computer science, computational logic and artificial intelligence. It can also be used as a textbook in advanced undergraduate courses.

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.