Peter Clote Livres

The foundations of computational complexity theory trace back to Alan Turing in the 1930s, who explored automatic procedures for determining the validity of mathematical statements. A key problem in this field is the undecidability of the Halting Problem, which questions whether a given computer program will eventually halt. Today, computational complexity examines the quantitative aspects of solutions: Is a problem tractable? To measure intractability, various ideas emerged. A. Cobham questioned the appropriate model for defining a "computation step," M. Rabin proposed axioms for complexity measures, and C. Shannon introduced the boolean circuit for computing boolean functions. A crucial inquiry persists: What is the essence of computation? In 1957, John von Neumann noted in his Silliman Lectures that logics and statistics should be viewed as fundamental tools of information theory. He emphasized that the experience surrounding the planning, evaluating, and coding of complex logical and mathematical automata would significantly inform information theory, particularly regarding large electronic computing machines, which are the most typical, though not the only, examples of such automata.

Molecular biology. Math primer. Sequence alignment. All about eve. Hidden markov models. Structure prediction. A mathematical background. Resources.

This book constitutes the refereed proceedings of the 13th International Workshop on Computer Science Logic, CSL 2000, held in Fischbachau, Germany as the 8th Annual Conference of the EACSL in August 2000. The 28 revised full papers presented together with eight invited papers were carefully reviewed and selected by the program committee. Among the topics covered are automated deduction, theorem proving, categorical logic, term rewriting, finite model theory, higher order logic, lambda and combinatory calculi, computational complexity, logic programing, constraints, linear logic, modal logic, temporal logic, model checking, formal specification, formal verification, program transformation, etc.