Bücher von Helmut Schwichtenberg

The Marktoberdorf Summer School 1995 'Logic of Computation' was the 16th in a series of Advanced Study Institutes under the sponsorship of the NATO Scientific Affairs Division held in Marktoberdorf. Its scientific goal was to survey recent progress on the impact of logical methods in software development. The courses dealt with many different aspects of this interplay, where major progress has been made. Of particular importance were the following. ¿ The proofs-as-programs paradigm, which makes it possible to extract verified programs directly from proofs. Here a higher order logic or type theoretic setup of the underlying language has developed into a standard. ¿ Extensions of logic programming, e.g. by allowing more general formulas and/or higher order languages. ¿ Proof theoretic methods, which provide tools to deal with questions of feasibility of computations and also to develop a general mathematical understanding of complexity questions. ¿ Rewrite systems and unification, again in a higher order context. Closely related is the now well-established Grabner basis theory, which recently has found interesting applications. ¿ Category theoretic and more generally algebraic methods and techniques to analyze the semantics of programming languages. All these issues were covered by a team of leading researchers. Their courses were grouped under the following headings.

Recent developments in computer science clearly show the need for a better theoretical foundation for some central issues. Methods and results from mathematical logic, in particular proof theory and model theory, are of great help here and will be used much more in future than previously. This book provides an excellent introduction to the interplay of mathematical logic and computer science. It contains extensively reworked versions of the lectures given at the 1997 Marktoberdorf Summer School by leading researchers in the field.Topics covered include: proof theory and specification of computation (J.-Y. Girard, D. Miller), complexity of proofs and programs (S. R. Buss, S. S. Wainer), computational content of proofs (H. Schwichtenberg), constructive type theory (P. Aczel, H. Barendregt, R. L. Constable), computational mathematics, (U. Martin), rewriting logic (J. Meseguer), and game semantics (S. Abramski).

For some years, specification of software and hardwaresystems has been influenced not only by algebraic methodsbut also by new developments in logic. These newdevelopments in logic are partly based on the use ofalgorithmic techniques in deduction and proving methods, butare alsodue to new theoretical advances, to a great extentstimulated by computer science, which have led to new typesof logic and new logical calculi. The new techniques,methods and tools from logic, combined with algebra-basedones, offer very powerful and useful tools for the computerscientist, which may soon become practical for commercialuse, where, in particular, more powerful specification toolsare needed for concurrent and distributed systems. This volume contains papers based on lectures by leadingresearchers which were originally given at an internationalsummer school held in Marktoberdorf in 1991. The papers aimto give a foundation for combining logic and algebra for thepurposes of specification under the aspects of automateddeduction, proving techniques, concurrency and logic,abstract data types and operational semantics, andconstructive methods.