Computational LogicUlrich Berger, Helmut Schwichtenberg 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). |
Contents
Game Semantics | 1 |
Notes on the Simply Typed Lambda Calculus | 57 |
Problems in Type Theory | 99 |
Dijkstras Algorithm a Case Study | 113 |
Prepositional Proof Complexity An Introduction | 127 |
Formalizing Decidability Theorems About Automata | 179 |
Syntax Versus Semantics | 215 |
Complexity of Primitive Recursion | 273 |
Computers Reasoning and Mathematical Practice | 301 |
Research Directions in Rewriting Logic | 347 |
Sequent Calculus and the Specification of Computation | 399 |
Other editions - View all
Common terms and phrases
abstract algebra algorithm apply atomic automata axiom B₁ bound classical coherent space completeness Computer Science concurrent constructive context corresponding cut-elimination cut-free define definition denote equational equivalence example expression fact finite first-order formal formulas Frege Frege proof Frege systems function game semantics given goal graph Harrop formulas Hopcroft and Ullman Horn clauses I-proof induction hypothesis inference rules input interpretation intuitionistic logic lambda calculus Lemma linear logic logic programming M₁ mathematicians multiset natural numbers node notation Note notion Nuprl object-oriented operational semantics operations output Petri net play polynomial primitive recursive problem programming language proof system propositional provable prove quantifiers redex result rewrite rules rewrite theory rewriting logic sequent calculus set theory specification Springer strategy structure subformula subset symbols techniques theorem prover tree-proof type theory variables