Bøker i Cambridge Tracts in Theoretical Computer Science-serien

The author presents a theory whereby nets, terms and formulas represent concurrent processes at three levels of abstraction. The use of transformations in a series of case studies and the author identifies directions for research.

Declarative programs consist of mathematical functions and relations and are amenable to formal specification and verification, since the methods of logic and proof can be applied to the programs in a well-defined manner. Here Dr Padawitz emphasizes verification based on logical inference rules, i.e. deduction (in contrast with model-theoretic approaches, deductive methods can be automated to some extent). His treatment of the subject differs from others in that he tries to capture the actual styles and applications of programming; neither too general with respect to the underlying logic, nor too restrictive for the practice of programming. He generalizes and unifies results from classical theorem-proving and term rewriting to provide proof methods tailored to declarative program synthesis and verification. Detailed examples accompany the development of the methods, whose use is supported by a documented prototyping system. The book can be used for graduate courses or as a reference for researchers in formal methods, theorem-proving and declarative languages.

In this book the authors use the formal specification language PSF to provide descriptions of several communication protocols.

The Z notation is a language for expressing mathematical specifications of computing systems. By providing a formal semantics for Z, this book justifies the claim that Z is a precise specification language, and provides a standard framework for understanding Z specifications.

Artificial intelligence has recently turned to formal logic in the search for powerful yet well-behaved knowledge representation languages. This book, written for workers in artificial intelligence, covers the background of classical logic, including the major meta-theorems, and the state of the art in theorem proving, including Bibel's connection method.

Originally published in 1988, this book presents an introduction to lambda-calculus and combinators without getting lost in the details of mathematical aspects of their theory. Lambda-calculus is treated here as a functional language and its relevance to computer science is clearly demonstrated.

An introduction to the mathematical foundations of the subject. This work will be welcomed by graduate students and research workers in logic, philosophy and computer science as a textbook for beginners.

This book develops the theory of typed feature structures, a data structure that generalizes both first-order terms and feature structures of unification-based grammars to include inheritance, typing, inequality, cycles and intensionality. The resulting synthesis serves as a logical foundation for grammars, logic programming and constraint-based reasoning systems.

Petri nets are a popular and powerful formal model for the analysis and modelling of concurrent systems. The text is very clearly organised, with every notion carefully explained and every result proved. Clear exposition is given for place invariants, siphons, traps and many other important analysis techniques.

Classical logic has proved inadequate in various areas of computer science, artificial intelligence, mathematics, philosopy and linguistics. This is an introduction to extensions of first-order logic, based on the principle that many-sorted logic (MSL) provides a unifying framework in which to work.

A complete account of the predicate transformation calculus semantics of sequential programs.

This book presents a rigorous foundation for defining Boolean categories and will appeal to graduate students and researchers in theoretical computer science.

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 science of information. They illustrate their theory by applying it to a wide range of phenomena, from file transfer to DNA, from quantum mechanics to speech act theory.

This introduction to the basic ideas of structural proof theory contains a thorough discussion and comparison of various types of formalization of first-order logic. Examples are given of several areas of application, namely: the metamathematics of pure first-order logic (intuitionistic as well as classical); the theory of logic programming; category theory; modal logic; linear logic; first-order arithmetic and second-order logic. In each case the aim is to illustrate the methods in relatively simple situations and then apply them elsewhere in much more complex settings. There are numerous exercises throughout the text. In general, the only prerequisite is a standard course in first-order logic, making the book ideal for graduate students and beginning researchers in mathematical logic, theoretical computer science and artificial intelligence. For the new edition, many sections have been rewritten to improve clarity, new sections have been added on cut elimination, and solutions to selected exercises have been included.

This book introduces and teaches the techniques of type theory by focusing on one particularly neat system and studying it in detail. In this way, all the key ideas are covered without getting involved in the complications of more advanced systems, but concentrating rather on the principles that make the theory work in practice.

The authors describe here a framework in which the type notation of functional languages is extended to include a distinguishing notation for run-times and compile-times. Consequently the ability to specify code and verify program correctness can be improved.

This 2001 book is an introduction to verifying concurrent programs scaling up to a realistic size. It is self-contained and comprehensive, guiding the reader from advanced undergraduate level. Every method is illustrated by examples, and a picture gallery of some of the subject's key figures complements the text.

The logic and methodology of design is examined in this book from the perspective of computer science. Computers provide the context for this both by discussion of the design process for hardware and software systems and by consideration of the role of computers in design in general. The question is whether we can construct a theory of design.

This 1993 book shows how formal logic can be used to specify the behaviour of hardware designs and reason about their correctness. The book is based in part on the author's own research as well as on graduate teaching. Thus it can be used to accompany courses on hardware verification and as a resource for research workers.

A comprehensive 2003 treatment of term rewriting systems from an elementary to an advanced level. Much of this material appeared here for the first time in book form. Ideal for teaching or research, it features numerous exercises with selected solutions on the web, an extensive bibliography and a chapter on applications.

This book, based on courses taught at universities and summer schools, provides a broad introduction to the subject; many exercises are included with their solutions.

This book describes the mathematical aspects of the semantics of programming languages. The main goals are to provide formal tools to assess the meaning of programming constructs in ways independent of both language and platform. To do this the authors explain denotational and operational semantics and exploit the duality between them.

A study of techniques for formal theorem-proving, with particular reference to Cambridge LCF (Logic for Computable Functions). The book is aimed at graduate students and researchers in theoretical computer science.

Action Semantics is a comprehensive introduction to the semantics of programming languages. It will be of use to graduates of computer science and mathematics.

This book tackles the problems of update algorithms for databases. How can one construct and maintain a database of facts, capable of incorporating new information and getting rid of all outdated information, and yet in the process not disturb any other information in the database?

This book gives applications of the theory of process algebra. or Algebra of Comunicating Processes (ACS).

Describes the use of computer programs to check several proofs in the foundations of mathematics.

Recent research on the physical technologies of very large scale integration (VLSI).

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. This book contains a collection of research articles on belief revision that are right up to date and an introductory chapter that presents a survey of current research in the area and the fundamentals of the theory.

This is an advanced 2001 textbook on modal logic, a field which caught the attention of computer scientists in the late 1970s. Researchers in areas ranging from economics to computational linguistics have since realised its worth. The book is for novices and for more experienced readers, with two distinct tracks clearly signposted at the start of each chapter. The development is mathematical; prior acquaintance with first-order logic and its semantics is assumed, and familiarity with the basic mathematical notions of set theory is required. The authors focus on the use of modal languages as tools to analyze the properties of relational structures, including their algorithmic and algebraic aspects, and applications to issues in logic and computer science such as completeness, computability and complexity are considered. Three appendices supply basic background information and numerous exercises are provided. Ideal for anyone wanting to learn modern modal logic.