Our Subjects and Objectives. This book is about algebraic and symbolic computation and numerical computing (with matrices and polynomials). It greatly extends the study of these topics presented in the celebrated books of the seventies, AHU] and BM] (these topics have been under-represented in CLR], which is a highly successful extension and updating of AHU] otherwise). Compared to AHU] and BM] our volume adds extensive material on parallel com- putations with general matrices and polynomials, on the bit-complexity of arithmetic computations (including some recent techniques of data...

This book is a revised edition of the monograph which appeared under the same title in the series Research Notes in Theoretical Computer Science, Pit man, in 1986. In addition to a general effort to improve typography, English, and presentation, the main novelty of this second edition is the integration of some new material. Part of it is mine (mostly jointly with coauthors). Here is brief guide to these additions. I have augmented the account of categorical combinatory logic with a description of the confluence properties of rewriting systems of categor ical combinators (Hardin, Yokouchi),...

Recently, a variety ofresults on the complexitystatusofthegraph isomorphism problem has been obtained. These results belong to the so-called structural part of Complexity Theory. Our idea behind this book is to summarize such results which might otherwise not be easily accessible in the literature, and also, to give the reader an understanding of the aims and topics in Structural Complexity Theory, in general. The text is basically self contained; the only prerequisite for reading it is some elementary knowledge from Complexity Theory and Probability Theory. It can be used to teach a seminar...

The study of the connections between mathematical automata and for- mal logic is as old as theoretical computer science itself. In the founding paper of the subject, published in 1936, Turing showed how to describe the behavior of a universal computing machine with a formula of first- order predicate logic, and thereby concluded that there is no algorithm for deciding the validity of sentences in this logic. Research on the log- ical aspects of the theory of finite-state automata, which is the subject of this book, began in the early 1960's with the work of J. Richard Biichi on monadic...

This monograph is a slightly revised version of my PhD thesis 86], com- pleted in the Department of Computer Science at the University of Edin- burgh in June 1988, with an additional chapter summarising more recent developments. Some of the material has appeared in the form of papers 50,88]. The underlying theme of the monograph is the study of two classical problems: counting the elements of a finite set of combinatorial structures, and generating them uniformly at random. In their exact form, these prob- lems appear to be intractable for many important structures, so interest has focused...

Typing plays an important role in software development. Types can be consid- ered as weak specifications of programs and checking that a program is of a certain type provides a verification that a program satisfies such a weak speci- fication. By translating a problem specification into a proposition in constructive logic, one can go one step further: the effectiveness and unifonnity of a con- structive proof allows us to extract a program from a proof of this proposition. Thus by the "proposition-as-types" paradigm one obtains types whose elements are considered as proofs. Each of these...

This monograph studies the logical aspects of domains as used in de- notational semantics of programming languages. Frameworks of domain logics are introduced; these serve as foundations for systematic derivations of proof systems from denotational semantics of programming languages. Any proof system so derived is guaranteed to agree with denotational se- mantics in the sense that the denotation of any program coincides with the set of assertions true of it. The study focuses on two categories for dena- tational semantics: SFP domains, and the less standard, but important, category of stable...

This monograph develops techniques for equational reasoning in higher-order logic. Due to its expressiveness, higher-order logic is used for specification and verification of hardware, software, and mathematics. In these applica- tions, higher-order logic provides the necessary level of abstraction for con- cise and natural formulations. The main assets of higher-order logic are quan- tification over functions or predicates and its abstraction mechanism. These allow one to represent quantification in formulas and other variable-binding constructs. In this book, we focus on equational logic as...

Starting with Cook's pioneering work on NP-completeness in 1970, polynomial complexity theory, the study of polynomial-time com putability, has quickly emerged as the new foundation of algorithms. On the one hand, it bridges the gap between the abstract approach of recursive function theory and the concrete approach of analysis of algorithms. It extends the notions and tools of the theory of computability to provide a solid theoretical foundation for the study of computational complexity of practical problems. In addition, the theoretical studies of the notion of polynomial-time tractability...