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).
Author(s): Ulrich Berger, Helmut Schwichtenberg (eds.)
Series: NATO ASI series. Series F. Computer and systems sciences, vol. 165
Publisher: Springer
Year: 1999
Language: English
Pages: 450
Tags: Logics and Meanings of Programs; Mathematical Logic and Formal Languages; Programming Languages, Compilers, Interpreters
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
