Computational Logic : Proceedings of the NATO Advanced Study Institute on Computational Logic, held in Marktoberdorf, Germany, July 29-August 10, 1997

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). Front Matter....Pages i-vii Game Semantics....Pages 1-55 Notes on the Simply Typed Lambda Calculus....Pages 57-97 Problems in Type Theory....Pages 99-111 Formal Correctness Proofs of Functional Programs: Dijkstra’s Algorithm, a Case Study....Pages 113-126 Propositional Proof Complexity an Introduction....Pages 127-178 Formalizing Decidability Theorems About Automata....Pages 179-213 On the Meaning of Logical Rules I: Syntax Versus Semantics....Pages 215-272 Complexity of Primitive Recursion....Pages 273-300 Computers, Reasoning and Mathematical Practice....Pages 301-346 Research Directions in Rewriting Logic....Pages 347-398 Sequent Calculus and the Specification of Computation....Pages 399-444 Back Matter....Pages 445-448 Proceedings of the NATO Advanced Study Institute on Computational Logic, held in Marktoberdorf, Germany, July 29 - August 10, 1997