Type theory is one of the most important tools in the design of higher-level programming languages, such as ML. This book introduces and teaches its techniques by focusing on one particularly neat system and studying it in detail. By concentrating on the principles that make the theory work in practice, the author covers all the key ideas without getting involved in the complications of more advanced systems. This book takes a type-assignment approach to type theory, and the system considered is the simplest polymorphic one. The author covers all the basic ideas, including the system's...

Belief revision is a topic of much interest in theoretical computer science and logic, and it forms a central problem in research into artificial intelligence. In simple terms: how do you update a database of knowledge in the light of new information? What if the new information is in conflict with something that was previously held to be true? An intelligent system should be able to accommodate all such cases. This book contains a collection of research articles on belief revision that are completely up to date and an introductory chapter that presents a survey of current research in the...

This book discusses recent research in the theoretical foundations of several subjects of importance for the design of hardware, and for computer science in general. The physical technologies of very large scale integration (VLSI) are having major effects on the electronic industry. The potential diversity and complexity of digital systems have begun a revolution in the technologies of digital design, involving the application of concepts and methods to do with algorithms and programming. In return, the problems of VLSI design have led to new subjects becoming of importance in computer...

This advanced textbook on topology has three unusual features. First, the introduction is from the locale viewpoint, motivated by the logic of finite observations: this provides a more direct approach than the traditional one based on abstracting properties of open sets in the real line. Second, the author freely exploits the methods of locale theory. Third, there is substantial discussion of some computer science applications. As computer scientists become more aware of the mathematical foundations of their discipline, it is appropriate that such topics are presented in a form of direct...

Information is a central topic in computer science, cognitive science, and philosophy. In spite of its importance in the "information age," there is no consensus on what information is, what makes it possible, and what it means for one medium to carry information about another. Drawing on ideas from mathematics, computer science, and philosophy, this book addresses the definition and place of information in society. The authors, observing that information flow is possible only within a connected distribution system, provide a mathematically rigorous, philosophically sound foundation for a...

The automatic verification of large parts of mathematics has been an aim of many mathematicians from Leibniz to Hilbert. While Godel's first incompleteness theorem showed that no computer program could automatically prove certain true theorems in mathematics, the advent of electronic computers and sophisticated software means in practice there are many quite effective systems for automated reasoning that can be used for checking mathematical proofs. This book describes the use of a computer program to check the proofs of several celebrated theorems in metamathematics including those of Godel...

Computational learning theory is one of the first attempts to construct a mathematical theory of a cognitive process. It has been a field of much interest and rapid growth in recent years. This text provides a framework for studying a variety of algorithmic processes, such as those currently in use for training artificial neural networks. The authors concentrate on an approximate model for learning and gradually develop the ideas of efficiency considerations. Finally, they consider applications of the theory to artificial neural networks. An abundance of exercises and an extensive list of...

This book discusses the connection between two areas of semantics, namely the semantics of databases and the semantics of natural language, and links them via a common view of the semantics of time. It is argued that a coherent theory of the semantics of time is an essential ingredient for the success of efforts to incorporate more ???real world??? semantics into database models. This idea is a relatively recent concern of database research but it is receiving growing interest. The book begins with a discussion of database querying which motivates the use of the paradigm of Montague Semantics...

This book gives applications of the theory of process algebra, or Algebra of Communicating Processes (ACP), that is the study of concurrent or communicating processes studied using an algebraic framework. The approach is axiomatic; the authors consider structures that are some set of mostly equational axioms, which are equipped with several operators. Thus the term ?algebra? is used in the model-theoretic sense. The axiomatic approach enables one to organize the field of process theories. The theory is applied systematically to a number of situations, including systolic algorithms, semantics...

Chaitin, the inventor of algorithmic information theory, presents in this book the strongest possible version of Godel's incompleteness theorem, using an information theoretic approach based on the size of computer programs. One half of the book is concerned with studying the halting probability of a universal computer if its program is chosen by tossing a coin. The other half is concerned with encoding the halting probability as an algebraic equation in integers, a so-called exponential diophantine equation."