Handbook of Logic in Computer Science. Volume 5: Logic and Algebraic Methods

Samson Abramsky, Dov M Gabbay, Thomas S E Maibaum (eds.)0198537816, 9780198537816

Logic is now widely recognized as one of the foundational disciplines of computing, and its applications reach almost every aspect of the subject, from software engineering and hardware to programming languages and AI. The Handbook of Logic in Computer Science is a multi-volume work covering all the major areas of application of logic to theoretical computer science. The handbook comprises six volumes, each containing five or six chapters giving an in-depth overview of one of the major topics in field. It is the result of many years of cooperative effort by some of the most eminent frontline researchers in the field, and will no doubt be the standard reference work in logic and theoretical computer science for years to come. Volume 5: Algebraic and Logical Structures covers all the fundamental topics of semantics in logic and computation. The extensive chapters are the result of several years of coordinated research, and each have thematic perspective. Together, they offer the reader the latest in research work, and the book will be indispensable

The present Volume 5 continues with logical and algebraic methodologies basic to computer science. Chapter 1 covers Martin-Lof’s type theory, originally developed to clarify the foundations of constructive mathematics it now plays a major role in theoretical computer science. The second chapter covers categorial logic, the interaction area between category theory and mathematical logic. It builds on the basic concepts introduced in the chapter ‘Basic Category Theory’ in Volume 1 of this Handbook series. The third chapter presents methods for obtaining lower bounds on the computational complexity of logical theories. Many such theories show up in the landscape of logic and computation. The fourth chapter covers algebraic specification and types. It treats the subject using set theoretical notions only and is thus accessible to a wide range of readers. The last (fifth) chapter deals with computability on abstract data types. It develops a theory of computable functions on abstract many-sorted algebras, a general enough notion for the needs of computer science.